数据结构各种排序算法性能比拼Word文档格式.docx

1、2、Shell排序 Shell排序又称缩小增量排序,Shell排序法是以创建者Donald Shell的名字命名的.Shell排序法是对相邻指定距离（称为间隔）的元素进行比较,已知到使用当前间隔进行比较的元素都按顺序排序为止.Shell把间隔缩小一半,然后继续处理,当间隔最终变为1,并且不再出现变化时,Shell排序也就完成了其处理过程.先取一个整数d1n,把全部记录分成d1个组，所有距离为d1倍数的记录放在一组中，先在各组内排序；然后去d2d1重复上诉分组和排序工作；直至所取的增量dt=1（dtdt-ld2d1），即所有记录放在同一组中进行直接插入，直到dt=1，即所有记录放在一组中为止.

2、希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o（n2）好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。所以希尔排序是不稳定的，其时间复杂度为o（n2）。3、直接选择排序 待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二

3、个位置的数据元素交换，循环到只剩下最后一个数据元素为止，依次类推直到所有记录。第一趟第n个记录中找出关键码最小的记录与第n个记录交换；第二趟，从第二个记录开始的，2 -1个记录中再选出关键码最小的记录与第二个记录交换；如此，第 i 趟，则从第i个记录开始的 n - i + l个记录中选出关键码最小的记录与第 i 个记录交换，直到所有记录排好序。 该算法运行时间与元素的初始排列无关。不论初始排列如何，该算法都必须执行n-1趟，每趟执行n-i-1次关键字的比较，这样总的比较次数为：所以，简单选择排序的最好、最坏和平均情况的时间复杂度都为O（n2）。4、冒泡排序 在每一趟冒泡排序中，依次比较相邻的两

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

5、序出现最好情况。此时，只需进行一趟排序，作n-1次关键字比较，因此最好情况下的时间复杂度是O（n）。当原始数据反向有序时，冒泡排序出现最坏情况。此时，需进行n-1趟排序，第i趟作（n-i）次关键字间的比较，并且需执行（n-i）次元素交换，所以，比较次数为：因此,最坏情况下的时间复杂度为O（n2）。五、快速排序 首先我们选择一个中间值 middle （程序中我们可使用数组中间值），把比中问值小的放在其左边，比中问值大的放在其右边。由于这个排序算法较复杂，我们先给出其进行一次排序的程序框架。在待排序的个记录中任意取一个记录（通常取第一个记录）为区分标准，把所有小于该排序的记录移到左边，把所有大于该

6、排序码的记录移到右边，中级放所选记录，为一趟快速排序。然后对前后两个子序列分别重新上述过程，直到所有记录都排好序。对任意给定的序列中某个元素，经过一趟排序后，将原序列分割成两个子序列（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（s-1）为其低端序列，（Rp（0）,Rp（1）,Rp（s-1）为其高端序列。很明显，以后只需对低端和高端序列分别进行快速排序，直到子

7、序列为空或只有一个元素时结束，最后得到有序序列。总之，每趟使表的第一个元素放在适当位置，将表两分，再对子表进行同样的递归划分，直至划分的子表长度为1。 如果每一次分划操作后，左、右两个子序列的长度基本相等，则快速排序的效率最高，其最好情况时间复杂度为O（nlog2n）；反之，如果每次分划操作所产生的两个子序列，其中之一为空序列，此时，快速排序效率最低，其最坏情况时间复杂度为O（n2）。如果选择左边第一个元素为主元，则快速排序的最坏情况发生在原始序列正向有序或反向有序时。快速排序的平均情况时间复杂度为O（nlog2n）。六、堆排序1.原理 堆排序思想很简单，就是每次把关键词调整为堆，取出堆顶元素

8、与堆中最后一个元素交换，同时令堆得大小减一，把剩余的一些元素重新调整为堆，重复此过程，直到堆中只剩一个元素,n个关键字序列 kl , k2 ， ， kn称为堆，当且仅当该序列满足如下性质（简称为堆性质）: （ l） ki= k2i 且 ki= k2i 且 ki=k2i+1。若将此序列所存储的向量 R 1n看作是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树:树中非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆。 堆排序

9、的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。堆排序的最坏时间复杂度为O（nlogn）。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是不稳定的，算法时间复杂度O（nlogn）。 程序运行结果以及结果分析一、下图是对随机生成的10000个数进行排序，可以看出快速排序法耗时最少而直接插入排序耗时最多，堆排序和快速排序差不多。二、下图是对20000个随机数进行的排序，可以看出得出了和上述一样的结果。对程序结果的评价经过比较我们发现，当规模不断增加时，各种算法之间的差别是很大的。这七种算

