幾種排序算法的分析與比較C語言

1、- -一、設計思想插入排序：首先，我們定義我們需要排序的數(shù)組，得到數(shù)組的長度。如果數(shù)組只有一個數(shù)字，那么我們直接認為它已經(jīng)是排好序的，就不需要再進行調(diào)整，直接就得到了我們的結(jié)果。否則，我們從數(shù)組中的第二個元素開始遍歷。然后，啟動主索引，我們用curr當做我們遍歷的主索引，每次主索引的開始，我們都使得要插入的位置(insertindex)等于-1,即我們認為主索引之前的元素沒有比主索引指向的元素值大的元素，那么自然主索引位置的元素不需要挪動位置。然后，開始副索引，副索引遍歷所有主索引之前的排好的元素，當發(fā)現(xiàn)主索引之前的某個元素比主索引指向的元素的值大時，我們就將要插入的位置(insertinde

2、x)記為第一個比主索引指向元素的位置，跳出副索引；否則，等待副索引自然完成。副索引遍歷結(jié)束后，我們判斷當前要插入的位置(insertindex)是否等于-1，如果等于-1，說明主索引之前元素的值沒有一個比主索引指向的元素的值大，那么主索引位置的元素不要挪動位置，回到主索引，主索引向后走一位，進行下一次主索引的遍歷；否則，說明主索引之前insertindex位置元素的值比主索引指向的元素的值大，那么，我們記錄當前主索引指向的元素的值，然后將主索引之前從insertindex位置開始的所有元素依次向后挪一位，這里注意，要從后向前一位一位挪，否則，會使得數(shù)組成為一串相同的數(shù)字。最后，將記錄下的當前索

3、引指向的元素的值放在要插入的位置(insertindex)處，進行下一次主索引的遍歷。繼續(xù)上面的工作，最終我們就可以得到我們的排序結(jié)果。插入排序的特點在于，我們每次遍歷，主索引之前的元素都是已經(jīng)排好序的，我們找到比主索引指向元素的值大的第一個元素的位置，然后將主索引指向位置的元素插入到該位置，將該位置之后一直到主索引位置的元素依次向后挪動。這樣的方法，使得挪動的次數(shù)相對較多，如果對于排序數(shù)據(jù)量較大，挪動成本較高的情況時，這種排序算法顯然成本較高，時間復雜度相對較差，是初等通用排序算法中的一種。選擇排序：選擇排序相對插入排序，是插入排序的一個優(yōu)化，優(yōu)化的前提是我們認為數(shù)據(jù)是比較大的，挪動數(shù)據(jù)的代

4、價比數(shù)據(jù)比較的代價大很多，所以我們選擇排序是追求少挪動，以比較次數(shù)換取挪動次數(shù)。首先，我們定義我們需要排序的數(shù)組，得到數(shù)組的長度，定義一個結(jié)果數(shù)組，用來存放排好序的數(shù)組，定義一個最小值，定義一個最小值的位置。然后，進入我們的遍歷，每次進入遍歷的時候我們都使得當前的最小值為9999，即認為每次最小值都是最大的數(shù)，用來進行和其他元素比較得到最小值，每次認為最小值的位置都是0，用來重新記錄最小值的位置。然后，進入第二層循環(huán)，進行數(shù)值的比較，如果數(shù)組中的某個元素的值比最小值小，那么將當前的最小值設為元素的值，然后記錄下來元素的位置，這樣，當跳出循環(huán)體的時候，我們會得到要排序數(shù)組中的最小值，然后將最小值

5、位置的數(shù)值設置為9999,即我們得到了最小值之后，就讓數(shù)組中的這個數(shù)成為最大值，然后將結(jié)果數(shù)組results第主索引值位置上的元素賦值為最小值，進行下一次外層循環(huán)重復上面的工作。最終我們就得到了排好序的結(jié)果數(shù)組result。選擇排序的優(yōu)勢在于，我們挪動元素的次數(shù)很少，只是每次對要排序的數(shù)組進行整體遍歷，找到其中的最小的元素，然后將改元素的值放到一個新的結(jié)果數(shù)組中去，這樣大大減少了挪動的次序，即我們要排序的數(shù)組有多少元素，我們就挪動多少次，而因為每次都要對數(shù)組的所有元素進行遍歷，那么比較的次數(shù)就比較多，達到了n2次，所以，我們使用選擇排序的前提是，認為挪動元素要比比較元素的成本高出很多的時候。他

