数据结构课程设计报告 内部排序的算法设计与分析

1、郑州轻工业学院本科数据结构课程设计总结报告设计题目：常用的内部排序算法的分析和比较学生姓名：傅伟伟系 别：计算机科学与工程专 业：计算机科学与技术班 级：10-02班学 号：541007010207指导教师：卢 冰 、李 晔2012 年 6 月 21 日郑州轻工业学院课 程 设 计 任 务 书题目 常用内部排序算法分析与比较 专业、班级计算机科学与技术10-02班 学号 541007010207姓名 傅伟伟 主要内容：分析直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序等常用的内部排序算法的思想，通过交换次数以及比较次数来对这些算法进行比较。基本要求：通过给

2、定的记录数目及排序思想，设计相应的存储结构，程序之中要求可以实现完全随机，部分逆序等测试数据，来对每一种排序算法进行验证。其次还要设计出一个统计交换次数和比较次数的函数来进行计数。从待排序的记录数目、记录大小、关键字结构及其对稳定性的要求讨论出每种算法使用的环境。主要参考资料：严蔚敏 吴伟民 数据结构（c语言版） 清华大学出版社完 成 期 限： 2012/6/21 指导教师签名： 课程负责人签名： 2012年 6月 21 日一、设计题目：常用的内部排序的算法分析和比较二、运行环境：操作系统：windows软件：visual c+ 6.0 三、设计目的：针对常见的计算机内部排序算法，如直接插入排

3、序、希尔排序、冒泡排序、简单选择排序、堆排序、归并排序、基数排序等，通过是自己设计的程序，借助排序中交换次数和比较次数来比较这些算法的适用范围。四、程序设计的流程图：用户使用的提示性界面4 程序退出2 用户自行输入数据3全部逆序的随机数1完全随机数的操作八种内部排序的各个操作显示操作之后八种算法的比较五、算法分析：1、简单选择排序：简单选择排序的每一趟都是从待排的数据元素中选出一个最小（最大）的一个元素，顺序的放在已经排好的数列的最后，直到全部待排序的数据元素排序完毕。2、直接插入排序：这是一种最简单的排序方法，它的基本操作时将一个记录插入到一个已经排好序的有序表中，从而得到一个新的记录数增1

4、的有序表。其效率：从空间的角度来看待，它只需要一个辅助的空间，从时间上来看的话，排序的基本操作是比较两个关键字的大小和移动（本程序中将移动和交换看成一样）记录。在整个排序的过程中，当待排序列中的关键字非递减有序的话，那么比较次数最小n-1，且不需要移动，当待排序列逆序时，比较次数达到最大（n+2）（n-1）/2，记录的移动的次数也达到最大值（n+4）（n-1）/2。取平均值得时候直接插入排序的时间复杂度o(n)。排序是稳定的。3、冒泡排序：这种排序的比较基本思想就是两两比较待排序的数据元素的大小，发现两个数据元素的次序相反时候，就进行交换，知道没有反序的数据为止。冒泡排序是一次的比较找出最小（

5、最大）值，然后将其放置序列的最后一个位置，再将剩下的从第一个位置开始至n-i的位置进行重复的操作。4、希尔排序：属于一种插入排序类的方法，先将整个待排序记录分成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对整体记录进行一次直接插入排序。实质上就是一个将序列分块化，然后再对各个块进行排序，化整为零的操作，最后待序列差不多有序的时候进行一次化零为整操作，实现最后一次的插入排序。5、快速选择排序：这个是对冒泡排序的一种改进。它的基本思想就是，在当前无序区r1.h中任取一个数据元素作为比较的基准(不妨记为x)，用此基准将当前无序区划分为左右两个较小的无序区：r1.i-1和ri

6、+1.h，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准x则位于最终排序的位置上，即r1.i-1x.keyri+1.h(1ih)，当r1.i-1和ri+1.h均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。6、堆排序：堆排序实质上就是具备有如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。它只需要记录一个大小的辅助空间，每个待排序的纪录仅占有一个存储空间。一般对记录数较少的文件并不值得提倡，但是对n较大的文件还是很有效的，因为其运行时间主要是小号在建初始堆和调整建新堆时进行的反复的筛

