基于C語言實(shí)現(xiàn)的若干排序算法和分析

《基于C語言實(shí)現(xiàn)的若干排序算法和分析》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、萬方數(shù)據(jù)第九卷第一期安徽電氣工程職業(yè)技術(shù)學(xué)院學(xué)報(bào)2004年3月V01．9，No．IJOURNALOFANHUIELECTRICALENGINEERINGPROFESSIONALTECHNIQUECOLLEGEMarch2004基于C語言實(shí)現(xiàn)的若干排序算法和分析汪祖柱，沈曉璐’(安徽大學(xué)管理學(xué)院，安徽合肥230039)【摘要】討論了幾種常見的內(nèi)部排序算法及其時(shí)間復(fù)雜度：插入排序、起泡排序、選擇排序、快速排序、希爾排序、堆排序，并且對(duì)這幾種排序算法進(jìn)行了分析比較。著重提供了希爾排序和堆排序的實(shí)現(xiàn)程序，以堆排序及希爾排序作為具體應(yīng)用例子來實(shí)現(xiàn)對(duì)一批數(shù)據(jù)進(jìn)行排序。

2、[關(guān)鍵詞]排序；算法；比較；交換[中圖分類號(hào)]TPl8[文獻(xiàn)標(biāo)識(shí)碼]A[文章編號(hào)]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引言作為計(jì)算機(jī)科學(xué)中一項(xiàng)復(fù)雜而重要的技術(shù)，排序一直是計(jì)算機(jī)領(lǐng)域內(nèi)人們感興趣的課題，尋找速度快、附加存儲(chǔ)空間開銷小的高效排序算法也一直是

4、人們追尋的目標(biāo)。本文討論整數(shù)數(shù)組元素的排序，分析幾種常見排序算法并進(jìn)行比較；著重提供了希爾排序和堆排序的實(shí)現(xiàn)程序，并且已在TurboC2．0上運(yùn)行通過。2常見的幾種排序算法2．1插人排序2．1．1基本思想插入排序是逐個(gè)處理待排序的記錄，每個(gè)新記錄與前面已排序的子序列進(jìn)行比較，將它插入到子序列中正確的位置，直到全部插完為止。2．1．2算法步驟在插入第i個(gè)記錄時(shí)，假設(shè)rl，r2，??，ri—l已經(jīng)排序，下面用順序存儲(chǔ)表示給出算法。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、部循環(huán)共要做i一1次n比較。因此，K-I：較次數(shù)最多為：∑i=@(竹2)。相反地，考慮最佳情況，此時(shí)數(shù)組中的關(guān)鍵碼是完全有序i=2的，總的比較次數(shù)即外循環(huán)的執(zhí)行次數(shù)。因此最佳情況下插入排序的時(shí)間代價(jià)是@(n)。在平均情況下。在數(shù)組的前i一1個(gè)記錄中有一半值比第i個(gè)記錄的值大，因此，平均時(shí)間開銷就是最差情況的一半，仍然為@(”2)。而總交換次數(shù)是總比較次數(shù)減去／,g一1，它在最佳情況下為0，在最差及平均情況下為@(行2)。2．2起泡排序2．2．1基本思想將待排序的記錄的鍵值順次做兩兩比較，若為“逆序”則將兩個(gè)記錄交換。2．2．2算法步驟對(duì)含，z個(gè)記錄的文件進(jìn)

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、它前一個(gè)結(jié)點(diǎn)的鍵值小的概率有多大就決定了交換的次數(shù)。實(shí)際上起泡排序