数据结构课程设计报告各种排序算法性能比较

1、EAST CHINA INSTITUTE OF TECHNOLOGY课程设计报告课程设计题目：各种排序算法性能比较学生姓名：学 号：专 业：信息管理与信息系统班级：指导教师：2012年06月23日目录CONTENTS一、课程设计目的 2二、课程设计题目概述 2三、数据定义 2四、各种排序的基本原理及时间复杂度分析 3五、程序流程图 6六、程序源代码 6七、程序运行与测试 15八、实验体会九、参考文献、 课 程设计目的课程设计为学生提供了一个既动手又动脑， 独立实践的机会， 将课本上的理 论知识和实际有机的结合起来， 锻炼学生的分析解决实际问题的能力。 提高学生 适应实际，实践编程的能力。二、课

2、程设计题目概述排序的方法很多， 但是就其全面性能而言， 很难提出一种被认为是最好的方 法，每一种方法都有各自的优缺点， 适合在不同的环境下使用。 如果排序中依据 的不同原则对内部排序方法进行分类， 则大致可分为直接插入排序、 直接选择排 序、起泡排序、Shell排序、快速排序、堆排序等六类排序算法。本实验是对直接插入排序、直接选择排序、起泡排序、Shell排序、快速排序、 堆排序这几种内部排序算法进行比较， 用不同的测试数据做测试比较。 比较的指 标为关键字的比较次数和关键字的移动次数。 最后用图表数据汇总， 以便对这些 内部排序算法进行性能分析。三、数据定义输入数据： 由于大多数排序算法的时

3、间开销主要是关键字之间的比较和记录的移动， 算 法的执行时间不仅依赖于问题的规模， 还取决于输入实例中数据的状态。 所以对 于输入数据， 我们采用由用户输入记录的个数 （以关键字的数目分别为 20，100， 500 为例），测试数据由随机数产生器生成。输出数据：产生的随机数分别用直接插入排序；直接选择排序；起泡排序；Shell排序；快速排序；堆排序这些排序方法进行排序，输出关键字的比较次数和移动次数。四、各种排序的基本原理及时间复杂度分析1、直接插入排序( InsertSort)1.1 、基本原理：假设待排序的n个记录RO, R1,，Rn顺序存放在数组中，直接插入法在 插入记录Ri(i=1 ,

4、2,，n-1)时，记录被划分为两个区间R0,Ri-1和Ri+1,Rn-1, 其中，前一个子区间已经排好序， 后一个子区间是当前未排序的部分， 将关键码 Ki与Ki-1Ki-2，K0依次比较，找出应该插入的位置，将记录 Ri插，然后 将剩下的 i-1 个元素按关键词大小依次插入该有序序列， 没插入一个元素后依然 保持该序列有序， 经过 i-1 趟排序后即成为有序序列。 每次将一个待排序的记录， 按其关键字大小插入到前面已经排好序的子文件中的适当位置， 直到全部记录插 入完成为止。1.2 、时间复杂度分析：直接插入排序算法必须进行 n-1 趟。最好情况下，即初始序列有序，执行 n-1 趟，但每一趟

5、只比较一次，移动元素两次，总的比较次数是 (n-1) ，移动元 素次数是2(n-1)。因此最好情况下的时间复杂度就是 0(n)。最坏情况(非递增) 下，最多比较 i 次，因此需要的比较次数是：所以，时间复杂度为O(n2)。2、直接选择排序( SelectSort)2.1 、基本原理：待排序的一组数据元素中， 选出最小的一个数据元素与第一个位置的数据元 素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换， 循环到只剩下最后一个数据元素为止， 依次类推直到所有记录。 第一趟第 n 个记 录中找出关键码最小的记录与第 n个记录交换；第二趟，从第二个记录开始的， 2 -1 个记录中再

6、选出关键码最小的记录与第二个记录交换； 如此，第 i 趟，则从 第 i 个记录开始的 n - i + l 个记录中选出关键码最小的记录与第 i 个记录交换， 直到所有记录排好序。2.2、时间复杂度分析：3 / 21该算法运行时间与元素的初始排列无关。 不论初始排列如何， 该算法都必须 执行 n-1 趟，每趟执行 n-i-1 次关键字的比较，这样总的比较次数为：所以，简 单选择排序的最好、最坏和平均情况的时间复杂度都为O(n2) 。3、冒泡排序( BubbleSort)3.1 、基本原理在每一趟冒泡排序中，依次比较相邻的两个关键字大小，若为反序咋交换。 经过一趟起泡后，关键词大的必须移到最后。按