10、法中，快速排序耗时是最少的。也是最快的一种排序方法。堆排序和快速排序差不多，属于同一个数量级。直接选择排序是耗时最多的。通过这次作业我学到了很多东西： 巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。 通过自己编写的程序对各种排序性能的比较让我更深入理解了他们的应用。 参考文献1严蔚敏，吴伟民， 数据结构（C语言版），清华大学出版社2007 附录#includestdio.htime.h#define SWAP（x,y） int t;t=x; x=y; y=t;#define N 30000void nixu（int a,int b）/ 反序 int i; for（i=0;iN

11、;i+） bN-1-i=ai; void popo（int a,int len）/*冒泡排序*/ int length=len; int i=0; int j=0; for（;len; for（;jaj+1） int temp=aj; aj=aj+1; aj+1=temp; length-; j=0;void select（int array,int n）/选择排序 int i,j,t,k;n-1; k=i; for（j=i+1;n; if（arrayjarrayk）k=j; /k存放一轮中的最小数的下标; t=arrayi; arrayi=arrayk; arrayk=t; void Swa

12、p（int *a,int *b） int temp; temp = *a; *a = *b; *b = temp;void InsertSort（int data,int length）/直接插入排序 int i = 0; int j = 0; for（i = 1;i 0;-j） if（dataj right） return; while（i!=j）/*找到最终位置*/ while（aj=temp & ji） j-; if（j ai+=aj; while（ai i+; aj-=ai; ai=temp; quickSort（a,left,i-1）;/*递归左边*/ quickSort（a,i+1

13、,right）;/*递归右边*/ /归并排序 /归并排序合并数组函数的具体实现 void merge（int a,int low,int middle,int high） int h,i,j,k; int bN; h=low; i=low; j=middle+1; while（h=middle&=high） if（ahmiddle） for（k=j;k=high;k+） bi=ak; for（k=h;=middle; for（k=low; ak=bk;/归并排序函数的具体实现 void mergesort（int a,int low,int high） int middle; if（lowhi

14、gh） middle=（low+high）/2; mergesort（a,low,middle）; mergesort（a,middle+1,high）; merge（a,low,middle,high）;void swapa（int a, int i, int j）/希尔排序 int t = ai; ai = aj; aj = t;void selsort（int a, int n, int incr） int i, j; for （i = incr; i = incr） & （aj 2; i /= 2） for （j = 0; j i; j+） selsort（&aj, n - j, i）

15、; selsort（a, n, 1）;void shift（int a,int i,int m）/堆排序 int k,t; t=ai; k=2*i+1; while （km） if （km-1） & （ak ak+1） k +; if （t=0;i-） shift（a,i,n）; for（i=n-1;= 1;i-） k=a0;a0=ai;ai=k; shift（a,0,i）;int main（）int series N=0; int series_0N; int series_aN; int series_bN; int series_cN; int series_dN; int series

16、_eN; int series_fN; int series_gN; int i,num; srand（time（NULL）; seriesi=rand（）%N; series_0i=seriesi; for（num=0;num0） nixu（series_0,series）; printf（待排数据：n）;%d ,seriesi）; putchar（N）; series_ai=seriesi; series_bi=seriesi; series_ci=seriesi; series_di=seriesi; series_ei=seriesi; series_fi=seriesi; serie

17、s_gi=seriesi; clock_t begin1, end1;/*计算冒泡排序时间*/ double cost1; begin1 = clock（）; popo（series_a,N-1）; end1 = clock（）; cost1 = （double）（end1 - begin1）/ CLOCKS_PER_SEC;冒泡排序耗时:%lf secondsn,cost1）; clock_t begin2,end2;/*计算选择排序时间*/ double cost2; begin2=clock（）; select（series_b,N）; end2=clock（）; cost2=（doub

18、le）（end2 - begin2）/ CLOCKS_PER_SEC;选择排序耗时:,cost2）; clock_t begin3, end3;/*计算直接插入排序时间*/ double cost3; begin3=clock（）; InsertSort（series_c,N）; end3=clock（）; cost3=（double）（end3-begin3）/ CLOCKS_PER_SEC;直接插入排序耗时:,cost3）; clock_t begin4, end4;/*计算快速排序时间*/ double cost4; begin4=clock（）; quickSort（series_d,

19、0,N-1）; end4=clock（）; cost4=（double）（end4-begin4） / CLOCKS_PER_SEC;快速排序耗时:,cost4）; clock_t begin5, end5;/*计算归并排序时间*/ double cost5; begin5=clock（）; mergesort（series_e,0,N-1）; end5=clock（）; cost5=（double）（end5-begin5）/ CLOCKS_PER_SEC;归并排序耗时:,cost5）; clock_t begin6, end6;/*计算希尔排序时间*/ double cost6; begin6=clock（）; shellsort（series_f,N）; end6=clock（）; cost6=（double）（end6-begin6）/ CLOCKS_PER_SEC;希尔排序耗时:,cost6）; clock_t begin7, end7;/*计算堆排序时间*/ double cost7; begin7=clock（）; heap（series_g,N）; end7=clock（）; cost7=（double）（end7-begin7）/ CLOCKS_PER_SEC;堆排序耗时:,cost7）;