6、相對與插入排序，他的比較次數(shù)大于插入排序的次數(shù)，而挪動次數(shù)就很少，元素有多少個，挪動次數(shù)就是多少個。希爾排序：首先，我們定義一個要排序的數(shù)組，然后定義一個步長的數(shù)組，該步長數(shù)組是由一組特定的數(shù)字組成的，步長數(shù)組具體得到過程我們不去考慮，是由科學家經(jīng)過很長時間計算得到的，已經(jīng)根據(jù)時間復雜度的要求，得到了最適合希爾排序的一組步長值以及計算步長值的公式，我們這里直接拿來使用。然后根據(jù)要排序的數(shù)組的長度，選擇比長度小的最大的步長值，作為我們開始的步長。然后，進入循環(huán)遍歷，外層循環(huán)由步長值決定，直到步長為1時，我們就可以精確比較每一個數(shù)值，所以外層循環(huán)最終當步長為1時，我們就將得到排序后的結(jié)果。然后，進

7、入內(nèi)層循環(huán)，內(nèi)層循環(huán)從步長那個位置開始遍歷，先記錄下步長值位置的數(shù)值，啟動副索引j,然后比較步長值位置的元素的值與減去步長值位置元素的值，如果減去步長值處元素的值大于步長值位置的元素的值，那么，我們將減去步長值處的元素挪到步長值位置處，將副索引指向前一個步長值處然后再判斷前一步長值與再前一步長值之間的大小關系，重復上面的工作；如果前一步長值處元素的數(shù)值不比步長值處元素的數(shù)值大，那么將剛才記錄下的數(shù)值，放在目前j索引位置處。重復上面的步驟，直到遍歷到我們的最后一個元素，然后將步長值減小到下一級步長。最終，當我們的步長值為1的遍歷全部結(jié)束后，我們就得到了最終排序好的數(shù)組。希爾排序算法是初等排序算法

8、向高等排序算法過度的一個中間排序算法，他的時間復雜度相比初等排序有很大的提升，達到了0(1.3)。而且希爾排序的穩(wěn)定性也很好，如果給一個排好序的數(shù)組，希爾排序?qū)贿M行數(shù)據(jù)的比較，不需要進行挪動，直接將結(jié)果返回，所以希爾排序在我們實際的應用當中還是比較值得推薦的。而且，科學家也已經(jīng)為我們計算出了非常合適的步長值以及計算步長值的公式，我們直接可以使用，使得我們的算法開發(fā)也非常容易。歸并排序：首先，我們定義一個要排序的數(shù)組，得到數(shù)組的頭下標top,得到數(shù)組的末尾下標bottom。然后，通過top和bottom得到數(shù)組的中間元素的下標middle，將數(shù)組人為的分成兩半，即前半部分和后半部分。然后，遞

9、歸調(diào)用算法，重復上面的過程，直到top=bottom，即分到前半部分和后半部分只剩下一個元素的時候，調(diào)用Merge函數(shù)，進行真正意義上的排序算法。然后，進入Merge函數(shù)：首先定義一個tempa的數(shù)組，用來臨時存放要排序的數(shù)組，然后進入一個循環(huán)，當左面索引的值小于等于中間索引值，即當前半部分的數(shù)字還沒有遍歷完成，且當右面索引的值小于等于末尾索引值，即當后半部分也有數(shù)字沒有遍歷完成時，進行遍歷，遍歷時，判斷左面索引處的數(shù)字的值的大小是否小于或等于右面索引位置數(shù)字的值，如果小于，那么，將左面索引位置的元素放進tempa數(shù)組中，將左索引加1繼續(xù)判斷是否進行再次遍歷；否則，將右面索引位置的元素放進te