7、选上的。7、归并排序：归并排序实质上就是将两个或者两个以上的有序表组合成一个新的有序表。8、基数排序：基数排序是一种借助多关键字排序思想对单逻辑关键字进行的排序方法。中间是涉及到一个重复的分配再收集的操作。具体在本程序中：根据数项个位上的值，将所有的数据项分为10组；然后对这10组数据重新排列，把所有的以0结尾的排在最前，当然需要保证稳定性，然后依次类推以2、39开头，接着进行第二趟的排序，由于本程序中用到的数字是1000以内的实例，那么需要有第三趟的操作，最后就是收集，收集完输出的时候是将一个关键字按照百位十位个位一次输出的。9、排序算法的时间空间复杂度：排序方法最坏情况平均情况稳定性空间复

8、杂简单选择o(n)o(n)不稳定o(1)直接插入o(n)o(n)稳定o(1)冒 泡o(n)o(nlogn)稳定o(1)希尔排序-o(n1.3)不稳定o(1)快速选择o(nlogn)o(n)不稳定o(nlogn)堆排序o(nlogn)o(nlogn)不稳定o(1)归并排序o(nlogn)o(nlogn)不稳定o(n)基数排序o(d(n+rd)o(d(n+rd)稳定o(rd)六、程序调试：1、本程序实例使用的是visual c+ 6.0开发，运行本程序之后出现人机交互的界面如下所示：2、选择的是第一步操作之后对程序进行随机数据的操作，本次输入的是随机生成23个数据，运行之后会出现相应的系统给出的原

9、来的随机数，以及运行排序之后的全部数据，在此之后给出了各个排序表的比较次数和交换次数的表格，以便于对各个排序的方法得到分析性能：要求系统产生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、执行第三步操作，系统生成随机的逆序的一组

10、数据：要求系统随机产生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、25、为了确保系统测试的稳定性，本系统中提供的一组数据保证在50个以内，下面是用户要求系统输出50个以上时候系统给出反应6、程序的安全退出：一些说明，本程序的健壮性还不是很好，比如说在人机交互的主界面以及数据的录入的时候，用户需要小心的正确输入阿拉伯数字。七、个人收获心得：本次课程设计是在最后一

11、次的实验基础之上，即最后一段时间的学习数据结构（c语言版）中的内部排序算法的基础上，通过对各个内部排序的算法的分析，比较，然后再运行在系统上面。计算机算法的设计不是一个小的功夫就能够满足的，在这次的课程设计中，自己可以能够深入的了解到每一个排序的每一步具体的操作，真正的领悟每一个算法本质的排序思想，为自己以后的计算机学习奠定了坚实的基础。当然本次的课程设计，在最初的算法写作的时候并没有遇到什么较为复杂的错误，后续的程序界面搭建时候，由于忽略掉了全局变量被修改的这一个现象，使得自己花了一些功夫在调试程序。问题不麻烦，相对来说，这种错误真的是常见的但却也是最应该避免的错误，但愿这一次的错误，可以为

12、自己的后期学习中添砖加瓦。本次所选的课程题目是关于内部排序的算法分析与比较，计算机内部排序的算法也不仅仅是在本程序中调试的那八种排序，当然除了内部排序还有外部的排序，在一个内部排序的时候，自己花的这些功夫，随只是勉强的实现了功能，但是计算机的算法还是很深，需要自己引起足够的重视。想成为一名好的计算机编程员，代码的重复需要自己下很大的功夫。计算机语言的学习，计算机算法的衍生可谓都是博大精深，必须要施之与论持久战的方法，化整为零，溶入希尔算法的缩小增量的思想，定会到达一个“基本有序”的地步，最终实现一步合零位整一步插入，相信计算机可以走得持久。最后，对传授自己数据结构知识的卢冰卢老师说一声谢谢！八

13、、附录（本程序的源代码及其注释）：#include#include#include#define maxsize 50typedef int keytype;#define maxnum 100typedef structkeytype key;redtype;redtype rmaxnum;/定义结构体数组typedef structredtype rmaxsize+1;/r0闲置、或者用作哨兵单元int length;sqlist;/顺序表的类型sqlist l,l0,l1,l2,l3,l4,l5,l6,l7;typedef sqlist headtype;#define radix 10

14、/关键字的基数#define max 8/关键字项数的最大值#define max_space 10000typedef int keystype;typedef structkeystype keysmax;/关键字int next;slcell;/静态链表的节点类型typedef struct slcell rlmax_space; /静态链表的可利用空间 int keynum; /记录当前的关键字个数 int recnum; /静态链表的当前长度sllist;/静态链表的类型typedef int arrtyperadix;int compare8;/用来记录比较的次数int chang

15、e8;/用来比较交换的次数 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.ri);void shuchu(sqlist &l)/输出顺序表中的元素int i=1;printf(该顺序存储中的数据元素为：);for(;il.length;i+)printf(%d ,l.ri);printf(%dnn,l.ri);/=简单选择排序=int selectminkey(

16、sqlist &l,int i)/在l.ri到length中找到最小值的记录int k;compare0 += l.length-i;for(k=i;i=l.length;i+)compare0+;/记录的是i与length的比较compare0+;/下面的选择语句中的比较if(l.ri.keyl.rk.key)k=i;change0+;return k;void selectsort(sqlist &l)/顺序表的简单选择排序操作int i,j,temp;for(i=1;il.length;+i)compare0+;/记录的是i与length的比较j = selectminkey(l,i);

17、compare0+;if(i!=j)temp=l.ri.key;l.ri.key=l.rj.key;l.rj.key=temp;change0+=3;/交换次数加3/=直接插入排序=void insersort(sqlist &l)/直接插入排序int j;for(int i = 2 ; i=l.length; +i) compare1+;/i与lengthcompare1+;/记录的是下面选择语句的比较if(l.ri.key0;j-)compare1+;/for循环中的比较compare1+;/记录的是下面括号中要进行的比较if(l.r0.key=l.rj.key) break;l.rj+1

18、 = l.rj;/记录后移change1+;/位置后移，交换次数加1l.rj+1 = l.r0;/插入到正确位置change1+;/=冒泡排序=void bubblesort(sqlist &l)/冒泡排序int i,j,temp;for(i=1;i=l.length;i+)compare2+;/记录上面的for循环for(j=1;jl.rj+1.key)temp = l.rj.key;l.rj.key=l.rj+1.key;l.rj+1.key = temp;change2+=3;/=希尔排序=void shellinsert(sqlist &l, int dk)/以增量dk做一次希尔插入排

19、序/前后记录的增量式dk，r0作为的是一个暂存单元，而不是哨兵，当j=0时候，表示插入位置找到int i,j;for(i = dk+1; i=l.length; +i)compare3+;/上面的for循环条件比较compare3+;/下面的选择比较if(l.ri.key0; j-=dk)compare3+;/for循环compare3+;/下面的比较if(l.r0.keyl.rj.key) break;l.rj+dk = l.rj;/记录后移，查找插入位置change3+;l.rj+dk = l.r0;/插入change3+;void shellsort(sqlist &l)/按增量序列对书

20、序表l做希尔排序int k;int dlta = 5,3,2,1;int t = 4;for(k=0;kt;+k)compare3+;/for循环shellinsert(l,dltak);/=快速排序=int partition(sqlist &l,int low ,int high)/交换顺序表l中字表的rlow hingh的记录，是枢轴记录到位，并返回所在的位置，此时在它之前的记录均不大于它keytype pivotkey;l.r0 = l.rlow;pivotkey = l.rlow.key;change4+;while(lowhigh)compare4+;/记录的是上面的while循环

21、的条件判断compare4+;/记录下面的循环增加的终止while(low=pivotkey) -high;compare4+;l.rlow = l.rhigh;change4+;compare4+;/记录下面的循环增加的终止while(lowhigh&l.rlow.key=pivotkey) +low;compare4+;l.rhigh = l.rlow;change4+;l.rlow = l.r0;change4+;return low;void qsort(sqlist &l,int low, int high)/对顺序表l中的子序列做快速排序int pivotloc;if(lowhig

22、h)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.rs;for(j = 2*s; j=m; j*=2)compare5+;/for循环的调教判断if(jm&(compare5+)&(h.rj.key h.rj.key ) c

23、ompare5+;break;h.rs = h.rj; s = j;change5+;h.rs = rc;change5+;/插入void headsort(headtype &h)/对顺序表进行堆排序redtype temp;/中间变量用于保存数值，for(int i = h.length/2 ; i0; -i)compare5+;headadjust(h,i,h.length);/后续的调整for(i=h.length;i1;-i)compare5+;temp=h.r1; h.r1=h.ri; h.ri=temp;/最后的一次记录相互交换change5+=3;headadjust(h,1,

24、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+)compare6+=2;/for循环中的两个条件判断if(sri.keysrj.key) change6+;trk = sri+;else change6+;trk =srj+;while(i=m) compare6+;trk+ = sri+;change6+;while(j=n) compare6+;trk+ = srj+;change6+;void msort(redtype sr,re

25、dtype tr1,int s,int t)int m;redtype tr2maxsize+1;if(s=t) compare6+;/条件的判断tr1s=srs;change6+;elsecompare6+;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+

26、)compare7+;ri.key=l.ri.key;lk.recnum = l.length;lk.keynum = 3;/设置为三位数的比较for(i=1;i=lk.recnum;i+) /将给定的数字按照三位数的格式进行拆分。百位、十位、个位 compare7+; j=lk.keynum-1;change7+=3;/下面的三个式子lk.rli.keysj-=ri.key/100;/获取的是最高位的，本示例中的是百位上的数字lk.rli.keysj-=(ri.key%100)/10;/获取的是十位上的数字lk.rli.keysj=ri.key%10;/获取的是个位上的数值 for(i=0;

27、ilk.recnum;+i) /将所有的链表用链表连接起来，构成二维的链表 lk.rli.next=i+1; lk.rllk.recnum.next=0;/链表循环 change7+;void distribute(slcell (&r)max_space,int i,arrtype &f,arrtype &e) /第i趟分配int j,p;for(j=0;jradix;j+) compare7+;fj =0;/各子表初始化为空表for(p=r0.next; p; p=rp.next)j = rp.keysi;change7+;if(!fj) fj=p;change7+;else rej.ne

28、xt = p;change7+;ej =p;change7+;void collect(slcell (&r)max_space,int i,arrtype f,arrtype e) /基数排序 int j,t; for(j=0;!fj;j+);/找第一个非空的子表r0.next=fj;/r0的next指向第一个非空子表的第一个结点 t=ej;change7+=2; while (jradix-1) compare7+; for(j+;jradix-1&!fj;j+); compare7+; if (fj) rt.next=fj; t=ej; change7+=2; rt.next=0; ch

29、ange7+; void radixsort(sllist &l)arrtype f,e; for(int i=0;il.recnum;+i) compare7+;l.rli.next = i+1;change7+;l.rll.recnum.next = 0;/将l改造为一个静态的链表change7+;for(i=0;i=0;j-) /控制输出一个数据compare7+; printf(%d,l.rli.keysj); printf( ); printf(n); /=链表复制操作=void copy(sqlist &l)l0.length=l.length;l1.length=l.length

30、;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.ri.key=l.ri.key;l2.ri.key=l.ri.key;l3.ri.key=l.ri.key;l4.ri.key=l.ri.key;l5.ri.key=l.ri.key;l6.ri.key=l.ri.key;l7.ri.key=l.ri.key;l0.ri.key=l.ri.key;/=主菜单=

31、void menu()printf(t=tn);printf(t=计算机科学与技术10-02班=傅伟伟=541007010207=tn);printf(t=欢迎使用测试内部排序界面=tn);printf(t=tn);printf(t请选择你要进行的操作tn);printf(tcase 1: 产生完全随机的数据再进行排序tn);printf(tcase 2： 自行输入一些数据再实现排序操作tn);printf(tcase 3： 产生的是一组随机的但是是逆序递增的一组tn);printf(tcase 0: 退出程序tn);printf(t为了测试的正常进行，请选择正确的输入形式tn);/=输出比较

32、次数和交换次数的表格=void table()printf(ttn);printf(t=算法名称=比较次数=交换次数=tn);printf(t1简单选择排序 t%dt %d tn,compare0,change0);printf(t2直接插入排序 t%dt %d tn,compare1,change1);printf(t3 冒泡排序 t%dt %d tn,compare2,change2);printf(t4 希尔排序 t%dt %d tn,compare3,change3);printf(t5快速选择排序 t%dt %d tn,compare4,change4);printf(t6 堆 排

33、序 t%dt %d tn,compare5,change5);printf(t7 归并排序 t%dt %d tn,compare6,change6);printf(t8 基数排序 t%dt %d tn,compare7,change7);printf(ttn);/=用于系统产生随机数的情况=void random(sqlist &l)sllist lk;for(int i =0;i50)printf(请将输入的个数限制在50之内，请重新输入!n);goto a;for(i=1;i=l.length;i+) l.ri.key =1+(int )(1000.0*rand()/(rand_max+1

34、.0);/随机生成1000以内的整数printf(排序之前的随机生成的%d个数是:n,l.length);for(i=1;i=l.length;i+) printf(%d ,l.ri.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);/