几种排序算法分析

《几种排序算法分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

《几种排序算法的分析》摘要：排序算法是在C++中经常要用到的一种重要的算法。如何进行排序，特别是高效率的排序是是计算机应用屮的一个重要课题。同一个问题可以构造不同的算法，最终选择哪一个好呢？这涉及如何评价一个算法好坏的问题，算法分析就是评估算法所消耗资源的方法。可以对同一问题的不同算法的代价加以比较，也可以由算法设计者根据算法分析判断一种算法在实现时是否会遇到资源限制的问题。排序的目的之一就是方便数据的查找。在实际生活中，应根据具体情况悬着适当的算法。一般的，对于反复使用的程序，应选取时间短的算法；对于涉及数据量较大，存储空间较小的情况则应选取节约存储空间的算法。木论文重点讨论时间复杂度。时间复杂度就是一个算法所消耗的吋间。算法的效率指的是最坏情况下的算法效率。排序分为内部排序和外部排序。本课程结业论文就内部排序算法（插入排序，选择排序，交换排序，归并排序和基数排序）的基本思想，排序步骤和实现算法等进行介绍。本论文以较为详细的文字说明，表格对比，例子阐述等方面加以比较和总结，通过在参加数据的规模，记录说带的信息量大小，对排序稳定的要求，关键字的分布情况以及算法的时间复杂度和空间复杂度等方面进行比较，得出它们的优缺点和不足，从而加深了对它们的认识和了解，进而使自己在以后的学习和应用中能够更好的运用。 1•五种排序算法的实例:1.1•插入排序1.1.1.直接插入排序思路：将数组分为无序区和有序区两个区，然后不断将无序区的笫一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。要点：设立哨兵，作为临时存储和判断数组边界Z用。实现：VoidTnsertSort(NodeL[],intlength){Tnti,j;//分别为有序区和无序区指针for(i=l;i=l)//直到增量缩小为1{Shell(L,d);d=d/2;//缩小增量VoidShell(NodeL[],intd)Inti,j;For(i=d+l;i=l)//直到增量缩小为1{Shell(L,d);d=d/2;//缩小增量VoidShell(NodeL[],intd)Inti,j;For(i=d+l;iO&&L[j]>L[O]){L[j+d]=L[j];//移动j二j-d;〃查找}L[j+d]二L[0];}1・2•选择排序1.2.1.直接选择排序思路：将序列划分为无序和冇序区，寻找无序区中的最小值和无序区的首元素交换，冇序区扩大一个，循环最终完成全部排序。实现：VoidSelectSort(NodeL[]){Inti,j,k;//分別为有序区，无序区，无序区最小元素指针For(i=0;i0;i--)〃交换{Tnttemp=L[i];L[i]二L[0];L[0]=temp;Heapify(L,0,i);//调整堆}}VoidBuildingHeap(NodeL[]){For(i=length/2T;i>0;i--)Heapify(L,i,length);}1.3.归并排序思路：将原序列划分为有序的两个序列，然后利用归并算法进行合并，合并之后即为冇序序列。要点：归并、分治实现：VoidMergeSort(NodeL[],intm,intn){Intk;If(m