7、照这种方式进行第一趟在序列 ( I0In-1 )中从前往后进行两个相邻元素的比较，若后者小，则交换，比 较 n-1 次；第一趟排序结束，最大元素被交换到 In-1 中，下一趟只需在子序 列( I0In-2)中进行；如果在某一趟排序中未交换元素，则不再进行下一趟排序。将被排序的记录数组 J1n垂直排列，每个记录Ji看作是重量为 Ji.key 的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上 "飘浮"。如此反复进行，直到最后任 何两个气泡都是轻者在上，重者在下为止，最后可完成 。3.2 、时间复杂度分析当原始数据正向有序时，

8、冒泡排序出现最好情况。 此时，只需进行一趟排序， 作n-1次关键字比较，因此最好情况下的时间复杂度是0(n)。当原始数据反向有序时，冒泡排序出现最坏情况。此时，需进行n-1趟排序，第i趟作(n-i)次关键字间的比较，并且需执行 (n-i) 次元素交换，所以，比较次数为：因此 , 最坏 情况下的时间复杂度为 0(n2) 4、Shell 排序( ShellSort )4.1 、基本原理Shell 排序又称缩小增量排序 ,Shell 排序法是以创建者 Donald Shell 的名 字命名的 .Shell 排序法是对相邻指定距离 (称为间隔 ) 的元素进行比较 ,已知到使 用当前间隔进行比较的元素都

9、按顺序排序为止 .Shell 把间隔缩小一半 , 然后继续 处理, 当间隔最终变为 1 ,并且不再出现变化时 ,Shell 排序也就完成了其处理过 程.先取一个整数d1<n,把全部记录分成di个组，所有距离为di倍数的记录放 在一组中，先在各组内排序； 然后去 d2<d1 重复上诉分组和排序工作；直至所取 的增量dt=1(dt<dt- l<<d2<d1)，即所有记录放在同一组中进行直接插入，直 到 dt=i ，即所有记录放在一组中为止。4.2 、时间复杂度分析希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时 候，步长最大，所以插入排序的元素个

10、数很少，速度很快；当元素基本有序了， 步长很小，插入排序对于有序的序列效率很高。所以， 希尔排序的时间复杂度会2比 o(n2) 好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改 变相同元素的相对顺序， 但在不同的插入排序过程中， 相同的元素可能在各自的 插入排序中移动，最后其稳定性就会被打乱， 所以 shell 排序是不稳定的。所以 希尔排序是不稳定的，其时间复杂度为 o(n2) 。5、快速排序( QuickSort)5.1 基本原理首先我们选择一个中间值 middle (程序中我们可使用数组中间值)，把比 中问值小的放在其左边，比中问值大的放在其右边。由于这个排序算法较复杂，

11、我们先给出其进行一次排序的程序框架。在待排序的个记录中任意取一个记录 (通常取第一个记录) 为区分标准，把所有小于该排序的记录移到左边，把所有 大于该排序码的记录移到右边，中级放所选记录，为一趟快速排序。 然后对前后 两个子序列分别重新上述过程， 直到所有记录都排好序。 对任意给定的序列中某 个元素，经过一趟排序后，将原序列分割成两个子序列(Rp(°),Rp(i),Rp(i )和(Rp(s+1) ,Rp(s+2),Rp(n-1)，其中前一个子序列中的所有元素的关键词均小于或等于 该元素的关键词值 $s),后一个子序列中元素的关键词均大于或等于Kp(s)。称该元素&s)为分割元

