《2022年多种排序算法的比较和分析 .pdf》由会员分享，可在线阅读，更多相关《2022年多种排序算法的比较和分析 .pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、排序算法的分析与比较- 1 - 一、设计思想排序是指将一个数据元素的任意序列，按关键字重新排列成一个有序的序列。当关键字为记录中的主关键字时，排序结构是唯一的，否则结果不唯一。如果待排序记录中存在多条关键字相同的记录，经过排序后，这些记录之间的相对次序不变，则称这种排序算法为稳定的 ；反之，称为 不稳定的 。排序算法的评价依据算法的时间复杂度，执行算法所需的附加空间以及算法本身的复杂性来判定的。选择排序的基本思想：首先在所有记录中选出关键字最小的记录，把它与第1 个记录交换，然后在其余的记录中再选出关键字次最小的记录与第2 个记录交换， 以次类推 ，直到所有记录排序完成。简单选择排序过程中的记
2、录比较次数与记录序列的初始状态无关，无论记录的初始序列如何，所需进行的关键字比较次数均为：（n-1+n-2+ +1） =O(n2) 当记录序列的初始状态为“ 有序 ” 状态时，所需进行的记录移动次数最少，为 0 次；当记录序列的初始状态为“ 逆序 ” 状态时，所需进行的记录移动次数最多，为3(n-1)次。因此，简单选择排序总的时间复杂度为O(n2) 插入排序的基本思想：一趟直接插入排序的基本操作是：将一个记录插入到一个有序的子序列中，从而使有序子序列的长度增1。一般情况下，第i 趟直接插入排序的操作为：在含有 i-1 个记录的有序子序列r1.i-1 中插入一个记录ri ，变成含有i 个记录的有
3、序子序列r1.i ，整个排序过程需插入n-1 趟插入，即i 从 2 到 n。直接插入排序的算法简洁，容易实现。从时间来看，排序的基本操作为：比较两个记录的大小和移动记录。其中： 1、最小比较次数：Cmin = n-1 = O(n) 2、最大比较次数：Cmax =(2+3+ +n)= (n+2)(n-1) /2 = O(n2 ) 3、最小移动次数：Mmin = 0 4、最大移动次数：Mmax = (2+1+3+1+ +n+1) = O(n2)从空间看，直接插入排序算法只需一个记录的辅助空间。直接插入排序算法当记录的数量n很小时， 是一种很好的排序方法。但是通常待排序的记录数量n 很大时， 则不宜
4、采用直接插入排序。在直接插入排序的基础上，从减少比较和移动 着两种操作的次数着眼，可得到一些改进的算法，如折半插入排序，可以减少关键字之间的比较次数，但移动次数不变。2-路插入排序可以减少比较和移动次数。另外表插入排序可以做到不移动记录。希尔排序的基本思想：希尔排序方法是一种“ 逐渐缩小插入间隔” 的插入排序方法，在时间效率上较直接插入排序有较大的改进。从对直接插入排序的分析可知，其时间复杂度为O(n2), 但是当待排序记录处于基本有序 状态或当 n 值较小时， 直接插入排序的效率可大大提高。希尔排序方法正是基于这两点考虑对直接插入排序加以改进而提出的一种插入排序算法。 Shell 排序的基本
5、的做法是先确定一个小于n 的整数 gap1 作为第一个增量，把记录序列分为 gap1 个组， 所有距离为gap1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后， 取第二个增量gap2 （gap2 gap1）,重复上述分组和排序，直至所取的增量gapt=1（gaptgapt-1 gap2gap1）,即所有记录处在同一组中进行直接插入排序为止。当n时，可减少至n ( log2n )2。快速排序的基本思想：首先选取一个记录作为支点（不失一般性，可选第一个记录），依它的关键字为基准重排其余记录，将所有关键字比它大的记录都排在它之后，而将所有关键字比它小的记录都排在它之前，由此完成一趟快速排序
6、。之后，分别对由一趟排序分割而成的两个子序列进行快速排序。最坏情况：O(n*n) ；最好情况： O(nlog2n) 。快速排序的平均时间复杂度是O(knlogn), 它是目前基于比较的内部排序方法中速度最快的一种，快速排序也因此而得名。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 13 页 - - - - - - - - - 排序算法的分析与比较- 2 - 归并排序的基本思想：归并排序是利用“ 归并 ” 技术来进行排序，所谓归并是指将两个有序的序列合并形成一个新的有序序
7、列。将待排序记录序列r1,r2,rn 看成为 n个长度为1 的有序子序列，把这些子序列两两进行归并，便得到【n/2】个长度为2 的有序子序列，然后在两两归并，如此重复， 直到最后得到一个长度为n 的有序记录序列为止，这种方法成为归并方法。对n 个记录的序列进行归并排序时，必须进行【log2n】趟归并，而每趟归并所需的时间是O(n),所以二路归并排序算法时间复杂度为O(nlog2n)。与快速排序和堆排序相比， 归并排序的最大优点是，它是一种稳定的排序方法，但在一般情况下，很少利用归并排序进行内部排序。二、算法流程图图 1：快速排序算法流程图名师资料总结 - - -精品资料欢迎下载 - - - -
8、 - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 13 页 - - - - - - - - - 排序算法的分析与比较- 3 - 图 2：选择排序算法流程图图 3：插入排序算法流程图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 13 页 - - - - - - - - - 排序算法的分析与比较- 4 - 图 4：希尔排序算法流程图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -
9、- - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 13 页 - - - - - - - - - 排序算法的分析与比较- 5 - 图 5：归并排序算法流程图图 1 表示快速排序算法流程图。首先选取一个记录作为支点（不失一般性， 可选第一个记录） ，依它的关键字为基准重排其余记录，将所有关键字比它大的记录都排在它之后，而将所有关键字比它小的记录都排在它之前，由此完成一趟快速排序。图 2 表示选择排序流程图。首先在所有记录中选出关键字最小的记录，把它与第 1 个记录交换， 然后在其余的记录中再选出关键字次最小的记录与第2 个记录交换，以次类推 ，直到所有记
10、录排序完成。图 3 表示插入排序流程图。一趟直接插入排序的基本操作是：将一个记录插入到一个有序的子序列中，从而使有序子序列的长度增1。图 4 表示希尔排序的流程图。希尔排序方法是一种“ 逐渐缩小插入间隔” 的插入排序方法，在时间效率上较直接插入排序有较大的改进。图5表示归并排序的流程图。图 5 是归并排序的流程图。 归并排序是利用“ 归并 ” 技术来进行排序，所谓归并是指将两个有序的序列合并形成一个新的有序序列。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 13 页 -
11、 - - - - - - - - 排序算法的分析与比较- 6 - 三、源代码#include #include #define length 100 int Mtimes=0; int Ctimes=0; void printArray( int array)/* 打印数组函数 */ int i; for(i=0;ilength;i +) /* 对要打印的数组进行遍历*/ printf( %d ,arrayi);/* 打印待排序数组*/ printf( n ); /* 选择排序 */ selectsort(int array) int blength = 0;/* 定义新数组 */ int i
12、,j,temp,m=0,n,x; for(i=0;ilength;i +)/* 扫描待排序数组*/ temp=arrayi;/* 将i 赋予 temp*/ n=i; for(j=0;jlength;j+) Ctimes+ ; if(arrayj temp)/* 将数组的值赋予temp*/ temp=arrayj; Mtimes+; /* 移动次数 +1*/ n=j; bm =temp; m+; arrayn=999;/* 设置一个无限大的值999*/ /* 直接插入排序 */ void insertsort(int array) /* 插入排序函数 */ int i,j,m,temp,n; 名
13、师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 13 页 - - - - - - - - - 排序算法的分析与比较- 7 - for(i=1;i=0;j-) Ctimes+; /* 比较次数自加 */ if(arrayi j+1;m-) arraym =arraym-1; Mtimes+; arraym =temp; /* 将arrayi插入*/ /*printArray(array);调用打印函数打印数组*/ printf( Mtimes= %d ,Mtimes); pr
14、intf( Ctimes=%d,Ctimes); printf( n ); /* 希尔排序代码 */ void shellsort(int array) int gaps= 1,5,13,43,113,297,815,1989 ;/* 定义步长 */ int i,j; int k; int gap; int temp; for(k=0;gapsk =0) gap=gapsk; for(i=gap;i=gap& arrayj-gap temp) Mtimes+;/* 移动次数加 1*/ arrayj =arrayj-gap; j=j-gap; arrayj =temp;/* 将j 赋给 temp
15、*/ printf( Mtimes= %d ,Mtimes); printf( Ctimes=%d,Ctimes); printf( n ); void merge(int array, int top,int middle,int bottom) /* 建立归并排序函数*/ int tempa100;/* 声明一个临时数组*/ int left=top; int right=middle+1; int tempIndex=0; int begin=0; int end=0; int i=0,j; while(left=middle& right=bottom)/* 当数组不为空 */ Mti
16、mes+; Ctimes+; if(arrayleft =arrayright)/* 若左边数组元素小于右边元素*/ tempatempIndex =arrayleft;/* 将左边的元素放入临时数组*/ left+;/* 左边索引加 1*/ else/* 若左边数组元素大于右边元素*/ tempatempIndex =arrayright;/* 将右边的元素放入临时数组*/ right+;/* 左边索引加 1*/ tempIndex+;/* 临时索引加 1*/ if(left=middle)/* 若左边的元素剩下*/ begin=left; end=middle; 名师资料总结 - - -精
17、品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 13 页 - - - - - - - - - 排序算法的分析与比较- 9 - else/* 若右边的元素剩下*/ begin=right; end=bottom; for(i=begin;i=end;i+)/* 遍历剩下的数组*/ Mtimes+; tempatempIndex =arrayi; tempIndex+; for(i=top,j=0;i=bottom;i +,j+)/* 将排好序的数组放回原数组中*/ arrayi =tempaj; v
18、oid mergesort(int array,int top,int bottom,int level)/* 归并排序代码 */ int middle;/* 声明中值 */ if(top=bottom)/* 数组不为空的话返回*/ return; for(i=top+1;i=pivot)/* 若数组元素大于支点则放入大数组中*/ bigbigIndex =arrayi; bigIndex+; else/* 若数组元素大于支点则放入小数组中*/ smallsmallIndex =arrayi; smallIndex+; for(i=0;ismallIndex;i +)/* 将小数组放入原数组的
19、前面*/ Mtimes+; Ctimes+; arrayarrayIndex +top=smalli; arrayIndex+ ; arrayarrayIndex+top=pivot;/* 将支点放入 */ arrayIndex+; for(i=0;ibigIndex;i +)/* 将大数组放入原数组的支点的后面*/ arrayarrayIndex +top=bigi; arrayIndex+ ; quicksort( array,top,top+smallIndex -1,level+1);/* 递归调用本函数，对小数组部分进行快速排序*/quicksort( array,top+small
20、Index+1,bottom,level+1);/* 递归调用本函数， 对大数组部分进行快速排序*/ void main() int i=0,j; int arraylength,array1length,array2length,array3length,array4length; for(j =0;j4;j+)/* 每组排序执行 4次 */ for(i=0;ilength;i +) arrayi =array1i =array2i =array3i =array4i =rand()%100; /* 生成随机函数 */printf( nThe insertsort order is: );/
21、* 打印插入排序结果*/ Mtimes=0;/* 计时归零 */ Ctimes=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 13 页 - - - - - - - - - 排序算法的分析与比较- 11 - insertsort(array); printf( The shellsort order is: );/* 打印希尔排序结果*/ Mtimes=0; Ctimes=0; shellsort(array1); printf( The mergesort or
22、der is: );/* 打印归并排序结果*/Mtimes=0; Ctimes=0; mergesort(array2,0,length-1,0); printf( Mtimes= %d ,Mtimes); printf( Ctimes=%d,Ctimes); printf( nThe quicksort order is: );/* 打印快速排序结果*/ Mtimes=0; Ctimes=0; quicksort(array3,0,length -1,0); printf( Mtimes= %d ,Mtimes); printf( Ctimes=%d,Ctimes); printf( nTh
23、e selectsort order is:);/* 打印选择排序结果*/ Mtimes=0; Ctimes=0; selectsort(array4); printf( Mtimes= %d ,Mtimes); printf( Ctimes=%d,Ctimes); getchar(); 四、运行结果图 6 多种排序算法运行结果名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 13 页 - - - - - - - - - 排序算法的分析与比较- 12 - 由以上运算结果可
24、以得知：直接插入排序算法当记录的数量n 很小时， 是一种很好的排序方法。希尔排序方法是改进的插入排序方法，在时间效率上较直接插入排序有较大的提高。从分析可知，希尔排序和插入排序时间复杂度为O(n2), 但是当待排序记录处于基本有序 状态或当 n 值较小时， 直接插入排序的效率可大大提高。但是通常待排序的记录数量n很大时，希尔排序则优于插入排序。选择排序均为比较10000 次，移动 100 次，属于移动最优的排序算法， 但是它的缺点就是进行判断比较的次数比较多。进行归并排序时，其时间复杂度为 O(nlog2n) ，它是一种比较稳定的算法。快速排序相比归并排序速度快但稳定性不高，其最坏情况： O(
25、n*n) ；最好情况： O(nlog2n) 。五、遇到的问题及解决这部分我主要遇到了如下三个问题，其内容与解决方法如下所列：归并排序如何实现归并排序是利用“ 归并 ” 技术来进行排序， 所谓归并是指将两个有序的序列合并形成一个新的有序序列。 将待排序记录序列r1,r2,rn 看成为 n 个长度为 1 的有序子序列， 把这些子序列两两进行归并，便得到【n/2】个长度为2 的有序子序列，然后在两两归并，如此重复，直到最后得到一个长度为n 的有序记录序列为止，按分治思想可以分为三个步骤：（1）将原数组分解为一系列子数组。（2）递归地解决子数组。知道子数组足够小，直接排序。（3）将子数组的结果合并成原
26、数组。上一种算法排好序的数组传到下一个算法导致第二个算法不排序。前一种算法排序的数组，传到下一个算法中，因为是排好序的序列，所以导致第二个算法的比较次数和移动次数均为零。又要求必须是统一的数组，则不能重新随机生成，所以定义五个数组array length,array1length ,array2length,array3length, array4length。 要求五个数组相等， 即 array length=array1length= array2length= array3length= array4length。希尔算法是如何执行的在希尔排序中，子序列的构成不是简单地“ 逐段分割 ”
27、，而是将相隔某个“ 增量” 的记录组成一个子序列。 如在第一趟排序时的增量为7，即将相隔为7 的元素编成一组进行直接插入排序。第二趟排序时的增量为3，增量进一步缩小。由于在这两趟的插入排序中在子序列中逆序的关键字是跳跃式地移动，从而使得在进行最后一趟增量为1 的插入排序时，序列已基本有序， 只要作少量比较和移动即可完成排序，因此希尔排序的时间复杂度较直接插入排序低。 下面用算法语言描述的希尔排序: 希尔排序中增量序列的选取是一个复杂的问题，涉及到一些数学上尚未解决的难题。我们不想加以详细讨论。到目前仅得出部分结论：如当增量序列为 dk=2t-k+l -1时，希尔排序的运行时间为O(n3/2)
28、，其中 1kt log2(n1) 。增量序列还可以有各种取法, 如 dk=2t-k ，（ d=,9,5,3,2,1）。但请注意：应使增量序列中的值没有除1 之外的公因子，并且最后一个增量值必须等于1。六、心得体会要编写一个程序， 首先要先做好算法。 算法的残缺和逻辑错误将会直接导致编程的失败。然而， 从一开始就能设计出完美的算法，几乎是不可能的，除非这个问题是前人解决过的而且刚好你学会了或者对你来说是个十分简单的问题。但是这并不代表我们就不能无限的让自名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - -
29、- - - 第 12 页，共 13 页 - - - - - - - - - 排序算法的分析与比较- 13 - 己的算法趋于完美。因为几乎每一个程序都是分块完成的，所以我们一定会遇到前人曾经解决过的问题， 如果我们可以把这些别人解决过的问题的算法很好的应用进自己的程序，这时我们就可以得到一个相对很好的算法。可见，学习是多么的重要。我想编写一个程序的过程应该是这样的。首先将自己认为正确的算法用编程语言编写出来，然后在进行调试并不断完善自己的算法。这时就需要对程序中的每个元素进行监控，确保他按你的想法完成。当然，printf（）语句可以实现这个功能，但是却十分费力。个人推荐用一种编程软件， 不但可以让你实现对每个元素的监控还能明确的告诉你程序每个步骤运行的先后顺序。对于排序算法的学习，不仅让我掌握了新知识多种排序算法，还让我对以前学习的知识更加熟悉了。对于新知识的学习总可以获得很多除此之外更多的收获。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 13 页 - - - - - - - - -