10、mpa數(shù)組中，將右索引加1繼續(xù)判斷是否進行再次遍歷。直到這個循環(huán)結(jié)束。這時，我們將兩個元素中，小的元素放在了tempa數(shù)組中，但是這時我們的左索引或是右索引可能還沒有到達中間處或是末尾處，即還沒有遍歷完成所有的這兩個元素，但是有一面(或是前半部分或是后半部分)已經(jīng)遍歷完成。那么我們需要判斷這時的左索引是否小于或等于了中間值，如果是，那么將begin賦值為做索引，end賦值為中間值；否則，將begin賦值為右索引，將end賦值為末尾值。然后將所有begin和end之間的數(shù)字追加到tempa中，這時，tempa中的所有元素都排序成功。最后，將tempa中的所有元素重新放回array數(shù)組中的相應位置

11、。這次Merge排序就結(jié)束了，然后返回遞歸的調(diào)用處，進行下次的遞歸調(diào)用和Merge函數(shù)。重復上面所有的工作，最終我們可以得到排序成功的array數(shù)組。歸并排序相比與初等排序，其優(yōu)勢在于，我們使用了分而治之(Divide-and-Conquer)的思想，將復雜的問題細化，先小方面進行排序，然后將排好序的元素合并在一起，再進行大方面的排序，這樣就使我們的整體算法挪動次數(shù)變小，使整體的時間復雜度降低，優(yōu)化了排序的次數(shù)。比起低等排序，如果要排序的數(shù)據(jù)量很大的時候，會明顯體現(xiàn)出歸并排序的優(yōu)勢?？焖倥判颍合啾扔跉w并排序，快速排序是歸并排序的一個優(yōu)化。它可以有效減少挪動的次數(shù)，因為它每次遞歸調(diào)用的時候，都是

12、將第一個數(shù)字當做pivot，然后根據(jù)這個pivot，將數(shù)組分成比pivot大和比pivot小的兩個部分，然后進入排序階段，最后遞歸調(diào)用快速排序的算法，最終便得到了我們的排序結(jié)果。排序算法階段：首先判斷這次遞歸傳進來的top值和bottom值，如果top值比bottom值大，或是相等，那么說明我們的遞歸已經(jīng)到了最底層，已經(jīng)將前、后兩個部分的元素分成了只剩下各一個元素，則我們將退出本次遞歸調(diào)用，返回到上次調(diào)用的地方向下執(zhí)行;否則,進入排序階段。首先，開啟主索引i=top+l開始，到bottom結(jié)束，如果我們的第i個元素比pivot大，那么就將其追加放入big數(shù)組中，否則，將其追加放入small數(shù)組

13、中。循環(huán)結(jié)束后，我們開始將分好的兩個數(shù)組分別返回到要排序的數(shù)組array的相應位置處，進行拼接。這里注意：在拼接的過程中，不要忘記為ivot預留中間一個位置，然后將pivot的值放到array中間的位置處。然后遞歸調(diào)用下次的快速排序函數(shù)。而再一次的調(diào)用會將上次調(diào)用函數(shù)的時候，得到的比pivot小的部分進行排序，同樣使得第一個元素成為新的pivot，再次將數(shù)組分成大、小兩個部分。繼續(xù)上面同樣的工作，我們最終會分成每個部分只有一個元素，這時再次調(diào)用排序后，就得到了排序完成的兩個元素，然后經(jīng)過不斷的返回到遞歸調(diào)用，將會不斷的使小半部分的數(shù)組慢慢排序成功，然后進行第二部分的排序。同理，當最終所有的遞歸

