内部排序演示C++ 第3页
#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);
}
void insertion_sort(int n,int A[])//插入排序
{
int mt=0;//移动次数movetime
int ct=0;//比较次数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=1;i<n;i++)
{
temp=a[i],
mt++;
for(j=i-1;j>=0&&temp<a[j];j--,ct++)
a[j+1]=a[j],
mt++;
a[j+1]=temp,
mt++;
}
printf("插入排序");
output(n,a,ct,mt);
}
void shell_sort(int n,int A[])//希尔排序
{
int mt=0;//移动次数movetime
int ct=0;//比较次数cmdtime
int i,j,k,h,y;
int a[N];
for(i=0;i<n;i++)
a[i]=A[i];//使数组a[]与数组A[]完全相同,对数组a[]进行操作(不改动A[],可以使A[]被其他函数调用)
for(i=0;i<t;i++)
{
h=d[i];
for(j=h;j<n;j++)
{
y=a[j],
mt++;
for(k=j-h,ct++,mt++;k>=0&&y<a[k];k-=h)
a[k+h]=a[k];
a[k+h]=y;
}
}
printf("希尔排序");
output(n,a,ct,mt);
}
void main()
{
int n;
int i;
int A[N];
printf("\t*******************************************************\n");
printf("\t******************内部排序时间复杂度比较***************\n");
printf("\t*******************************************************\n");
printf("请输入数组大小(小于100)：");
scanf("%d",&n);//输入所需排序数组大小
for(i=0;i<n;i++)
{
printf("请输入数组a[%d]：",i);
scanf("%d",&A[i]);//依次输入数组A[0]~A[n]
}
bubble_sort(n,A);//冒泡排序
insertion_sort(n,A);//插入排序
selection_sort(n,A);//选择排序
quick_sort(n,A);//快速排序
shell_sort(n,A);//希尔排序
} 710