内部排序演示
【问题描述】
设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。
【基本要求】
(1) 对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较；
(2) 待排序的元素的关键字为整数。其中的数据要用伪随机产生程序产生(如10000个)，至少用5组不同的输入数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较。（gettickcount()）
【数据结构描述】
输入一个无序数组，分别使用内部排序的几种方法：
bubble_sort(n,A);冒泡排序，
insertion_sort(n,A);插入排序
selection_sort(n,A);选择排序
quick_sort(n,A);快速排序
shell_sort(n,A);希尔排序
求出分别的比较次数和移动次数。
【主要算法流程描述】
源程序代码
#include <stdio.h>
#define N 100//定义数组最大为100
const int t=3;//定义希尔排序次数
int d[t]={4,3,1};//定义希尔排序比较量
int qmt;//快速排序的移动次数
int qct;//快速排序的比较次数
void output(int n,int a[],int ct,int mt)//内部排序中调用的输出函数
{
int i;
printf("\n排序结果:");
for( i=0;i<n;i++)
printf("%d ",a[i]);//输出各排序完成的数组
printf("\n比较次数:%d\n",ct);//输出各排序比较次数
printf("移动次数:%d\n\n",mt);//输出各排序移动次数
}
void bubble_sort(int n,int A[])//冒泡排序
{
int mt=0;//移动次数mt=movetime
int ct=0;//比较次数ct=cmdtime
int i,j,temp;
int a[N];
for(i=0;i<n;i++)
a[i]=A[i];//使数组a[]与数组A[]完全相同,对数组a[]进行操作(不改动A[],可以使A[]被其他函数调用)
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++,ct++)
{
if(a[j+1]<a[j])//前后比较
temp=a[j],
a[j]=a[j+1],
a[j+1]=temp,
mt+=3;//关键字交换计为3次移动
}
}
printf("冒泡排序");
output(n,a,ct,mt);
}
void selection_sort(int n,int A[])//选择排序
{
int mt=0;//移动次数movetime
int ct=0;//比较次数cmdtime
int i,j,temp,k;
int a[N];
for(i=0;i<n;i++)
a[i]=A[i];//使数组a[]与数组A[]完全相同,对数组a[]进行操作(不改动A[],可以使A[]被其他函数调用)
for(i=0;i<n-1;i++)
{
k=i;
for(j=i+1;j<n;j++,ct++)
if(a[k]>a[j])
k=j;
temp=a[i],
a[i]=a[k],
a[k]=temp,
mt+=3;//关键字交换计为3次移动
}
printf("选择排序");
output(n,a,ct,mt);
}
void quick(int a[],int low,int up)//快速排序递归算法
{
int i,j,temp;
if(low<up)
{
i=low;
j=up;
temp=a[low],
qmt++;
while(i!=j)
{
qct++;
while(i<j&&a[j]>temp)
j--,
qct++;
if(i<j)
a[i++]=a[j],
qct++;
qmt++;
while(i<j&&a[i]<=temp)
i++,
qct++;
if(i<j)
a[j--]=a[i],
qct++,
qmt++;
}
a[i]=temp,
qmt++;
quick(a,low,j-1);
quick(a,i+1,up);
}
}
void quick_sort(int n,int A[])//快速排序(通过调用快速排序递归算法完成)
{
int i;
int a[N];
for(i=0;i<n;i++)
a[i]=A[i];//使数组a[]与数组A[]完全相同,对数组a[]进行操作(不改动A[],可以使A[]被其他函数调用)
quick(a,0,n-1);//调用快速排序递归算法
printf("快速排序");
output(n,a,qct,qmt);
} 710