14、調(diào)用都結(jié)束之后，我們會得到最終排序的結(jié)果?？焖倥判蛩惴ǖ膬?yōu)勢在于，他同樣也是分而治之(Divide-and-Conquer)的思想，巧妙之處在于,他每次分的時候已經(jīng)實際意義上的將數(shù)組大小兩個部分分好了，在遞歸回歸的時候，相對拼接數(shù)組就十分簡單。而歸并排序在拼接數(shù)組的時候還需要將兩部分數(shù)組進行比較，進行排序，這樣使得我們挪動的次數(shù)就少了很多。但是，它也有不好用的時候，如果給你一個已經(jīng)排好序的數(shù)組，那么它每次遞歸調(diào)用的時候，分開的兩部分中，比pivot小的部分元素的個數(shù)為0,而比pivot大的部分元素的個數(shù)為當次調(diào)用遞歸傳進來的數(shù)組長度減1的長度。所以需要的時間復雜度反而會增加。所以快速排序用在一

15、個很隨即的數(shù)組中時，一般會發(fā)揮比較好的性能。二、算法流程圖1下面給出插入排序的算法流程圖：遍歷整個數(shù)組：i將最小億min賦值丸-SSSSj即每次遍歷開始時都無最小值啟動副索引，遍歷整個數(shù)組：i*須斷副索引元素買r是否比最小值小_一將當前最小值賦值丸副索引位置元素的值，并記錄出現(xiàn)最小值的位置直到副循環(huán)結(jié)束，得到數(shù)組中的最小9999,值和位置，將最小值位置元素賦值為排序嚥程圖組中I說明：圖2是選擇排序算法的流程圖，體現(xiàn)了選擇排序的整體算法核心思想。其中，每次副循環(huán)我們都可以得到當前數(shù)組中的最小的元素的數(shù)值和位置，然后將每次得到最小的元素值追加到結(jié)果數(shù)組中，然后將最小元素的值賦值為最大值。得到比數(shù)組

16、長度小的，最大的步長值的下標k- #- #-啟動主循環(huán)，由步長值數(shù)組的下標1控制圖3希爾排序算法流稈圖說明：圖3是希爾排序算法的流程圖，有指明回到由k控制的主循環(huán)，當副循環(huán)遍鹽痔的整體算法核心思想。其中，沒數(shù)組的最后一個元素時，執(zhí)行完后面的大的- #-判斷之后，會回去主循環(huán)，得到新的比上次循環(huán)小的步長值。- -OO圖4歸并排序算法流程圖說明：圖4是歸并排序?qū)Ｋ惴ǖ牧鞒虉D，糠現(xiàn)了歸并排序的整體算法核丿前半部分和后半部分兩次遞歸調(diào)用，本與本圖思想基本相同，且調(diào)用Mrge心思想。其中，有思想R次調(diào)用的思想過多贅述的核心思- -定義一個比pivot小的數(shù)組，以屋個比pit大的數(shù)組，并將當前的array

17、的2口處設為pivot值從傳進來的wp點處開aril始遍歷，至（Jboltam處a斷第i個元素的li暑pivaVj_-1假11將第i個元素追加將第i個元素追加到犬兀素數(shù)組中到小兀素數(shù)組中重新走向arraylnd&x然后將小數(shù)組“大數(shù)組所有元素啟入日洱數(shù)組相應位置衆(zhòng)瀬速排序算法流程圖下次排序說明：圖5是快速排序算法的流程圖，體現(xiàn)了快速排序的整體算法核心思想。其中，當進入函數(shù)體之后，主要的拆分數(shù)組的工作是由top和bottom值來控制的，每次遞歸調(diào)用都根據(jù)當時的top和bottom值來取得pivot值和分開大小兩部分數(shù)組。三、源代碼下面給出的是整個程序的源代碼，五種排序算法寫在了一個程序里面。其中

18、，包括一個PrintArray的函數(shù)，用來打印整個數(shù)組，然后，除了一個主函數(shù)之外，還有其他的6個函數(shù)，分別是那5種排序算法，都有注釋標示著。主函數(shù)中，外層循環(huán)一共執(zhí)行四次，分別是讓5種排序算法執(zhí)行排序4組不同的數(shù)據(jù)。4組數(shù)據(jù)分別是：第一組為隨機數(shù)組，第二組為正序排好的數(shù)組，第三組為倒序排好的數(shù)組，最后一組為前半部分為正序排好的數(shù)組，后半部分為倒序排好的數(shù)組。這樣的選擇有利于將所有的情況都能基本覆蓋到，可以充分觀察出每種排序算法的性能和穩(wěn)定性。運行結(jié)果中會有分析說明。#includestdio.h#includestdlib.h#includetime.hintcompareCount=0,mo

