主要内容：分析直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序等常用的内部排序算法的思想，通过交换次数以及比较次数来对这些算法进行比较。 基本要求：通过给定的记录数目及排序思想，设计相应的存储结构，程序之中要求可以实现完全随机，部分逆序等测试数据，来对每一种排序算法进行验证。其次还要设计出一个统计交换次数和比较次数的函数来进行计数。从待排序的记录数目、记录大小、关键字结构及其对稳定性的要求讨论出每种算法使用的环境。 一、设计题目： 常用的内部排序的算法分析和比较 二、运行环境： 操作系统：Windows 软件：Visual C++ 6.0 三、设计目的： 针对常见的计算机内部排序算法，如直接插入排序、希尔排序、冒泡排序、简单选择排序、堆排序、归并排序、基数排序等，通过是自己设计的程序，借助排序中交换次数和比较次数来比较这些算法的适用范围。 四、程序设计的流程图： 
五、算法分析： 1、简单选择排序： 简单选择排序的每一趟都是从待排的数据元素中选出一个最小（最大）的一个元素，顺序的放在已经排好的数列的最后，直到全部待排序的数据元素排序完毕。 2、直接插入排序： 这是一种最简单的排序方法，它的基本操作时将一个记录插入到一个已经排好序的有序表中，从而得到一个新的记录数增1的有序表。其效率：从空间的角度来看待，它只需要一个辅助的空间，从时间上来看的话，排序的基本操作是比较两个关键字的大小和移动（本程序中将移动和交换看成一样）记录。在整个排序的过程中，当待排序列中的关键字非递减有序的话，那么比较次数最小n-1，且不需要移动，当待排序列逆序时，比较次数达到最大（n+2）（n-1）/2，记录的移动的次数也达到最大值（n+4）（n-1）/2。取平均值得时候直接插入排序的时间复杂度O(n²)。排序是稳定的。 3、冒泡排序： 这种排序的比较基本思想就是两两比较待排序的数据元素的大小，发现两个数据元素的次序相反时候，就进行交换，知道没有反序的数据为止。冒泡排序是一次的比较找出最小（最大）值，然后将其放置序列的最后一个位置，再将剩下的从第一个位置开始至n-i的位置进行重复的操作。 4、希尔排序： 属于一种插入排序类的方法，先将整个待排序记录分成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对整体记录进行一次直接插入排序。实质上就是一个将序列分块化，然后再对各个块进行排序，化整为零的操作，最后待序列差不多有序的时候进行一次化零为整操作，实现最后一次的插入排序。 5、快速选择排序： 这个是对冒泡排序的一种改进。它的基本思想就是，在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。 6、堆排序： 堆排序实质上就是具备有如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。它只需要记录一个大小的辅助空间，每个待排序的纪录仅占有一个存储空间。一般对记录数较少的文件并不值得提倡，但是对n较大的文件还是很有效的，因为其运行时间主要是小号在建初始堆和调整建新堆时进行的反复的筛选上的。 7、归并排序： 归并排序实质上就是将两个或者两个以上的有序表组合成一个新的有序表。 8、基数排序： 基数排序是一种借助多关键字排序思想对单逻辑关键字进行的排序方法。中间是涉及到一个重复的分配再收集的操作。具体在本程序中：根据数项个位上的值，将所有的数据项分为10组；然后对这10组数据重新排列，把所有的以0结尾的排在最前，当然需要保证稳定性，然后依次类推以2、3……9开头，接着进行第二趟的排序，由于本程序中用到的数字是1000以内的实例，那么需要有第三趟的操作，最后就是收集，收集完输出的时候是将一个关键字按照百位十位个位一次输出的。 9、排序算法的时间空间复杂度： 
六、程序调试： 1、本程序实例使用的是visual C++ 6.0开发，运行本程序之后出现人机交互的界面如下所示： 2、选择的是第一步操作之后对程序进行随机数据的操作，本次输入的是随机生成23个数据，运行之后会出现相应的系统给出的原来的随机数，以及运行排序之后的全部数据，在此之后给出了各个排序表的比较次数和交换次数的表格，以便于对各个排序的方法得到分析性能： 要求系统产生23个数据， 随机数据为： 2、564、194、809、585、480、351、896、823、747、175、859、711、514、304、15、92、365、148、166、989、446、120 如下图所示 3、进行第二步操作，用户自行的输入一些数据来对各个算法进行性能的测试： 用户输入的测试数据12个， 数据为： 887、44、556、525、4、666、78、91、05、125、58、643 运行之后的界面如下所示： 4、执行第三步操作，系统生成随机的逆序的一组数据： 要求系统随机产生34个数据： 随机的逆序数据是： 989、896、859、823、809、747、711、664、608、602、 585、572、564、532、514、480、451、446、378、365、 353、351、304、194、175、167、166、148、120、92、 15、9、5、2 5、为了确保系统测试的稳定性，本系统中提供的一组数据保证在50个以内，下面是用户要求系统输出50个以上时候系统给出反应 6、程序的安全退出： 一些说明，本程序的健壮性还不是很好，比如说在人机交互的主界面以及数据的录入的时候，用户需要小心的正确输入阿拉伯数字。 七、附录（本程序的源代码及其注释）： #include<stdio.h> #include<stdlib.h> #include<math.h> #define MAXSIZE 50 typedef int KeyType; #define MAXNUM 100 typedef struct{ KeyType key; }RedType; RedType R[MAXNUM];//定义结构体数组 typedef struct{ RedType r[MAXSIZE+1];//r[0]闲置、或者用作哨兵单元 int length; }Sqlist;//顺序表的类型 Sqlist L,L0,L1,L2,L3,L4,L5,L6,L7; typedef Sqlist HeadType; #define RADIX 10//关键字的基数 #define MAX 8//关键字项数的最大值 #define MAX_SPACE 10000 typedef int KeysType; typedef struct { KeysType keys[MAX];//关键字 int next; }SLCell;//静态链表的节点类型 typedef struct
{ SLCell rl[MAX_SPACE]; //静态链表的可利用空间 int keynum; //记录当前的关键字个数 int recnum; //静态链表的当前长度 }SLList;//静态链表的类型 typedef int ArrType[RADIX]; int compare[8];//用来记录比较的次数 int change[8];//用来比较交换的次数 void shuRu(Sqlist &L){//数据录入顺序表 int i=1,n; printf("请输入你输入的数据个数 : \n"); scanf("%d",&n); printf("请依次的输入各个数据值\n"); L.length = n; for(;i<=L.length;i++){ scanf("%d",&L.r[i]); } } void shuChu(Sqlist &L){//输出顺序表中的元素 int i=1; printf("该顺序存储中的数据元素为："); for(;i<L.length;i++){ printf("%d ",L.r[i]); } printf("%d\n\n",L.r[i]); } //==========================================简单选择排序====================== int SelectMinKey(Sqlist &L,int i){//在L.r[i到length]中找到最小值的记录 int k; compare[0] += L.length-i; for(k=i;i<=L.length;i++){ compare[0]++;//记录的是i与length的比较 compare[0]++;//下面的选择语句中的比较 if(L.r[i].key<L.r[k].key){k=i;change[0]++;} } return k; } void SelectSort(Sqlist &L){//顺序表的简单选择排序操作 int i,j,temp; for(i=1;i<L.length;++i){ compare[0]++;//记录的是i与length的比较 j = SelectMinKey(L,i); compare[0]++; if(i!=j){ temp=L.r[i].key;L.r[i].key=L.r[j].key;L.r[j].key=temp; change[0]+=3;//交换次数加3 } } } //======================================直接插入排序================================= void inserSort(Sqlist &L){//直接插入排序 int j; for(int i = 2 ; i<=L.length; ++i) { compare++;//i与length compare++;//记录的是下面选择语句的比较 if(L.r[i].key<L.r[i-1].key){ L.r[0] = L.r[i];//复制为监视哨 L.r[i] = L.r[i-1]; change+=2;//监视哨的赋值，以及位置的后移，交换次数自加； for(j = i-2;j>0;j--){ compare++;//for循环中的比较 compare++;//记录的是下面括号中要进行的比较 if(L.r[0].key>=L.r[j].key) break; L.r[j+1] = L.r[j];//记录后移 change++;//位置后移，交换次数加1 } L.r[j+1] = L.r[0];//插入到正确位置 change++; } } } //========================================冒泡排序============================= void BubbleSort(Sqlist &L){//冒泡排序 int i,j,temp; for(i=1;i<=L.length;i++){ compare++;//记录上面的for循环 for(j=1;j<=L.length-i;j++){ compare++;//上面的for循环的比较 compare++;//下面选择的比较 if(L.r[j].key>L.r[j+1].key){ temp = L.r[j].key; L.r[j].key=L.r[j+1].key; L.r[j+1].key = temp; change+=3; } } } } //========================================希尔排序=================================== void ShellInsert(Sqlist &L, int dk){//以增量dk做一次希尔插入排序 //前后记录的增量式dk，r[0]作为的是一个暂存单元，而不是哨兵，当j<=0时候，表示插入位置找到 int i,j; for(i = dk+1; i<=L.length; ++i){ compare++;//上面的for循环条件比较 compare++;//下面的选择比较 if(L.r[i].key<L.r[i-dk].key){ L.r[0] = L.r[i];//暂存在L.r[0] change++; for(j=i-dk; j>0; j-=dk) {compare++;//for循环 compare++;//下面的比较 if(L.r[0].key>L.r[j].key) break; L.r[j+dk] = L.r[j];//记录后移，查找插入位置 change++; } L.r[j+dk] = L.r[0];//插入 change++; } } } void ShellSort(Sqlist &L){//按增量序列对书序表L做希尔排序 int k; int dlta[] = {5,3,2,1}; int t = 4; for(k=0;k<t;++k){ compare++;//for循环 ShellInsert(L,dlta[k]); } } //=========================快速排序=================================== int Partition(Sqlist &L,int low ,int high){ //交换顺序表L中字表的r[low hingh]的记录，是枢轴记录到位，并返回所在的位置，此时在它之前的记录均不大于它 KeyType pivotkey; L.r[0] = L.r[low]; pivotkey = L.r[low].key; change[4]++; while(low<high){ compare[4]++;//记录的是上面的while循环的条件判断 compare[4]++;//记录下面的循环增加的终止 while(low<high&&L.r[high].key>=pivotkey) {--high;compare[4]++;} L.r[low] = L.r[high];change[4]++; compare[4]++;//记录下面的循环增加的终止 while(low<high&&L.r[low].key<=pivotkey) {++low;compare[4]++;} L.r[high] = L.r[low];change[4]++; } L.r[low] = L.r[0]; change[4]++; return low; } void Qsort(Sqlist &L,int low, int high){//对顺序表L中的子序列做快速排序 int pivotloc; if(low<high){ pivotloc = Partition(L,low,high); Qsort(L,low,pivotloc-1); Qsort(L,pivotloc+1,high); } } void QuickSort(Sqlist &L){//对顺序表做快速排序 Qsort(L,1,L.length); } //======================堆排序=========================================== void HeadAdjust(HeadType &H , int s, int m ){ RedType rc; int j; rc = H.r[s]; for(j = 2s; j<=m; j=2){ compare[5]++;//for循环的调教判断 if(j<m&&(compare[5]++)&&(H.r[j].key < H.r[j+1].key)) ++j; if(rc.key > H.r[j].key ) {compare[5]++;break;} H.r[s] = H.r[j]; s = j; change[5]++; } H.r[s] = rc; change[5]++; }//插入 void HeadSort(HeadType &H){//对顺序表进行堆排序 RedType temp;//中间变量用于保存数值， for(int i = H.length/2 ; i>0; --i){ compare[5]++; HeadAdjust(H,i,H.length);//后续的调整 } for(i=H.length;i>1;--i){ compare[5]++; temp=H.r; H.r=H.r[i]; H.r[i]=temp;//最后的一次记录相互交换 change[5]+=3; HeadAdjust(H,1,i-1);//第一次的调整 } } //==============================归并排序================================= void Merge(RedType SR[],RedType TR[],int i,int m,int n){ int j,k; for(j=m+1,k=i;i<=m&&j<=n;k++){ compare[6]+=2;//for循环中的两个条件判断 if(SR[i].key<SR[j].key) {change[6]++;TR[k] = SR[i++];} else {change[6]++;TR[k] =SR[j++];} } while(i<=m) { compare[6]++; TR[k++] = SR[i++]; change[6]++; } while(j<=n) { compare[6]++; TR[k++] = SR[j++]; change[6]++; } } void MSort(RedType SR[],RedType TR1[],int s,int t){ int m; RedType TR2[MAXSIZE+1]; if(s==t) { compare[6]++;//条件的判断 TR1[s]=SR[s]; change[6]++; } else{ compare[6]++; m=(s+t)/2; MSort(SR,TR2,s,m); MSort(SR,TR2,m+1,t); Merge(TR2,TR1,s,m,t); } } void MergeSort(Sqlist &L){ MSort(L.r,L.r,1,L.length); } //===============================基数排序========================== void CreatSLList(SLList &LK,Sqlist &L){ int i,j; for(i=1;i<=L.length;i++){ compare[7]++; R[i].key=L.r[i].key; } LK.recnum = L.length; LK.keynum = 3;//设置为三位数的比较 for(i=1;i<=LK.recnum;i++) //将给定的数字按照三位数的格式进行拆分。百位、十位、个位 { compare[7]++; j=LK.keynum-1; change[7]+=3;//下面的三个式子 LK.rl[i].keys[j--]=R[i].key/100;//获取的是最高位的，本示例中的是百位上的数字 LK.rl[i].keys[j--]=(R[i].key%100)/10;//获取的是十位上的数字 LK.rl[i].keys[j]=R[i].key%10;//获取的是个位上的数值 } for(i=0;i<LK.recnum;++i){ //将所有的链表用链表连接起来，构成二维的链表 LK.rl[i].next=i+1; } LK.rl[LK.recnum].next=0;//链表循环 change[7]++; } void Distribute(SLCell (&r)[MAX_SPACE],int i,ArrType &f,ArrType &e) {//第i趟分配 int j,p; for(j=0;j<RADIX;j++) {compare[7]++;f[j] =0;}//各子表初始化为空表 for(p=r[0].next; p; p=r[p].next){ j = r[p].keys[i]; change[7]++; if(!f[j]) {f[j]=p;change[7]++;} else {r[e[j]].next = p;change[7]++;} e[j] =p;change[7]++; } } void Collect(SLCell (&r)[MAX_SPACE],int i,ArrType f,ArrType e) //基数排序 { int j,t; for(j=0;!f[j];j++);//找第一个非空的子表 r[0].next=f[j];//r[0]的next指向第一个非空子表的第一个结点 t=e[j];change[7]+=2; while (j<RADIX-1) { compare[7]++; for(j++;j<RADIX-1&&!f[j];j++); { compare[7]++; if (f[j]){ r[t].next=f[j]; t=e[j]; change[7]+=2; } } } r[t].next=0; change[7]++; } void RadixSort(SLList &L){ ArrType f,e; for(int i=0;i<L.recnum;++i) {compare[7]++;L.rl[i].next = i+1;change[7]++;} L.rl[L.recnum].next = 0;//将L改造为一个静态的链表 change[7]++; for(i=0;i<L.keynum;++i){//按照最低位优先一次对各个关键字进行分配和收集 compare[7]++; Distribute(L.rl,i,f,e);//第i趟分配 Collect(L.rl,i,f,e);//第i趟的收集 } } void print(SLList &L){ int i; printf("排序的结果为："); for(i=L.rl[0].next;i;i=L.rl[i].next) //总的大的链表的循环 { compare[7]++; for(int j=L.keynum-1;j>=0;j--) //控制输出一个数据 {compare[7]++; printf("%d",L.rl[i].keys[j]); } printf(" "); } printf("\n"); } //===============================链表复制操作============================= void Copy(Sqlist &L){ L0.length=L.length;L1.length=L.length;L2.length=L.length; L3.length=L.length;L4.length=L.length; L5.length=L.length;L6.length=L.length; L7.length=L.length; for(int i=1;i<=L1.length;i++){ L1.r[i].key=L.r[i].key;L2.r[i].key=L.r[i].key; L3.r[i].key=L.r[i].key;L4.r[i].key=L.r[i].key; L5.r[i].key=L.r[i].key;L6.r[i].key=L.r[i].key; L7.r[i].key=L.r[i].key;L0.r[i].key=L.r[i].key; } } //=====================主菜单======================================= void Menu(){ printf("\t================================================================\t\n"); printf("\t===计算机科学与技术10-02班======傅伟伟======541007010207========\t\n"); printf("\t===================欢迎使用测试内部排序界面=====================\t\n"); printf("\t================================================================\t\n"); printf("\t请选择你要进行的操作\t\n"); printf("\tcase 1: 产生完全随机的数据再进行排序\t\n"); printf("\tcase 2： 自行输入一些数据再实现排序操作\t\n"); printf("\tcase 3： 产生的是一组随机的但是是逆序递增的一组\t\n"); printf("\tcase 0: 退出程序\t\n"); printf("\t为了测试的正常进行，请选择正确的输入形式\t\n"); } //========================输出比较次数和交换次数的表格================= void Table(){ printf("\t@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\t\n"); printf("\t=算法名称===========比较次数==============交换次数================\t\n"); printf("\t1简单选择排序 \t%d\t %d \t\n",compare[0],change[0]); printf("\t2直接插入排序 \t%d\t %d \t\n",compare,change); printf("\t3 冒泡排序 \t%d\t %d \t\n",compare,change); printf("\t4 希尔排序 \t%d\t %d \t\n",compare,change); printf("\t5快速选择排序 \t%d\t %d \t\n",compare[4],change[4]); printf("\t6 堆 排 序 \t%d\t %d \t\n",compare[5],change[5]); printf("\t7 归并排序 \t%d\t %d \t\n",compare[6],change[6]); printf("\t8 基数排序 \t%d\t %d \t\n",compare[7],change[7]); printf("\t@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\t\n"); } //=====================================用于系统产生随机数的情况=============== void Random(Sqlist &L){ SLList LK; for(int i =0;i<8;i++){ compare[i]=0; change[i]=0; } a:printf("请输入你产生的随机数的数据个数 : "); scanf("%d",&L.length); if(L.length>50){ printf("请将输入的个数限制在50之内，请重新输入!\n"); goto a; } for(i=1;i<=L.length;i++) { L.r[i].key =1+(int )(1000.0rand()/(RAND_MAX+1.0));//随机生成1000以内的整数 } printf("排序之前的随机生成的%d个数是:\n",L.length); for(i=1;i<=L.length;i++) printf("%d ",L.r[i].key); Copy(L); printf("\n下面执行的是各个排序的运行情况\n"); SelectSort(L0);//简单选择排序 printf("排序之后的元素：\n"); shuChu(L0); inserSort(L1);//直接插入排序 BubbleSort(L2);//冒泡排序 ShellSort(L3);//希尔排序 QuickSort(L4);//快速选择排序 HeadSort(L5);//堆排序 MergeSort(L6);//归并排序 CreatSLList(LK,L7);//对于静态的链表需要进行的是特殊处理 RadixSort(LK);//基数排序的操作 // print(LK);//用来测试的是基数排序的正确性 Table(); } //=====================用于用户自行的输入一些数值================================= void Yonghu(Sqlist &L){ SLList LK; for(int i =0;i<8;i++){ compare[i]=0; change[i]=0; } shuRu(L); printf("您输入的%d个数据是\n",L.length); for(i=1;i<=L.length;i++) printf("%d ",L.r[i].key); printf("\n"); Copy(L); SelectSort(L0);//简单选择排序 shuChu(L0); inserSort(L1);//直接插入排序 BubbleSort(L2);//冒泡排序 ShellSort(L3);//希尔排序 QuickSort(L4);//快速选择排序 HeadSort(L5);//堆排序 MergeSort(L6);//归并排序 CreatSLList(LK,L7);//对于静态的链表需要进行的是特殊处理 RadixSort(LK);//基数排序的操作 // print(LK);//用来测试的是基数排序的正确性 Table(); } //=================用于系统产生随机数的情况================================= void Nixu(Sqlist &L){ SLList LK; Sqlist la;//用于暂存随机数， int i; for(i =0;i<8;i++){ compare[i]=0; change[i]=0; } a:printf("请输入你产生的随机数的总个数n : "); scanf("%d",&L.length); if(L.length>50){ printf("请将输入的个数限制在50之内，请重新输入!\n"); goto a; } for(i=1;i<=L.length;i++) { L.r[i].key =1+(int )(1000.0rand()/(RAND_MAX+1.0));//随机生成1000以内的整数 } inserSort(L);//直接插入排序使得随机数递增有序 la.length=L.length; i=la.length; for(int k=1;i>=1;i--){//将待排的数据保存在L中，并使得其顺序递减 la.r[k].key = L.r[i].key; k++; } printf("逆序的%d个随机数是：\n",la.length); shuChu(la); Copy(la); SelectSort(L0);//简单选择排序 shuChu(L0); inserSort(L1);//直接插入排序 BubbleSort(L2);//冒泡排序 ShellSort(L3);//希尔排序 QuickSort(L4);//快速选择排序 HeadSort(L5);//堆排序 MergeSort(L6);//归并排序 CreatSLList(LK,L7);//对于静态的链表需要进行的是特殊处理 RadixSort(LK);//基数排序的操作 // print(LK);//用来测试的是基数排序的正确性 Table(); } //======================================主函数用于测试的=================== void main(){ int choose; for(;;){ Menu(); printf("\t请选择："); scanf("%d",&choose); switch(choose){ case 1:Random(L);break; case 2:Yonghu(L);break; case 3:Nixu(L);break; case 0:return; }//switch }//for }