// 我真诚地保证：
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。
// 在此，我感谢马晓红学姐对我的启发和帮助。下面的报告中，我还会具体地提到
// 他们在各个方法对我的帮助。
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。
// 我从未抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。
// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
// 郭晓琳
#include<stdio.h>
#include<math.h>
#include<ctime>
#include<string>
#define MAX 10000
#define LEFT(x) 2*(x)
#define RIGHT(x) 2*(x)+1
int cc1=0,sc1=0,cc2=0,sc2=0,cc3=0,sc3=0,cc4=0,sc4=0,cc5=0,sc5=0,sc6=0,cc6=0;
int RANDOM(int a,int b)//RANDOM函数，产生[a,b]之间的一个随机值
{
return rand()%(b-a+1)+a;//rand函数，产生从0~RAND_MAX之间的随机整数
}
int swap(int& x,int& y)//传入的必须是指针，以保证实参的内容得到交换
{
int t=x;
x=y;
y=t;
return 0;
}
int RANDOMIZE_IN_PLACE(int num[],int size)//将一个数组中的元素随机排列
{
for(int i=1;i<=size;i++)
swap(num[i],num[RANDOM(i,size)]);
return 0;
}
int Init(int num[],int size)
{
printf(" compCount shiftCount\n");
for(int i=1;i<=size;i++)
num[i]=i;
return 0;
}
int COPY(int num1[],int num2[],int size)
{
for(int i=1;i<=size;i++)
num2[i]=num1[i];
return 0;
}
int PRINT(int num[],int size)
{
for(int i=1;i<=size;i++)
{
printf("%d ",num[i]);
if(i%20==0)printf("\n");
}
return 0;
}
int QSort(int lo,int hi,int num[])
{
int i,j,m;
if(lo<hi)
{
i=lo;j=hi;m=(lo+hi)/2;
do
{
cc1++;
while(num[i]<num[m]){i++;cc1++;}
while(num[m]<num[j]){j--;cc1++;}
if(i<=j)
{
if(m==i)m=j;
else if(m==j)m=i;
swap(num[i],num[j]);i++;j--;
sc1+=3;
}
}while(i<=j);
QSort(lo,j,num);QSort(i,hi,num);
}
return 0;
}
int QuickSort(int num[],int size)
{
printf("QuickSort: ");
QSort(1,size,num);
printf("%d %d\n",cc1,sc1);
return 0;
}
int BubbleSort(int num[],int length)
{
printf("BubbleSort: ");
for(int j=length-1;j>0;j--)
for(int i=0;i<j;++i){
cc4++;
if(num[i+1]<num[i]){swap(num[i+1],num[i]);sc4+=3;}
}
printf("%d %d\n",cc4,sc4);
return 0;
}
int MAX_HEAPIFY(int A[],int i,int size)
{
int l(LEFT(i)),r(RIGHT(i));
int largest;
cc2+=2;
if(l<=size&&A[l]>A[i])largest=l;
else largest=i;
if(r<=size&&A[r]>A[largest])largest=r;
if(largest!=i)
{
swap(A[i],A[largest]);
sc2+=3;
MAX_HEAPIFY(A,largest,size);
}
return 0;
}
int BUILD_MAX_HEAP(int A[],int size)
{
for(int i=size/2;i>=1;i--)
MAX_HEAPIFY(A,i,size);
return 0;
}
int HEAPSORT(int A[],int size)
{
printf("heapsort: ");
BUILD_MAX_HEAP(A,size);
for(int i=size;i>=2;i--)
{
swap(A[1],A[i]);
sc2+=3;
--size;
MAX_HEAPIFY(A,1,size);
}
printf("%d %d\n",cc2,sc2);
return 0;
}
int InsertSort(int num[],int length)
{
printf("InsertSort: ");
for(int i=2;i<=length;i++)
{
cc3++;
if(num[i]<num[i-1])
{
num[0]=num[i];
num[i]=num[i-1];
int j=i-2;
while(num[j]>num[0]){num[j+1]=num[j];j--;cc3++;}
swap(num[j+1],num[0]);
sc3+=3;
}
}
printf("%d %d\n",cc3,sc3);
return 0;
}
int SelectSort(int num[],int length)
{
printf("SelectSort: ");
for(int i=0;i<length-1;i++)
{
int min=i;
for(int j=i+1;j<length;j++){
cc6++;
if(num[j]<num[min])min=j;
}
if(min!=i){swap(num[i],num[min]);sc6+=3;}
}
printf("%d %d\n",cc6,sc6);
return 0;
}
int ShellSort(int num[],int size)
{
printf("ShellSort: ");
int i=4,h=1;
while(i<=size){i*=2;h=2*h+1;}
while(h)
{
i=h;
while(i<=size)
{
int j=i-h;
cc5++;
while(j>0&&num[j+h]<num[j]){swap(num[j],num[j+h]);j=j-h;cc5++;sc5+=3;}i++;
}
h=(h-1)/2;
}
printf("%d %d\n",cc5,sc5);
return 0;
}
void cCsC(int num[],int n)
{
int temp[MAX];
Init(num,n);
RANDOMIZE_IN_PLACE(num,n);
COPY(num,temp,n);
HEAPSORT(temp,n);
COPY(num,temp,n);
QuickSort(temp,n);
COPY(num,temp,n);
InsertSort(temp,n);
COPY(num,temp,n);
BubbleSort(temp,n);
COPY(num,temp,n);
ShellSort(temp,n);
COPY(num,temp,n);
SelectSort(temp,n);
}
int main()
{
srand((unsigned)time(NULL));
int num[MAX],n=500,t=8;
char cmd;
do
{
printf("*************************************\n");
printf(" 欢迎进入内部排序算法比较程序！ \n");
printf(" 1.排序算法测试 \n");
printf(" 2.选择长度(100-1000) \n");
printf(" 3.选择组数(5-20) \n");
printf(" 4.退出 \n");
printf("*************************************\n");
printf("请输入命令:\n");
fflush(stdin);
scanf("%c",&cmd);
switch(cmd)
{
case '1':break;
case '2':printf("请输入长度：\n");fflush(stdin);scanf("%d",&n);
if(n<100){printf("数据小于100，将按长度100算。");n=100;}
else if(n>1000){printf("数据大于1000，将按长度1000算。");n=1000;}break;
case '3':printf("请输入组数：\n");fflush(stdin);scanf("%d",&t);if(t<5){printf("数据小于5，将按组数5算。");t=5;}
else if(t>20){printf("数据大于20，将按组数20算。");t=20;}break;
case '4':printf("谢谢使用!\n");break;
default:printf("输入错误!\n");break;
}
if(cmd!='4'){
printf("长度%d\t组数%d\n",n,t);
while(t--) cCsC(num,n);
t=8;
n=1000;
}
}while(cmd!='4');
return 0;
}