19、veCount=0;/*compareCount-記錄比較次數(shù)，moveCount-用來記錄挪動次數(shù)*/voidPrintArray(intarray,intlength)/*打印數(shù)組的函數(shù)*/inti=0;/*用來控制打印的循環(huán)變量*/for(i=O;ilength;i+)/*length為數(shù)組的長度*/if(arrayi=9999|arrayi=0)/*如果數(shù)組中的元素的值為9999或0*/printf(NN);/*輸出一個NN標記*/continue;/*不再向下判斷*/if(arrayi10)/*如果數(shù)組中數(shù)字為個位數(shù)*/printf(%d,arrayi);/*打印出數(shù)字之后再加3個空

20、格*/elseif(arrayi100)/*如果數(shù)組中的數(shù)字為兩位數(shù)*/printf(%d,arrayi);/*打印出數(shù)字之后再加2個空格*/else/*如果數(shù)字為三位數(shù)*/printf(%d,arrayi);/*打印出數(shù)字之后再加1個空格*/voidInsertSort(intarray,intlength)/*插入排序*/intj=O,curr,currData,insertIndex;/*j-循環(huán)變量，curr當前的數(shù)組下表，currData-當前數(shù)組元素的數(shù)值，insertindex-要插入新元素的位置*/for(curr=1;currlength;curr+)/*外層循環(huán)，用來遍歷整

21、個數(shù)組*/insertIndex=-1;/*每次遍歷向后移動時，都認為當前要插入的位置為-1，即不變*/for(j=0;jarraycurr)/*如果副索引遍歷到的元素的值比主索引位置元素的值大*/insertIndex=j;/*將要插入的位置記錄為當前副索引的位置*/compareCount+;/*增加一次比較的次數(shù)*/break;/*副索引不再向后判斷，因為主索引前面的所有元素都是已經(jīng)排好序的*/compareCount+;/*增加一次比較的次數(shù)*/if(insertIndex=-1)/*如果要插入的位置為-1，說明主索引前面的元素沒有比主索引位置元素值大的元素*/continue;/*主

22、索引向后移動*/elsecurrData=arraycurr;/*如果要插入的位置不為-1，說明要將主索引位置的元素向前插，那么先記錄主索引位置元素的值*/for(j=curr;j=insertIndex+1;j-)/*啟動循環(huán)，開始從主索引位置向前一個一個元素向后挪*/arrayj=arrayj-1;/*前一元素挪到后一元素位置*/moveCount+;/*增加挪動次數(shù)*/arrayinsertIndex=currData;/*最終將主索引位置的元素插入到要插入的位置處*/voidSelectionSort(intarray,intlength)/*選擇排序*/intresult100=0;

23、/*定義結(jié)果數(shù)組，用來存放最終排序完成的結(jié)果*/inti=O,j=O,min,minIndex;/*i-主循環(huán)控制變量，j-副循環(huán)控制變量，min-記錄最小值，minlndex-記錄最小值的位置*/for(i=0;ilength;i+)/*啟動主循環(huán)，使得每次得到一個最小值*/min=9999;/*初始化的最小值為9999，即為最大值*/minIndex=O;/*初始化的最小值的*/for(j=0;jlength;j+)/*啟動副循環(huán)，得到當前數(shù)組當做的最小值*/if(arrayjmin)/*如果有數(shù)據(jù)比最小值小*/min=arrayj;/*將最小值重新定位為新的最小值*/minIndex=j

