数据结构排序算法的分析和比较(包涵源代码)

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

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

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

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

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

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

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

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

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

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

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

12、快速排序的最坏情况发生在原始序列正向有序或反向有序时。快速排序的平均情况时间复杂度为 0(nlog2n)。6、堆排序( Heapsort )6.1 、基本原理堆排序思想很简单，就是每次把关键词调整为堆，取出堆顶元素与堆中最后一个元素交换， 同时令堆的大小减一， 把剩余的一些元素重新调整为堆， 重复此过程， 知道堆中只剩下一个 元素，n个关键字序列 K1,K2,K3,称为堆，当且仅当该序列满足如下性质(简称为堆性质)：(1)Ki<=K2i且Ki<=K2i+1或(2) Ki<=K2i且Ki>=K2i+1.。若将此序列所存储的向量R1n看作是一棵完全二叉树的存储结构，则堆实质

13、上是满足如下性质的完全二叉树：树中非叶子结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。根结点(亦称 为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。根结点(亦称为堆顶) 的关键字是堆里所有结点关键字中的最大者，称为大根堆。注意：堆中任一子树亦是堆。以上讨论的实际上是二叉堆，类似的可以定义K叉堆6.2 时间复杂度分析堆排序的时间， 主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。堆排序的最坏时间复杂度为0(nlogn)。堆排序的平均性能较接近于最坏性能。 由于建初始堆所需的比较次数较多， 所以堆排序不适宜于记录数较少的文件

14、。 堆排序 是不稳定的，算法时间复杂度 0(nlogn)。四、程序流程图循环20次p产生1组随机数a将隨机数保存在数组中*快連Shell排字选择排序仪排序,排序直接 插入 排序*起泡卜记录关键字的比技次数和移功次数“输出关謹宇的比较次数s移动次数的平均值卡L_五、程序源代码#in clude<stdio.h>#in clude<stdlib.h>typedefstructint key; /* 关键字 */RecordNode; /*排序节点的类型*/typedefstructRecordNode *record;int n; /*排序对象的大小*/SortObject

15、; /*排序节点的类型*/voidI nsertSort(SortObject *p, un sig ned long *compare ,un sig ned long *excha nge) in ti,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->rec

16、ordi=p->recordi;pvector->n=p->n;*compare=0;*exchange=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->

17、recordj+1=temp; (*exchange)+; free(pvector);voidSelectSort(SortObject *p,unsigned long *compare,unsigned long *exchange) inti,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+)/* 复

18、制数组 */ pvector->recordi=p->recordi;pvector->n=p->n; *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->reco

19、rdk; pvector->recordk=temp;( *exchange)+=3; free(pvector);voidBubbleSort(SortObject *p,unsigned long *compare,unsigned long *exchange) inti,j,noswap;RecordNode temp;SortObject *pvector;if(pvector=(SortObject *)malloc(sizeof(SortObject)=NULL) printf("OverFollow!"); getchar();exit(1);for(

20、i=0;i<p->n;i+)/* 复制数组 */ pvector->recordi=p->recordi; pvector->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->re

21、cordj=pvector->recordj+1; pvector->recordj+1=temp;(*exchange)+=3; noswap=0; if(noswap) break; free(pvector);voidShellSort(SortObject *p,intd,unsigned long *compare,unsigned long *exchange) inti,j,increment;RecordNode temp; SortObject *pvector;if(pvector=(SortObject*)malloc(sizeof(SortObject)=N

22、ULL) printf("OverFollow!");getchar();exit(1);for(i=0;i<p->n;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-inc

23、rement;while(j>=0&&temp.key<pvector->recordj.key) (*compare)+; pvector->recordj+increment=pvector->recordj;(*exchange)+; j-=increment; pvector->recordj+increment=temp;(*exchange)+; free(pvector);Void SiftHeap(SortObject *pvector,intsize,intp,unsigned long *compare,unsigned

24、long *exchange) RecordNode temp;inti,child; temp=pvector->recordp;(*exchange)+;i=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->r

25、ecordi=pvector->recordchild; (*exchange)+;i=child; child=2*i+1;else break; pvector->recordi=temp;(*exchange)+;voidHeapSort(SortObject *p,unsigned long *compare,unsigned long *exchange) inti,n;RecordNode temp; SortObject *pvector; if(pvector=(SortObject *)malloc(sizeof(SortObject)=NULL) printf(

26、"OverFollow!");getchar();exit(1); for(i=0;i<p->n;i+) pvector->recordi=p->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; pvecto

27、r->recordi=temp;(*exchange)+=3; SiftHeap(pvector,i,0,compare,exchange);free(pvector);longvoidQuickSort(SortObject *pvector,intleft,intright,unsigned long*compare,unsigned *exchange) inti,j;RecordNode temp;if(left>=right)return;i=left;j=right;temp=pvector->recordi;(*exchange)+; while(i!=j) w

28、hile(pvector->recordj.key>=temp.key)&&(j>i) (*compare)+;j-;if(i<j) pvector->recordi+=pvector->recordj; (*exchange)+; while(pvector->recordi.key<=temp.key)&&(j>i)(*compare)+;i+;if(i<j)pvector->recordj-=pvector->recordi;(*exchange)+;pvector->recor

29、di=temp; (*exchange)+;QuickSort(pvector,left,i-1,compare,exchange); QuickSort(pvector,i+1,right,compare,exchange);voidSortMethod(void) inti,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+) pvec

30、tor->recordi.key=random(5000); pvector->n=MAXSORTNUMj;InsertSort(pvector,&numj0,&numj1);SelectSort(pvector,&numj2,&numj3);BubbleSort(pvector,&numj4,&numj5);ShellSort(pvector,4,&numj6,&numj7);Heapsort(pvector,&numj8,&numj9); QuickSort(pvector,0,MAXSORTNUM

31、j-1,&numj10,&numj11);printf("nSort Method Compare As Follows:");for(j=0;j<3;j+)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:Com

32、pared->%-7ld Exchanged->%-7ldn",numj2,numj3); printf("3.BubbleSort Method:Compared->%-7ld Exchanged->%-7ldn",numj4,numj5);printf("4.ShellSort Method:Compared->%-7ld printf("5.HeapSort Method:Compared->%-7ld printf("6.QuickSortMethod:Compared->%-7ld

33、if(j!=2)printf("Press Enter to continue.n");s getchar();void main()SortMethod();Exchanged->%-7ldn",numj6,numj7);Exchanged->%-7ldn",numj8,numj9);Exchanged->%-7ldn",numj10,numj11)六、程序运行与测试图 6.1 数据长度为 20 时算法运行界面卫 CIridcwsfomd?num is 20,the result is:Method :CoBp<ire

34、cl>lfi0Method :Co«p<ireci? 190Method: CoMpared>18 7Method :Coinpfired-> 5?Nft t hod: Conpared->60Method:Canpared->17When The ndx 1.InseriSort 2.SeLectSort 3. Elubb eSort 4.ShellSort 5 r HeaoSort g. QuicksortPress (-rHerWhen The id ax 1.InseriSort2 .Selcc.tScr t3.BubbleSor t 4.ShelISor t5. HeapSort6. QuickSor tExchanged- >137 Exchaned Exchanged>3 fi& rxchanejed-> 15S Fxchaned->A8 Exchanged>35Exchansed->2672 EMchflnged->285E>«:hiinynd->7434Exchanged>1410Enchanted->359Exchansed> 176Exchanged>62702Lxchah£