基于C语言实现的若干排序算法和分析

《基于C语言实现的若干排序算法和分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第九卷第一期安徽电气工程职业技术学院学报2004年3月V01．9，No．IJOURNALOFANHUIELECTRICALENGINEERINGPROFESSIONALTECHNIQUECOLLEGEMarch2004基于C语言实现的若干排序算法和分析汪祖柱，沈晓璐’(安徽大学管理学院，安徽合肥230039)【摘要】讨论了几种常见的内部排序算法及其时间复杂度：插入排序、起泡排序、选择排序、快速排序、希尔排序、堆排序，并且对这几种排序算法进行了分析比较。着重提供了希尔排序和堆排序的实现程序，以堆排序及希尔排序作为具体应用例子来实现对一批数据进行排序。

2、[关键词]排序；算法；比较；交换[中图分类号]TPl8[文献标识码]A[文章编号]1009—1238(2004)01—0085—05SortingAlgorithmsBasedonCLanguageandAnalysisWANGZu—zhu，SHENXiao—lU(SchoolofManagement，AnhuiUniversity，Hefei230039，China)[Abstract]Somesortingalgorithms，whichareinsertionsort，bubblesort，selectionsort，quicksort，Shells

3、ortandheapsort，arediscussed．Theabovealgorithmsarealsocomparedinseveralaspects．AsexamplestwoCprogramssortingsomeintegersusingalgorithmsonShellsortandHeapsortareimplemented．[Keywords]sorting；algorithm；compare；change1引言作为计算机科学中一项复杂而重要的技术，排序一直是计算机领域内人们感兴趣的课题，寻找速度快、附加存储空间开销小的高效排序算法也一直是

4、人们追寻的目标。本文讨论整数数组元素的排序，分析几种常见排序算法并进行比较；着重提供了希尔排序和堆排序的实现程序，并且已在TurboC2．0上运行通过。2常见的几种排序算法2．1插人排序2．1．1基本思想插入排序是逐个处理待排序的记录，每个新记录与前面已排序的子序列进行比较，将它插入到子序列中正确的位置，直到全部插完为止。2．1．2算法步骤在插入第i个记录时，假设rl，r2，⋯⋯，ri—l已经排序，下面用顺序存储表示给出算法。voidcrpxz(JD“]，intn){inti，j；for(i=2；i<=n；i++){r[0]=r[i]；j=i一1；whil

5、e(r[0]．key

6、部循环共要做i一1次n比较。因此，K-I：较次数最多为：∑i=@(竹2)。相反地，考虑最佳情况，此时数组中的关键码是完全有序i=2的，总的比较次数即外循环的执行次数。因此最佳情况下插入排序的时间代价是@(n)。在平均情况下。在数组的前i一1个记录中有一半值比第i个记录的值大，因此，平均时间开销就是最差情况的一半，仍然为@(”2)。而总交换次数是总比较次数减去／,g一1，它在最佳情况下为0，在最差及平均情况下为@(行2)。2．2起泡排序2．2．1基本思想将待排序的记录的键值顺次做两两比较，若为“逆序”则将两个记录交换。2．2．2算法步骤对含，z个记录的文件进

7、行排序最多需要，z一1趟起泡排序。下面给出算法。voidqppx(JDr[]，intn){inti，j，k；JDx；j=1；k=1；while((jO)){k=0；for(i=1；i<=n；i++)if(r[i++]．key

8、它前一个结点的键值小的概率有多大就决定了交换的次数。实际上起泡排序