24、;/*記錄下來最小值的位置*/compareCount+;arrayminIndex=9999;/*將最小值位置處設置為最大值。*/resulti=min;/*將最小值追加到結(jié)果數(shù)組中*/moveCount+;voidShellSort(intarray,intlength)/*希爾排序*/intgaps=l,5,13,43,113,297,815,1989;/*定義步長數(shù)組，步長數(shù)組是科學家為我們計算好的*/inti,j,k;/*定義循環(huán)控制變量*/intgap;/*定義單個步長值*/inttemp;/*定義臨時使用的數(shù)值*/for(k=0;gapsk=0)/*通過下標來控制循環(huán)*/gap=

25、gapsk;/*得到步長值*/for(i=gap;i=gap&arrayj-gaptemp)/*如果j的值大于等于步長值且j前一步長值處的值比j處的值大*/arrayj=arrayj-gap;/*將j前一步長值處元素放到j處*/j=j-gap;/*重新定向j*/moveCount+;arrayj=temp;/*將記錄下來的temp值放在j處*/compareCount+;voidMerge(intarray,inttop,intmiddle,intbottom,intlength)/*歸并排序的排序算法*/inttempa100=0;/*定義一個tempa的數(shù)組，用來記錄單次調(diào)用本函數(shù)時得到排

26、序好的數(shù)組*/intleft=top;/*left-左半部分索引的位置*/intright=middle+l;/*right-右半部分的位置*/inttempIndex=O;/*控制tempa數(shù)組的下標*/intbegin=0,end=0;/*用來記錄沒有遍歷到的數(shù)據(jù)的開始和結(jié)束位置*/inti,j;while(left=middle&right=bottom)/*遍歷前后兩個半部分*/if(arrayleft=arrayright)/*如果前半部分的left處的值小于后半部分right處的值*/tempatempIndex=arrayleft;/*將left處的元素追加到tempa數(shù)組中*/

27、left+;/*重定向left*/elsetempatempIndex=arrayright;/*否則，將right處的元素追加到tempa數(shù)組中*/right+;/*重定向right*/tempIndex+;/*完成追加工作，將tempa下標向后移動*/compareCount+;begin=0;/*單次調(diào)用Merge的時候，將begin賦值為0*/end=0;if(left=middle)/*如果上半部分還沒有遍歷完元素*/begin=left;/*得到當前上半部分遍歷到的元素的下標*/end=middle;/*將中間值賦值給end*/elsebegin=right;/*否則，得到下半部分

28、遍歷到的元素的下標*/end=bottom;/*將末尾值賦值費end*/for(i=begin;i=end;i+)/*從begin處開始遍歷到end處*/tempatempIndex=arrayi;/*將主循環(huán)沒有遍歷到的元素依次追加到tempa中*/tempIndex+;moveCount+;for(i=top,j=0;i=bottom;i+,j+)/*上面的工作全部結(jié)束后，將排好序的數(shù)組返回給array*/arrayi=tempaj;/*相應array位置賦值為排好序的tempa位置的值*/moveCount+;voidMergeSort(intarray,inttop,intbottom

29、,intlevel,intlength)/*歸并排序*/if(top=bottom)return;/*如果當前的top值大于bottom值的話，那么退出函數(shù)返回遞歸調(diào)用處*/for(i=top+1;i=pivot)/*如果第i個元素的值大于pivot*/bigbigindex=arrayi;/*將該元素追加到大元素數(shù)組中*/bigIndex+;/*重定向大數(shù)組索引*/elsesmallsmallindex=arrayi;/*否則，將該元素追加到小元素數(shù)組中*/smallIndex+;/*重定向小數(shù)組索引*/compareCount+;arrayIndex=0;/*每單次調(diào)用函數(shù)時，重新定位ar

30、rayindex索引*/for(i=0;ismallindex;i+)/*遍歷所有小索引的數(shù)字*/arrayarrayindex+top=smalli;/*往top處開始一個個的追加較小的數(shù)*/arrayindex+;moveCount+;arrayarrayIndex+top=pivot;/*空出一位放pivot*/arrayIndex+;for(i=0;ibiglndex;i+)/*遍歷所有大索引的數(shù)字*/arrayarraylndex+top=bigi;/*將大的數(shù)字主鍵到當前array+top處*/arrayIndex+;moveCount+;QuickSort(array,top,t

31、op+smallIndex-l,level+l,length);/*遞歸調(diào)用快速排序*/QuickSort(array,top+smallIndex+1,bottom,level+1,length);voidmain()intarray_Al00,array_Bl00,array_Cl00,array_Dl00,array_El00;/*定義五個數(shù)組，用來分別讓五個算法排序*/inti,j;/*循環(huán)控制變量*/for(j=0;j4;j+)/*共產(chǎn)生4組數(shù)據(jù)*/if(j=0)/*第一次進入循環(huán)，設置第一組數(shù)據(jù)*/srand(int)time(NULL);/*設置隨即種子為當前時間值*/for(i

32、=0;il00;i+)array_Ai=array_Bi=array_Ci=array_Di=array_Ei=rand()%500+l;/*產(chǎn)生5組相同的，從1到500之間的隨機數(shù)*/if(j=1)/*第二次進入循環(huán)，設置第二組數(shù)據(jù)*/for(i=0;i100;i+)array_Ai=array_Bi=array_Ci=array_Di=array_Ei=i+1;/*產(chǎn)生5組相同的，從1到100正序排好的數(shù)組*/if(j=2)/*第三次進入循環(huán)，設置第三組數(shù)據(jù)*/for(i=0;i100;i+)array_Ai=array_Bi=array_Ci=array_Di=array_Ei=100-

