《综合排序正式论》word版.doc

目录一、问题描述32.1 基本要求：32.2. 算法思想：32.3. 模块划分：52.4. 数据结构：202.5. 源程序：212.6. 测试情况：32三、小结39四、参考文献40一、 问题描述用C语言编程解决插入、冒泡，快速排序，简单选择，堆排序以及分析各种算法的时间复杂度和空间复杂度，比较各种排序在不同场合的适用程度，分析各种排序算法的实用性。内容简介2.1 基本要求：（1）设计一个的菜单将在实现的功能显示出来，并有选择提示；（2）分别实现直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序，堆排序算法；（3）通过多种测试数据，对各种排序算法的时间复杂度和空间复杂度进行比较2.2. 算法思想：2.2.1简单选择排序基本思想每一趟在n-i+1(i=1,2,n-1)个记录中选取关键字最小的记录作为有序序列的第i个关键字。2.2.2 直接插入排序基本思想插入排序的思想就是读一个，排一个，将第个数放入数组的第个元素中，以后读入的数与已存入数组的数进行比较，确定它在从大到小的排列中应处的位置将该位置以及以后的元素向后推移一个位置，将读入的新数填入空出的位置中2.2.3折半插入排序基本思想从第二个数开始逐个置入监视哨，使用low，high标签进行折半判断比较大小，并确认插入位置，该位置到最后一个数全部后移一位，最后腾出该位置，把监视哨里面的数置入该位置。后面的数以此类推进行排序，直到最后一个数比较完毕。2.2.4希尔排序基本思想希尔排序法是1959年由D.L.Shell提出来的,又称减少增量的排序。下表是以八个元素排序示范的例子.在该例中,开始时相隔4个成分,分别按组进行排序,这时每组2个成分,共4组; 然后相隔2个成分,在按组排序.最后,对所有相邻成分进行排序.2.2.5冒泡排序基本思想依次比较相邻的两个数,把大的放前面,小的放后面.即首先比较第1个数和第2个数,大数放前,小数放后.然后比较第2个数和第3个数.直到比较最后两个数.第一趟结束,最小的一定沉到最后.重复上过程,仍从第1个数开始,到最后第2个数.然后.由于在排序过程中总是大数往前,小数往后,相当气泡上升,所以叫冒泡排序.2.2.6快速排序基本思想快速排序的基本思想是基于分治策略的。对于输入的子序列Lp.r，如果规模足够小则直接进行排序，否则分三步处理：分解(Divide)：将输入的序列Lp.r划分成两个非空子序列Lp.q和Lq+1.r，使Lp.q中任一元素的值不大于Lq+1.r中任一元素的值。 递归求解(Conquer)：通过递归调用快速排序算法分别对Lp.q和Lq+1.r进行排序。合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在Lp.q和Lq+1.r都排好序后不需要执行任何计算Lp.r就已排好序。2.2.7堆排序基本思想堆排序，顾名思义，就是基于堆。因此先来介绍一下堆的概念。堆分为最大堆和最小堆，其实就是完全二叉树。大顶堆要求节点的元素都要大于其孩子，小顶堆要求节点元素都小于其左右孩子，两者对左右孩子的大小关系不做任何要求。有了上面的定义，我们可以得知，处于大顶堆的根节点的元素一定是这个堆中的最大值。其实我们的堆排序算法就是抓住了堆的这一特点，每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最大堆，依次类推，最终得到排序的序列。或者说，堆排序将所有的待排序数据分为两部分，无序区和有序区。无序区也就是前面的最大堆数据，有序区是每次将堆顶元素放到最后排列而成的序列。每一次堆排序过程都是有序区元素个数增加，无序区元素个数减少的过程。当无序区元素个数为1时，堆排序就完成了。本质上讲，堆排序是一种选择排序，每次都选择堆中最大的元素进行排序。只不过堆排序选择元素的方法更为先进，时间复杂度更低，效率更高。 2.3. 模块划分：2.3.1 主函数的算法功能描述开始输入数据个数lengthcreate(),visit()输入select7select654321078select_sort(L); Zhijie(L); ShellSort(L,dlta,4); Maopao(L); QuickSort(L); print(num);HeapSort()QuickSort(L);select_sort(L);Maopao(L);ShellSort()Zhijie(L)Exit(0)BinsertSort()输入y/nny结束2.3.2 退出函数：exit();功能描述：根据提示 输入0，则退出系统2.3.3 选择排序算法功能描述函数：select_sort();开 始int i=1;假 iL.length真int j=i;k=i+1 假kL.lenth真L.rj.keyL.rk.key j=k; k+ i!=j 假真 L.ri L.rji+结 束2.3.4 直接插入排序算法描述开始i=2假i=L.length真L.ri.keyL.ri-1.key假真L.r0=L.ri；L.ri=L.ri-1；j=i-2；假L.r0.keyL.rj.key真L.rj+1=L.rj；-j；L.rj+1=L.r0+i结束2.3.5开始希尔排序算法功能描述k=0假kt真ShellInsert(&L,dltak,&r);i=dk+1;假i=L.length真假L.ri.key0&L.r0.keyL.rj.key假真L.rj+dk=L.rj；j-=dk；L.rj+dk=L.r0+i+k结束2.3.6 冒泡算法功能描述开 始int i=1;假 iL.length真int j=1;假 jL.length-i真L.rj.keyL.rj+1.key假真L.rj L.rj+1j+结 束i+2.3.7快速排序算法功能描述 算法功能描述开始Lowhigh假真真L.r0=L.rlowPivotkey=L.rlow.key假L.rhigh=L.rlow结束L,low,high假Low=pivotkey77L.rlow=L.rhigh真Lowhigh&L.rhigh.key=pivotkey77-high+low算法描述开始真LowhighL,low=pivotloc+1,high=highPivotloc=partioion(L,low,high),low=low,high=pivotloc-1;LowhighL，low，high假真假Pivotloc=partioion(L,low,high),low=low,high=pivotloc-1;QSort(L,low,pivotloc-1)结束2.3.8 堆排序调整为大顶堆堆排序2.3.9 折半插入排序2.3.10 打印函数void visit(SqList L)：打印链表中的数据2.3.12 生成随机序列2.4. 数据结构：（给出所使用的基本抽象数据类型,所定义的具体问题的数据类型,以及新定义的抽象数据类型。）#define MAXSIZE 200#define GET_ARRAY_LEN(array,len)len = (sizeof(array) / sizeof(array0);/定义一个带参数的 宏，将数组长度存储在变量len中typedef int KeyType;typedef struct /定义存储记录关键字及其他信息的结构体 KeyType key; char other;RedType; /记录类型typedef struct /定义存储所有记录的结构体 RedType rMAXSIZE+1; /r0闲置或用作哨兵单元 int length;/顺序表长度SqList;/顺序表类型typedef struct int move; /*记录数据移动次数*/ int comp; /*记录数据比较次数*/ int compex; /*记录空间复杂度*/ Recode;typedef SqList HeapType; /堆采用顺序表存储表示2.5. 源程序：（给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。）#include stdlib.h#include stdio.h #include time.h#include #includeusing namespace std;#define MAXSIZE 200#define GET_ARRAY_LEN(array,len)len = (sizeof(array) / sizeof(array0);/定义一个带参数的 宏，将数组长度存储在变量len中typedef int KeyType;typedef struct /定义存储记录关键字及其他信息的结构体 KeyType key; char other;RedType; /记录类型typedef struct /定义存储所有记录的结构体 RedType rMAXSIZE+1; /r0闲置或用作哨兵单元 int length;/顺序表长度SqList;/顺序表类型typedef struct int move; /*记录数据移动次数*/ int comp; /*记录数据比较次数*/ int compex; /*记录空间复杂度*/ Recode;typedef SqList HeapType; /堆采用顺序表存储表示int dlta5=31,15,7,3,1; /初始化希尔排序的增量序列int num20=0; /记录每个排序方法的移动次数和比较次数int flag=0; /入的数据void create(SqList *L,int length) /创造一个初始排序数列 int i; srand(time(0); /srand函数是随机数发生器的初始化函数 L-length=length; for(i=1;ilength;i+) L-ri.key=rand()%1000; L-ri.other=rand()%26+65; /*输出元素*/ void visit(SqList L) int i; printf(n); for(i=1;i=L.length;i+) printf(%4d%2c,L.ri.key,L.ri.other); printf(n); /*简单选择排序*/ void select_sort(SqList L) Recode r;p =0;r.move =0;pex=1; int i,j,k; RedType t; for (i=1;iL.length;i+) j=i; for (k=i+1;kL.rk.key) p+; j=k; /把无序区最小的挑出来 if (i!=j) /*交换顺序 */ /pex+; t=L.rj; L.rj=L.ri; L.ri=t; r.move =r.move +3; if(!flag) printf(本次随机数据排序的移动次数为:); printf(%dn,r.move); printf(本次随机数据排序的比较次数为:); printf(%dn,p); printf(简单选择排序后的结果：); visit(L);elsenum0=r.move;num1=p; /直接插入排序void Zhijie(SqList L) Recode r;p =0;r.move =0;/pex=0; int j;/ pex+; for(int i=2;i=L.length;+i) / pex +;if(L.ri.keyL.ri-1.key)L.r0=L.ri; /复制为哨兵L.ri=L.ri-1;r.move=r.move +2;for(j=i-2;L.r0.key L.rj.key;-j)L.rj+1=L.rj; /记录后移r.move +;p +;L.rj+1=L.r0; /插入到正确位置r.move +;if(!flag) printf(本次随机数据排序的移动次数为:); printf(%dn,r.move); printf(本次随机数据排序的比较次数为:); printf(%dn,p); printf(直接插入排序后的结果：); visit(L);elsenum2=r.move;num3=p; /希尔排序void ShellInsert(SqList *L,int dk,Recode *r)int i,j;for(i=dk+1;ilength ;+i)r-comp +;if(L-ri.keyri-1.key)L-r0=L-ri; /暂存r-move +;for(j=i-dk;j0&(L-r0.key rj.key);j-=dk)L-rj+dk=L-rj; /记录后移r-move +;r-comp +;L-rj+dk=L-r0; /插入到正确位置r-move +;void ShellSort(SqList L,int dlta,int t) /按增量序列dlta0.t-1对顺序表L作希尔排序。Recode r;p =0;r.move =0;int k;for(k=0;kt;+k) ShellInsert(&L,dltak,&r);/一趟增量为dltak的插入排序if(!flag) printf(本次随机数据排序的移动次数为:); printf(%dn,r.move); printf(本次随机数据排序的比较次数为:); printf(%dn,p); printf(希尔排序后的结果：); visit(L);elsenum4=r.move;num5=p;/冒泡排序法void Maopao(SqList L)Recode r;p =0;r.move =0;int i,j; RedType t;for(i=1;iL.length;i+)for(j=1;jL.rj+1.key) r.move =r.move +3;t=L.rj;L.rj=L.rj+1; L.rj+1=t;if(!flag) printf(本次随机数据排序的移动次数为:); printf(%dn,r.move); printf(本次随机数据排序的比较次数为:); printf(%dn,p); printf(冒泡排序后的结果：); visit(L);elsenum6=r.move;num7=p;/快速排序法int Partition(SqList *L,int low,int high,Recode *r)int pivotkey;L-r0=L-rlow; /用子表的第一个记录作枢轴记录pivotkey=L-rlow.key; /枢轴记录关键字r-move =r-move +2;while(lowhigh) /从表的两端交替的向中间扫描while(lowrhigh.key =pivotkey) -high; r-comp +;L-rlow=L-rhigh; /将比枢轴记录小的记录移到低端 while(lowrlow.key comp+;L-rhigh=L-rlow; /将比枢轴记录大的记录移到高端r-move =r-move+2;L-r low=L-r 0; /枢轴记录到位r-move +;return low; /返回枢轴位置void QSort(SqList *L,int low,int high,Recode *r)int pivotloc;if(lowrlow.high一分为二QSort(L,low,pivotloc-1,r); /对低子表递归排序，pivotloc是枢轴位置QSort(L,pivotloc+1,high,r); /对高子表递归排序void QuickSort(SqList L) Recode r;p =0;r.move =0;QSort(&L,1,L.length,&r);if(!flag)printf(本次随机数据排序的移动次数为:);printf(%dn,r.move);printf(本次随机数据排序的比较次数为:);printf(%dn,p);printf(快速排序后的结果：);visit(L);elsenum8=r.move;num9=p; /*堆排序*/ /堆调整算法void HeapAdjust (HeapType &L, int s, int m) / 已知 H.rs.m中记录的关键字除 H.rs 之外 /均满足堆的特征，本函数自上而下调整 H.rs /的关键字，使 H.rs.m 也成为一个大顶堆Recode r;RedType rc;pex=0;pex+; rc = L.rs; / 暂存 H.rs for (int j=2*s; j=m; j*=2 ) / j 初值指向左孩子自上而下的筛选过程;r.move+; / 自上而下的筛选过程 if ( jm & L.rj.key= L.rj.key ) break; / 再作“根”和“子树根”之间的比较， / 若“=”成立，则说明已找到 rc 的插 / 入位置 s ，不需要继续往下调整 L.rs = L.rj; s = j; r.move+; / 否则记录上移，尚需继续往下调整 L.rs = rc; / 将调整前的堆顶记录插入到 s (注意插入的位置为s j=2*s) r.move+; / HeapAdjustvoid HeapSort ( HeapType &L ) Recode r;p =0;r.move =0; RedType t; / 对顺序表L 进行堆排序for (int i=L.length/2; i0; -i )p+; HeapAdjust ( L, i, L.length ); / 建小顶堆for ( i=L.length; i1; -i ) p+;/ L.r1L.ri;if (i!=1) /*交换顺序 */ /pex+; t=L.r1; L.r1=L.ri; L.ri=t; r.move =r.move +3; / 将堆顶记录和当前未经排序子序列 / H.r1.i中最后一个记录相互交换 HeapAdjust(L, 1, i-1); / 对 L.r1 进行筛选 if(!flag) printf(*本次排序的移动次数为:); printf(%dn,r.move); printf(*本次排序的比较次数为:); printf(%dn,p); printf(堆排序后的结果：); visit(L);elsenum10=r.move;num11=p; / HeapSortvoid BInsertSort(SqList &L) / 对顺序表L作折半插入排序。 Recode r; p =0; r.move =0; /pex=0; int i,j,high,low,m; for (i=2; i=L.length; +i) L.r0 = L.ri; / 将L.ri暂存到L.r0 low = 1; high = i-1; while (low=high) /pex+;/ 在rlow.high中折半查找有序插入的位置 m = (low+high)/2; / 折半 if (L.r0.key=high+1; -j) L.rj+1 = L.rj; / 记录后移r.move =r.move+1; L.rhigh+1 = L.r0; / 插入 r.move =r.move+1; if(!flag) printf(*本次排序的移动次数为:); printf(%dn,r.move); printf(*本次排序的比较次数为:); printf(%dn,p); printf(折半插入排序后的结果：); visit(L);elsenum12=r.move;num13=p; / BInsertSortvoid print(int num) /打印排序方法比较表 int k=0; printf(nnnt_|n); printf(t|排序方法 | 关键字移动次数 |关键字比较次数 |n); printf(t_|n); printf(t|选择排序 | %5d | %5d |n,num0,num1); printf(t|直接插入排序 | %5d | %5d |n,num2,num3); printf(t|希尔排序 | %5d | %5d |n,num4,num5); printf(t|冒泡排序 | %5d | %5d |n,num6,num7); printf(t|快速排序 | %5d | %5d |n,num8,num9); printf(t|堆排序 | %5d | %5d |n,num10,num11); printf(t|折半插入排序 | %5d | %5d |n,num12,num13); printf(t_|n); printf(ntt n); printf(tt n); printf(tt 本组数据排序方法比较表 n); printf(tt n); printf(tt n); void main()char c;int select,length; SqList L;doprintf(请输入需排序的数据个数(小于200)：n);scanf(%d,&length); create(&L,length); printf(产生的随机序列为：n); visit(L); do printf(nn * 欢迎进入排序系统 *n ); printf( 1 选择排序 2.直接插入排序 3.希尔排序 4.冒泡排序 n ); printf( 5 快速排序 6 堆排序 7.折半插入排序 8.比较以上排序 n ); printf( 9.更改数据 0.退出 n ); printf( Please input number（0-7）n); scanf(%d,&select); switch (select) case 0:exit(0); case 1: select_sort(L); /选择排序 break; case 2: Zhijie(L); /直接插入排序 break; case 3: ShellSort(L,dlta,5);/希尔排序 break; case 4: Maopao(L); /冒泡排序 break; case 5: QuickSort(L); /快速排序 break;case 6: HeapSort ( L );/堆排序 printf(最终排序结果为:);visit(L); break;case 7: BInsertSort(L); /折半插入排序 break;case 8: /比较以上排序 flag=1; select_sort(L); Zhijie(L); ShellSort(L,dlta,4); Maopao(L); QuickSort(L); print(num); flag=0; break;case 9: /更改数据break; default:printf(输入错误！请重新输入.n); break; if(select=8) break;while(1);printf(是否更换数据重新进行排序？(y/n); getchar(); c=getchar(); if(c=n|c=N) break; system(cls);while(1);2.6. 测试情况：（设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计程序的功能。最后给出程序的测试情况，并分析运行结果。）2.6.1 测试数据的设计本程序的测试数据随机生成0到200之内的数据 图2.6.1 生成测试数据，进入排序系统2.6.2 程序运行结果分析 选择排序 直接插入排序希尔排序冒泡排序快速排序堆排序折半插入排序比较上述排序分别测试几组带排序序列个数不同的序列，排序比较如下：图为：5个数字排序比较结果图为：9个数字排序比较结果图为：20个数字排序比较结果图为：100个数字排序比较结果图为：200个数字排序比较结果分析：由以上运行结果可以看出排序算法的稳定性和其时间复杂度。例如，在选择排序中当关键字为450时，存在两个此信息，一个为D，另一个为A，排序前D在A的前面，排序后D在A的后面，故可知选择排序为不稳定的排序。由以上运行结果可分析出稳定排序有直接插入排序和冒泡排序，不稳定排序有选择排序，希尔排序和快速排序。由排序方法的比较表可知插入、冒泡排序的速度较慢。当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。快速排序是目前