12、素，子序列(Rp(0),Rp(i),Rp(s-i)为其低端序列，(Rp(o),Rp(i),Rp(s-i)为其咼端序列。很明显，以后只需对低端和咼端序列分别进 行快速排序， 直到子序列为空或只有一个元素时结束， 最后得到有序序列。 总之， 每趟使表的第一个元素放在适当位置， 将表两分，再对子表进行同样的递归划分， 直至划分的子表长度为 1。5.2 、时间复杂度分析如果每一次分划操作后， 左、右两个子序列的长度基本相等，则快速排序的 效率最咼，其最好情况时间复杂度为O(nlog 2n) ；反之，如果每次分划操作所产生的两个子序列，其中之一为空序列，此时，快速排序效率最低，其最坏情况时 间复杂度为

13、O(n2) 。如果选择左边第一个元素为主元，则快速排序的最坏情况发 生在原始序列正向有序或反向有序时。快速排序的平均情况时间复杂度为 O(nlog 2n) 。6、堆排序（ Heapsort ）6.1 、基本原理堆排序思想很简单， 就是每次把关键词调整为堆， 取出堆顶元素与堆中最后 一个元素交换，同时令堆的大小减一， 把剩余的一些元素重新调整为堆， 重复此 过程，知道堆中只剩下一个元素，n个关键字序列K1,K2,K3, 称为堆，当且仅当该序列满足如下性质（简称为堆性质）：（1 ） Ki<=K2i 且 Ki<=K2i+1或（2） Kiv=K2i且Ki>=K2i+1.。若将此序列所

14、存储的向量 R1n看作是一棵 完全二叉树的存储结构， 则堆实质上是满足如下性质的完全二叉树： 树中非叶子 结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。根结 点（亦称为堆顶） 的关键字是堆里所有结点关键字中最小者的堆称为小根堆。 根 结点（亦称为堆顶）的关键字是堆里所有结点关键字中的最大者，称为大根堆。注意：堆中任一子树亦是堆。以上讨论的实际上是二叉堆，类似的可以定义K叉堆6.2 时间复杂度分析堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成， 它们均是通过调用 Heapify 实现的。堆排序的最坏时间复杂度为 O（nlogn） 。堆 排序的平均性能较接近于

15、最坏性能。 由于建初始堆所需的比较次数较多， 所以堆 排序不适宜于记录数较少的文件。 堆排序是不稳定的， 算法时间复杂度 O（nlogn） 。五、程序流程图六、程序源代码#in clude<stdio.h>#in clude<stdlib.h> typedef structint key; /* 关键字 */RecordNode; /*排序节点的类型*/typedef structRecordNode *record;int n; /* 排序对象的大小 */SortObject; /* 排序节点的类型 */void InsertSort(SortObject *p,un

16、signed long *compare,unsigned long *exchange)int i,j;RecordNode temp;SortObject *pvector;if(pvector=(SortObject *)malloc(sizeof(SortObject)=NULL)printf("OverFollow!");getchar();exit(1);for(i=0;i<p->n;i+)/* 复制数组 */pvector->recordi=p->recordi;pvector->n=p->n;*compare=0;*exc

17、hange=0;for(i=1;i<pvector->n;i+) temp=pvector->recordi;(*exchange)+;j=i-1;while(temp.key<pvector->recordj.key)&&(j>=0) (*compare)+;(*exchange)+;pvector->recordj+1=pvector->recordj;j-;if(j!=(i-1) pvector->recordj+1=temp;(*exchange)+;free(pvector);void SelectSort(Sor

18、tObject *p,unsigned long *compare,unsigned long *exchange) int i,j,k;RecordNode temp;SortObject *pvector;if(pvector=(SortObject *)malloc(sizeof(SortObject)=NULL)printf("OverFollow!");getchar();exit(1);for(i=0;i<p->n;i+)/* 复制数组 */pvector->recordi=p->recordi;pvector->n=p->n

19、;*compare=0;*exchange=0;for(i=0;i<pvector->n-1;i+) k=i;for(j=i+1;j<pvector->n;j+) (*compare)+;if(pvector->recordj.key<pvector->recordk.key)k=j;if(k!=i) temp=pvector->recordi;pvector->recordi=pvector->recordk;pvector->recordk=temp;( *exchange)+=3;free(pvector);void Bu

20、bbleSort(SortObject *p,unsigned long *compare,unsigned long *exchange) int i,j,noswap;RecordNode temp;SortObject *pvector;if(pvector=(SortObject *)malloc(sizeof(SortObject)=NULL) printf("OverFollow!");getchar();exit(1);for(i=0;i<p->n;i+)/* 复制数组 */pvector->recordi=p->recordi;pve

21、ctor->n=p->n;*compare=0;*exchange=0;for(i=0;i<pvector->n-1;i+) noswap=1;for(j=0;j<pvector->n-i-1;j+) (*compare)+;if(pvector->recordj+1.key<pvector->recordj.key) temp=pvector->recordj;pvector->recordj=pvector->recordj+1;pvector->recordj+1=temp;(*exchange)+=3;nos

22、wap=0;if(noswap) break;free(pvector);void ShellSort(SortObject *p,int d,unsigned long *compare,unsigned long *exchange) int i,j,increment;RecordNode temp;SortObject *pvector;if(pvector=(SortObject*)malloc(sizeof(SortObject)=NULL) printf("OverFollow!");getchar();exit(1);for(i=0;i<p->n

23、;i+)/* 复制数组 */pvector->recordi=p->recordi;pvector->n=p->n;*compare=0;*exchange=0;for(increment=d;increment>0;increment/=2)for(i=increment;i<pvector->n;i+) temp=pvector->recordi;(*exchange)+;j=i-increment;while(j>=0&&temp.key<pvector->recordj.key) (*compare)+;

24、pvector->recordj+increment=pvector->recordj;(*exchange)+;j-=increment;pvector->recordj+increment=temp;(*exchange)+;free(pvector);longVoid SiftHeap(SortObject *pvector,int size,int p,unsigned long *compare,unsigned *exchange)RecordNode temp;int i,child;temp=pvector->recordp;(*exchange)+;i

25、=p;child=2*i+1;while(child<size)if(child<size-1&&pvector->recordchild.key<pvector->recordchild+1.key)(*compare) +;child+;if(temp.key<pvector->recordchild.key)(*compare)+;pvector->recordi=pvector->recordchild;(*exchange)+;i=child;child=2*i+1;else break;pvector->r

26、ecordi=temp;(*exchange)+;void HeapSort(SortObject *p,unsigned long *compare,unsigned long *exchange) int i,n;RecordNode temp;SortObject *pvector;if(pvector=(SortObject *)malloc(sizeof(SortObject)=NULL) printf("OverFollow!");getchar();exit(1);for(i=0;i<p->n;i+)pvector->recordi=p-&g

27、t;recordi;pvector->n=p->n;*compare=0;*exchange=0;n=pvector->n;for(i=n/2-1;i>=0;i-)SiftHeap(pvector,n,i,compare,exchange); temp=pvector->record0;pvector->record0=pvector->recordi;pvector->recordi=temp;(*exchange)+=3;SiftHeap(pvector,i,0,compare,exchange);free(pvector);void Qui

28、ckSort(SortObject *pvector,int left,int right,unsigned long*compare,unsigned long *exchange) int i,j;RecordNode temp;if(left>=right)return;i=left;j=right;temp=pvector->recordi;(*exchange)+;while(i!=j) while(pvector->recordj.key>=temp.key)&&(j>i) (*compare)+;j-;if(i<j)pvecto

29、r->recordi+=pvector->recordj;(*exchange)+;while(pvector->recordi.key<=temp.key)&&(j>i)(*compare)+;i+;if(i<j)pvector->recordj-=pvector->recordi;(*exchange)+;pvector->recordi=temp;(*exchange)+;QuickSort(pvector,left,i-1,compare,exchange);QuickSort(pvector,i+1,right,c

30、ompare,exchange);void SortMethod(void) int i,j;unsigned long num312=0;SortObject *pvector=(SortObject *)malloc(sizeof(SortObject);int random;randomize();for(j=0;j<3;j+) for(i=0;i<MAXSORTNUMj;i+)pvector->recordi.key=random(5000);pvector->n=MAXSORTNUMj;InsertSort(pvector,&numj0,&nu

31、mj1);SelectSort(pvector,&numj2,&numj3);BubbleSort(pvector,&numj4,&numj5);ShellSort(pvector,4,&numj6,&numj7);Heapsort(pvector,&numj8,&numj9);QuickSort(pvector,0,MAXSORTNUMj-1,&numj10,&numj11);printf("nSort Method Compare As Follows:");for(j=0;j<3;j

32、+)printf("nnWhen The max num is %d,the result is:n",MAXSORTNUMj);printf("1.InsertSort Method:Compared->%-7ldExchanged->%-7ldn",numj0,numj1);printf("2.SelectSort Method:Compared->%-7ldExchanged->%-7ldn",numj2,numj3);printf("3.BubbleSort Method:Compared-&

33、gt;%-7ld Exchanged->%-7ldn",numj4,numj5);printf("4.ShellSort Method:Compared->%-7ldExchanged->%-7ldn",numj6,numj7);printf("5.HeapSort Method:Compared->%-7ldExchanged->%-7ldn",numj8,numj9);printf("6.QuickSortMethod:Compared->%-7ldExchanged->%-7ldn&qu

34、ot;,numj10,numj11);if(j!=2)printf("Press Enter to continue.n");sgetchar();void mai n()SortMethod();七、程序运行与测试C: .'i'll1132 u->d. -eXfSorjt Method Conpar« Rs Follows:Mhcr Th吐 lux 1.InsertSort 2.SelectScrt p.BubbleScrt 4+SliellSQrl 5.HeapSort b. (Quicksort Press Enternuu i.s 2

35、0,the result isHcthad:Compared一>100Method:Compared >190 Nethcd：CoMpctrecl ->167 Mclhod; Conoctred一>52 Hethod:Corapnred->6H Hethcd:Compared->17 to Coniinue.Exchanged >/i8 Exchanged- >300 匚xchancd一一>15S Exclianaed一>48 Fxchnnjed一一>3b图7.1数据长度为20时算法运行界面When Tlie radx nun is 100, the reuul I is :1.InsertSort ? SclcctSort3.BubhleSort 4.Shell Sort !i. HeripSort 右.Qu:irkSor t Press EnterMelliod: Comwred>24 /8 Hc!thod Co»p