33、i;/*產(chǎn)生5組相同的，從100到1倒序排好的數(shù)組*/if(j=3)/*第四次進入循環(huán)，設置第四組數(shù)據(jù)*/for(i=0;i=50;i-)array_Ai=array_Bi=array_Ci=array_Di=array_Ei=-(2*i-200+1);/*數(shù)組下標50到99的數(shù)為倒序排好的99到1的奇數(shù)*/PrintArray(array_A,100);/*排序前先打印出整個數(shù)組*/compareCount=0,moveCount=0;/*重新定向比較次數(shù)和移動次數(shù)*/InsertSort(array_A,100);/*調(diào)用插入排序，排序?qū)ο螅篴rray_A*/printf(InsertSo

34、rt:CompareCount:%dtMoveCount:%dn,compareCount,moveCount);/*輸出比較次數(shù)和移動次數(shù)*/compareCount=0,moveCount=0;/*重新定向比較次數(shù)和移動次數(shù)*/SelectionSort(array_B,100);/*調(diào)用選擇排序，排序?qū)ο螅篴rray_B*/printf(SelectSort:CompareCount:%dMoveCount:%dn,compareCount,moveCount);compareCount=0,moveCount=0;/*重新定向比較次數(shù)和移動次數(shù)*/ShellSort(array_C,1

35、00);/*調(diào)用希爾排序，排序?qū)ο螅篴rray_C*/printf(ShellSort:CompareCount:%dtMoveCount:%dn,compareCount,moveCount);compareCount=0,moveCount=0;/*重新定向比較次數(shù)和移動次數(shù)*/MergeSort(array_D,0,99,0,100);/*調(diào)用歸并排序，排序?qū)ο螅篴rray_D*/printf(MergeSort:CompareCount:%dtMoveCount:%dn,compareCount,moveCount);compareCount=0,moveCount=0;/*重新定向比

36、較次數(shù)和移動次數(shù)*/QuickSort(array_E,0,99,0,100);/*調(diào)用快速排序，排序?qū)ο螅篴rray_E*/printf(QuickSort:CompareCount:%dtMoveCount:%dn,compareCount,moveCount);getch();四、運行結(jié)果面給出程序運行的結(jié)果圖：44557338364347319365395120426262192115295854026314120丄+32562+23652044552361613735377113416744684192491544264123968213824531163332276+7579276

37、190437296984071301913+13610250+211977146339445386286381491703032344543920B47523240511931716636739161372372154062104481431+930785420499453JD:Jin-TCkprujcct3norL：di&.eie12345678g1011121314151617181920212223242526272829303132333435363738394041+243444546+74849505152535455565758596061626364656667關6970717

38、2737475767778793081828384858667888990919293949596979899100InsertSort:ConpareCount:4950MoveCount:0Count:100Count:QCount:988Count:495O:Conpare:Conpare:ConpareMoveMoveMoveMoveMoveMoveMoveMoveMoveCount:264&Count:10000Count:338Count:546Count:615Count:2396Count:100Count:372Count:798Count:615Count:10000Cou

39、nt:338Count:356Count:4950InsertSort:ConpareSelectSort:ConpareShellsortMergesortQuicksort100999897969594939291908988873685848382318079787776757473727170696S6766656463626160595857565554535251504948474645444342+14039開373635弭3332H302928272625242322212019181716151413121110987654321:Conpare:Conpare:Conpar

40、eSelectSort:ConpareShellsortMergesortQuicksortInsertSort:ConpareSelectSort:ConpareShellsort:Conpare個4950100284好的數(shù)組輸出出來，因為5Count:99Count:100005圖6MoveCountMoveCount中排序算法的運行結(jié)果圖：果，其中并沒有將排序種排序算法都將一個數(shù)組排序成一樣的結(jié)果,所以打印結(jié)果相對不那么重要。而主要是打印出了403031+11步機100時間復雜度為-步的比較，和最前面的數(shù)比較之后移動次數(shù)又是(工(1to0)。最后，一半正序一半倒序的數(shù)組時，就各取一半，各

41、是2500次。擇排序：因為選擇排序每次都是雙重循環(huán)完全遍歷數(shù)組，所以其比較次數(shù)為個數(shù)？O(n*(lni)/2)，所以其結(jié)果大致如此；后面排正序排好的數(shù)組時，主要是相當就可99)n淞的數(shù)數(shù)組，用了2648次翻和2396I處的1巒9排倒序排好所以比較次數(shù)(2=10000),而如果我們將賦值到新的結(jié)果數(shù)組中算作挪動的話，那么就是只有(n=100)次挪動。希爾排序：希爾排序相對就比較穩(wěn)定，他每次排序使用的比較次數(shù)都是相同的，都為338而挪動次數(shù)相對不是固定的，其平均復雜度為(1.3=398)，排序正序排好的數(shù)組時，希爾排序只需要進行幾次比較，不需要進行任何的挪動就原樣將數(shù)組返回了。說明其穩(wěn)定性還是比較

42、不錯的。歸并排序：歸并排序這里，我將一次賦值看作是一次挪動。歸并排序采用的是“一刀切”的辦法，所以其比較次數(shù)相對固定，每次遞歸的時候，都將數(shù)組切成兩半，直到切到不能再切得時候，進行比較，用的是分而治之(Divide-and-Conquer)的思想。而賦值次數(shù)就比較多了，因為采用了遞歸的方法，每次都將數(shù)組分為兩部分的時候，都需要不斷的追加到臨時數(shù)組tempa中，然后再返回到array數(shù)組的相應位置，所以需要來回賦值?？焖倥判颍嚎焖倥判蛳鄬捅容^不穩(wěn)定了，因為我們?nèi)藶榈膶⒚看芜f歸進來的top值處的元素設為我們的pivot，在完全隨機的數(shù)組中，他的表現(xiàn)還是比較出色的，比較次數(shù)為615,快速排序這里，每次比較之后，得到了小的和大的數(shù)組之后，會返回到array里面，所以比較的次數(shù)和返回的次數(shù)是相同的。而當我們給快速排序一個已經(jīng)排好序的數(shù)組，或是正序，或是倒序，他每次比較的時候都會將除了第一個元素之外的其余元素放在一個部分里面，所以需要不斷的遞歸來拆分數(shù)組。所以執(zhí)行的次數(shù)比較多，達到了4950次。五、遇到的問題及解決這部分我主要遇到了如下三個問題，其內(nèi)容與解決方法如下所列：插入排序時，結(jié)果中出現(xiàn)了一串相同的數(shù)字在編寫插入排序的時候，在運行