幾種排序算法的分析與比較--C語(yǔ)言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、隨即的數(shù)組中時(shí)，一般會(huì)發(fā)揮比較好的性能。二、算法流程圖1.下面給出插入排序的算法流程圖:啟動(dòng)主索引curr=lin閑rtlrd最=-L認(rèn)為不用插入到前面啟動(dòng)副索引，副索弓第一個(gè)元素開(kāi)始遍歷到curr位置將inscrtindeK位置之后，到主索引位置的元素依次向后搠，將當(dāng)前主索引位置元素插入到insertlndex值位苜處圖1插入排序算法流程圖說(shuō)明：圖1是插入排序算法的流程圖，體現(xiàn)了插入排序的整體算法核心思想。其中，我們通過(guò)判斷insertIndex的值，來(lái)決定我們主索引遍歷位置的元素是否需要向前面插入，并且插入的到要插入的位置。圖2選擇排序算法流程圖說(shuō)明：圖2是選擇排序算法的流程圖，體現(xiàn)了選擇

16、排序的整體算法核心思想。其中，每次副循環(huán)我們都可以得到當(dāng)前數(shù)組中的最小的元素的數(shù)值和位置，然后將每次得到最小的元素值追加到結(jié)果數(shù)組中，然后將最小元素的值賦值為最大值。得到比數(shù)組長(zhǎng)度小的.最大的步長(zhǎng)值的下標(biāo)k啟動(dòng)主婚環(huán)，由步長(zhǎng)值數(shù)組的下標(biāo)k控制啟動(dòng)副循環(huán),從抄長(zhǎng)值處開(kāi)始遍歷下次儲(chǔ)環(huán)J記錄當(dāng)前副秦弓I的索引值上及索引位置元素值temp將第j祓步長(zhǎng)值處的元素挪到暇第j處，重新定位產(chǎn)j減步長(zhǎng)值將第j位置元素值重新賦值為temp圖3希爾排序算法流程圖說(shuō)明：圖3是希爾排序算法的流程圖，體現(xiàn)了希爾排序的整體算法核心思想。其中，沒(méi)有指明回到由k控制的主循環(huán)，當(dāng)副循環(huán)遍歷到數(shù)組的最后一個(gè)元素時(shí)，執(zhí)行完后面的大的

17、判斷之后，會(huì)回去主循環(huán)，得到新的比上次循環(huán)小的步長(zhǎng)值。循環(huán)第市后.前半部分或后半部分還會(huì)有沒(méi)有遍歷到的元素，將他們?nèi)甲芳拥解鮩pa數(shù)組中.并返回arqy數(shù):組，返回Merge調(diào)用處圖4歸并排序算法流程圖說(shuō)明：圖4是歸并排序算法的流程圖，體現(xiàn)了歸并排序的整體算法核心思想。其中，有前半部分和后半部分兩次遞歸調(diào)用，本圖只體現(xiàn)了一次調(diào)用的核心思想，另一次調(diào)用的思想與本圖思想基本相同，且調(diào)用Merge算法函數(shù)是一樣的，就沒(méi)有過(guò)多贅述。、圖5快速排序算法流程圖說(shuō)明：圖5是快速排序算法的流程圖，體現(xiàn)了快速排序的整體算法核心思想。其中，當(dāng)進(jìn)入函數(shù)體之后，主要的拆分?jǐn)?shù)組的工作是由top和bottom值來(lái)控制的

18、，每次遞歸調(diào)用都根據(jù)當(dāng)時(shí)的top和bottom值來(lái)取得pivot值和分開(kāi)大小兩部分?jǐn)?shù)組。三、源代碼下面給出的是整個(gè)程序的源代碼，五種排序算法寫(xiě)在了一個(gè)程序里面。其中，包括一個(gè)PrintArray的函數(shù)，用來(lái)打印整個(gè)數(shù)組，然后，除了一個(gè)主函數(shù)之外，還有其他的6個(gè)函數(shù)，分另是那5種排序算法，都有注釋標(biāo)示著。主函數(shù)中，外層循環(huán)一共執(zhí)行四次，分別是讓5種排序算法執(zhí)行排序4組不同的數(shù)據(jù)。4組數(shù)據(jù)分別是：第一組為隨機(jī)數(shù)組，第二組為正序排好的數(shù)組，第三組為倒序排好的數(shù)組，最后一組為前半部分為正序排好的數(shù)組，后半部分為倒序排好的數(shù)組。這樣的選擇有利于將所有的情況都能基本覆蓋到，可以充分觀察出每種排序算法的性能

19、和穩(wěn)定性。運(yùn)行結(jié)果中會(huì)有分析說(shuō)明。#include"stdio.h"#include"stdlib.h"#include"time.h"intcompareCount=0,moveCount=0;/*compareCount-記錄比較次數(shù)，moveCount-用來(lái)記錄挪動(dòng)次數(shù)*/voidPrintArray(intarray,intlength)/*打印數(shù)組的函數(shù)*/inti=0;/*用來(lái)控制打印的循環(huán)變量*/for(i=0;i<length;i+)/*length為數(shù)組的長(zhǎng)度*/if(arrayi=9999|arrayi=0)

20、/*如果數(shù)組中的元素的值為9999或0*/printf("NN");/*輸出一個(gè)NN標(biāo)記*/continue;/*不再向下判斷*/if(arrayi<10)/*如果數(shù)組中數(shù)字為個(gè)位數(shù)*/printf("%d",arrayi);/*打印出數(shù)字之后再加3個(gè)空格*/elseif(arrayi<100)/*如果數(shù)組中的數(shù)字為兩位數(shù)*/printf("%d",arrayi);/*打印出數(shù)字之后再加2個(gè)空格*/else/*如果數(shù)字為三位數(shù)*/printf("%d",arrayi);/*打印出數(shù)字之后再加1個(gè)空格*/

21、voidInsertSort(intarray,intlength)/*插入排序*/intj=0,curr,currData,insertIndex;/*j-循環(huán)變量，curr當(dāng)前的數(shù)組下表，currData-當(dāng)前數(shù)組元素的數(shù)值,insertindex-要插入新元素的位置*/for(curr=1;curr<length;curr+)/*外層循環(huán)，用來(lái)遍歷整個(gè)數(shù)組*/(insertIndex=-1;/*每次遍歷向后移動(dòng)時(shí)，都認(rèn)為當(dāng)前要插入的位置為-1,即不變*/for(j=0;j<curr;j+)/*內(nèi)層循環(huán)，用來(lái)查看當(dāng)前數(shù)組元素的數(shù)值是否比前面的已經(jīng)排好的數(shù)組元素?cái)?shù)值小*/(if(

22、arrayj>arraycurr)/*如果副索引遍歷到的元素的值比主索引位置元素的值大*/(insertindex=j;/*將要插入的位置記錄為當(dāng)前副索引的位置*/compareCount+;/*增力口一次比較的次數(shù)*/break;/*副索引不再向后判斷，因?yàn)橹魉饕懊娴乃性囟际且呀?jīng)排好序的*/)compareCount+;/*增力口次比較的次數(shù)*/)if(insertindex=-1)/*如果要插入的位置為-1,說(shuō)明主索引前面的元素沒(méi)有比主索引位置元素值大的元素*/(continue;/*主索引向后移動(dòng)*/)else(currData=arraycurr;/*如果要插入的位置不為-

23、1,說(shuō)明要將主索引位置的元素向前插，那么先記錄主索引位置元素的值*/for(j=curr;j>=insertindex+1;j-)/*啟動(dòng)循環(huán)，開(kāi)始從主索引位置向前一個(gè)一個(gè)元素向后挪*/(arrayj=arrayj-1;/*前一元素挪到后一元素位置*/moveCount+;/*增加挪動(dòng)次數(shù)*/)arrayinsertindex=currData;/*最終將主索引位置的元素插入到要插入的位置處*/)voidSelectionSort(intarray,intlength)/*選擇排序*/(intresult100=0;/*定義結(jié)果數(shù)組，用來(lái)存放最終排序完成的結(jié)果*/inti=0,j=0,m

24、in,minindex;/*i-主循環(huán)控制變量，j-副循環(huán)控制變量，min-記錄最小值，minindex-記錄最小值的位置*/for(i=0;i<length;i+)/*啟動(dòng)主循環(huán)，使得每次得到一個(gè)最小值*/min=9999;/*初始化的最小值為9999,即為最大值*/minlndex=0;/*初始化的最小值的*/for(j=0;j<length;j+)/*啟動(dòng)副循環(huán)，得到當(dāng)前數(shù)組當(dāng)做的最小值*/(if(arrayj<min)/*如果有數(shù)據(jù)比最小值小*/(min=arrayj;/*將最小值重新定位為新的最小值*/minIndex=j;/*記錄下來(lái)最小值的位置*/compare

25、Count+;arrayminIndex=9999;/*將最小值位置處設(shè)置為最大值。*/resulti=min;/*將最小值追加到結(jié)果數(shù)組中*/moveCount+;voidShellSort(intarray,intlength)/*希爾排序*/(intgaps=1,5,13,43,113,297,815,1989;/*定義步長(zhǎng)數(shù)組，步長(zhǎng)數(shù)組是科學(xué)家為我們計(jì)算好的*/inti,j,k;/*定義循環(huán)才$制變量*/intgap;/*定義單個(gè)步長(zhǎng)值*/inttemp;/*定義臨時(shí)使用的數(shù)值*/for(k=0;gapsk<length;k+);/*得到比數(shù)組長(zhǎng)度小的，最大的步長(zhǎng)值的下標(biāo)*/wh

26、ile(-k>=0)/*通過(guò)下標(biāo)來(lái)控制循環(huán)*/gap=gapsk;/*得到步長(zhǎng)值*/for(i=gap;i<length;i+)/*從步長(zhǎng)值處開(kāi)始相后遍歷*/temp=arrayi;/*首先記錄下i處的元素值*/j=i;/*啟動(dòng)副循環(huán)*/while(j>=gap&&arrayj-gap>temp)/*如果j的值大于等于步長(zhǎng)值且j前一步長(zhǎng)值處的值比j處的值大*/arrayj=arrayj-gap;/*將j前一步長(zhǎng)值處元素放到j(luò)處*/j=j-gap;/*重新定向j*/moveCount+;arrayj=temp;/*將記錄下來(lái)的temp值放在j處*/comp

27、areCount+;voidMerge(intarray,inttop,intmiddle,intbottom,intlength)/*歸并排序的排序算法*/(inttempa100=0;/*定義一個(gè)tempa的數(shù)組，用來(lái)記錄單次調(diào)用本函數(shù)時(shí)得到排序好的數(shù)組*/intleft=top;/*left-左半部分索引的位置*/intright=middle+1;/*right-右半部分的位置*/inttempIndex=0;/*控制tempa數(shù)組的下標(biāo)*/intbegin=0,end=0;/*用來(lái)記錄沒(méi)有遍歷到的數(shù)據(jù)的開(kāi)始和結(jié)束位置*/inti,j;while(left<=middle&

28、;&right<=bottom)/*遍歷前后兩個(gè)半部分*/if(arrayleft<=arrayright)/*如果前半部分的left處的值小于后半部分right處的值*/tempatempIndex=arrayleft;/*將left處的元素追加到tempa數(shù)組中*/left+;/*重定向left*/elsetempatempIndex=arrayright;/*否貝U,將right處的元素追加到tempa數(shù)組中*/right+;/*重定向right*/tempIndex+;/*完成追加工作，將tempa下標(biāo)向后移動(dòng)*/compareCount+;begin=0;/*單次

29、調(diào)用Merge的時(shí)候，將begin賦值為0*/end=0;if(left<=middle)/*如果上半部分還沒(méi)有遍歷完元素*/begin=left;/*得到當(dāng)前上半部分遍歷到的元素的下標(biāo)*/end=middle;/*將中間值賦值給end*/elsebegin=right;/*否則，得到下半部分遍歷到的元素的下標(biāo)*/end=bottom;/*將末尾值賦值費(fèi)end*/for(i=begin;i<=end;i+)/*從begin處開(kāi)始遍歷到end處*/tempatempIndex=arrayi;/*將主循環(huán)沒(méi)有遍歷到的元素依次追加到tempa中*/tempIndex+;moveCount

30、+;for(i=top,j=0;i<=bottom;i+,j+)/*上面的工作全部結(jié)束后，將排好序的數(shù)組返回給array*/(arrayi=tempaj;/*相應(yīng)array位置賦值為排好序的tempa位置的值*/moveCount+;)voidMergeSort(intarray,inttop,intbottom,intlevel,intlength)/*歸并排序*/(if(top<bottom)/*如果分開(kāi)的兩部分的元素的頭指針小于尾值指針*/(intmiddle=(top+bottom)/2;/*得到中間值的下標(biāo)，"一刀切"*/MergeSort(array

31、,top,middle,level+1,length);/*遞歸調(diào)用上半部分*/MergeSort(array,middle+1,bottom,level+1,length);/*遞歸調(diào)用下半部分*/Merge(array,top,middle,bottom,length);/*當(dāng)遞歸回歸后，調(diào)用排序*/)voidQuickSort(intarray,inttop,intbottom,intlevel,intlength)/*快速排序*/(intbig100=0;/*定義一個(gè)比pivot大的數(shù)組*/intsmall100=0;/*定義一個(gè)比pivot小的數(shù)組*/intsmallIndex=0,

32、bigIndex=0;/*smallIndex-小數(shù)組的索引，bigIndex-大數(shù)組索引*/intpivot=arraytop;/*每次調(diào)用函數(shù)時(shí)，都將重新得到array數(shù)組第一個(gè)數(shù)做pivot*/inti=0,arrayIndex=0;if(top>=bottom)return;/*如果當(dāng)前的top值大于bottom值的話，那么退出函數(shù)返回遞歸調(diào)用處*/for(i=top+1;i<=bottom;i+)/*主循環(huán)從top+1處開(kāi)始*/if(arrayi>=pivot)/*如果第i個(gè)元素的值大于pivot*/bigbigIndex=arrayi;/*將該元素追加到大元素?cái)?shù)組

33、中*/bigIndex+;/*重定向大數(shù)組索引*/elsesmallsmallIndex=arrayi;/*否則，將該元素追加到小元素?cái)?shù)組中*/smallIndex+;/*重定向小數(shù)組索引*/compareCount+;arrayIndex=0;/*每單次調(diào)用函數(shù)時(shí)，重新定位arrayIndex索引*/for(i=0;i<smallIndex;i+)/*遍歷所有小索引的數(shù)字*/arrayarrayIndex+top=smalli;/*往top處開(kāi)始一個(gè)個(gè)的追加較小的數(shù)*/arrayIndex+;moveCount+;)arrayarrayIndex+top=pivot;/*空出一位放pi

34、vot*/arrayIndex+;for(i=0;i<bigIndex;i+)/*遍歷所有大索引的數(shù)字*/arrayarrayIndex+top=bigi;/*將大的數(shù)字主鍵到當(dāng)前array+top處*/arrayIndex+;moveCount+;)QuickSort(array,top,top+sma111ndex-1,level+1,length);/*遞歸調(diào)用快速排序*/QuickSort(array,top+sma111ndex+1,bottom,level+1,length);)voidmain()intarray_A100,array_B100,array_C100,arr

35、ay_D100,array_E100;/*定義五個(gè)數(shù)組，用來(lái)分別讓五個(gè)算法排序*/inti,j;/*循環(huán)控制變量*/for(j=0;j<4;j+)/*一共產(chǎn)生4組數(shù)據(jù)*/if(j=0)/*第一次進(jìn)入循環(huán)，設(shè)置第一組數(shù)據(jù)*/srand(int)time(NULL);/*設(shè)置隨即種子為當(dāng)前時(shí)間值*/for(i=0;i<100;i+)array_Ai=array_Bi=array_Ci=array_Di=array_Ei=rand()%500+1;/*產(chǎn)生5組相同的，從1到500之間的F1機(jī)數(shù)*/)if(j=1)/*第二次進(jìn)入循環(huán)，設(shè)置第二組數(shù)據(jù)*/for(i=0;i<100;i+

36、)array_Ai=array_Bi=array_Ci=array_Di=array_Ei=i+1;/*產(chǎn)生5組相同的，從1到100正序排好的數(shù)組*/)if(j=2)/*第三次進(jìn)入循環(huán)，設(shè)置第三組數(shù)據(jù)*/for(i=0;i<100;i+)array_Ai=array_Bi=array_Ci=array_Di=array_Ei=100-i;/*產(chǎn)生5組相同的，從100到1倒序排好的數(shù)組*/)if(j=3)/*第四次進(jìn)入循環(huán)，設(shè)置第四組數(shù)據(jù)*/(for(i=0;i<50;i+)(array_Ai=array_Bi=array_Ci=array_Di=array_Ei=2*(i+1);/

37、*數(shù)組下標(biāo)0至U49的數(shù)為正序排好的2到100的偶數(shù)*/)for(i=99;i>=50;i-)(array_Ai=array_Bi=array_Ci=array_Di=array_Ei=-(2*i-200+1);/*數(shù)組下標(biāo)50到99的數(shù)為倒序排好的99到1的奇數(shù)*/)PrintArray(array_A,100);/*排序前先打印出整個(gè)數(shù)組*/compareCount=0,moveCount=0;/*重新定向比較次數(shù)和移動(dòng)次數(shù)*/InsertSort(array_A,100);/*調(diào)用插入排序，排序?qū)ο螅篴rray_A*/printf("InsertSort:CompareC

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

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

40、pareCount=0,moveCount=0;/*重新定向比較次數(shù)和移動(dòng)次數(shù)*/QuickSort(array_E,0,99,0,100);/*調(diào)用快速排序，排序?qū)ο螅篴rray_E*/printf("QuickSort:CompareCount:%dtMoveCount:%dn",compareCount,moveCount);)getch();)四、運(yùn)行結(jié)果下面給出程序運(yùn)行的結(jié)果圖：05295nehe-u1113,84441ssMQ124609352694329344414ss2ek222246248761305541233468665393732314o4C4244

41、464362234fl125636936163217155776-51913431394519T0-42T322417&54530036154sun七二264gCount:10000Count:338count:546Count1615678012372836611343lshMeIQUllol8ol6ol4ol2ok4CCS2248444S6648884877735s733373262728+647486667688687&8Count:49soCount:1D00DCount:338Count:356Count:495095949375747355S453353433151

42、4-13Count:49Count:10000Count:”3Count:316Count121+IC52545692949G696765292725Count:2500Count:1QQ0QCount:338Count:385Count:2S0099999246822222&75318B83M159B2ea5546Do5961581173eerroa事1eeeFFr6666aaa9753ppp0-0000135791111197531ooO1126162-4262621921153735M77113276475792763944533639161372372MoveCount;23S

43、6Hov«Count:100MoveCount:372MoveCOUrtt；793MoveCount:6151112131431323334515253547172737491929394Movecount:0Movecount:100MoveCount:。HoveCount：983MoveCount:4950903988fl770696367504943473029282710987MoveCount:49SDMovecount:100Movecount:2B4Movecount:1D2SMoveCount;4950222+2G2&826466689937959359575

44、55m19171513IMevecount:2500MoveCount:100Hovecount:232MoveCountMdv«Count：250Q87414543407$6442120&971&6Q02493+618049832431140Z44g7111141Z534404059135513772400575S57776&0Q95911Q0&5S55A4&164264244464211113795100111378492299M7847447737&+566S54S8410011工圖6五種排序算法的運(yùn)行結(jié)果圖說(shuō)明：本運(yùn)行圖是整個(gè)程

45、序運(yùn)行的結(jié)果，其中并沒(méi)有將排序好的數(shù)組輸出出來(lái)，因?yàn)?種排序算法都將一個(gè)數(shù)組排序成一樣的結(jié)果，所以打印結(jié)果相對(duì)不那么重要。而主要是打印出了每種算法對(duì)不同數(shù)組的排序所需要的比較次數(shù)和移動(dòng)次數(shù)。分析：插入排序：插入排序時(shí)初等排序的一種，所以其時(shí)間復(fù)雜度相對(duì)較大，隨機(jī)100個(gè)數(shù)據(jù)的數(shù)組，用了2648次比較和2396次移動(dòng)，總數(shù)達(dá)到了5044,因?yàn)槠鋾r(shí)間復(fù)雜度為O(n*(n-1)/2),所以其結(jié)果大致如此；后面排正序排好的數(shù)組時(shí)，主要是一步一步的比較，相當(dāng)于比較次數(shù)為(匯(1to99)n=4950);排倒序排好的數(shù)組時(shí)，每次和最前面的數(shù)比較之后就可以將主索引處的元素插入到前面，所以比較次數(shù)為99次，而

46、移動(dòng)次數(shù)又是(匯(1to99)n=4950)。最后，一半正序一半倒序的數(shù)組時(shí)，就各取一半，各是2500次。選擇排序：因?yàn)檫x擇排序每次都是雙重循環(huán)完全遍歷數(shù)組，所以其比較次數(shù)為(nA2=10000),而如果我們將賦值到新的結(jié)果數(shù)組中算作挪動(dòng)的話，那么就是只有(n=100)次挪動(dòng)。希爾排序：希爾排序相對(duì)就比較穩(wěn)定，他每次排序使用的比較次數(shù)都是相同的，都為338而挪動(dòng)次數(shù)相對(duì)不是固定的，其平均復(fù)雜度為(門人1.3=398),排序正序排好的數(shù)組時(shí)，希爾排序只需要進(jìn)行幾次比較，不需要進(jìn)行任何的挪動(dòng)就原樣將數(shù)組返回了。說(shuō)明其穩(wěn)定性還是比較不錯(cuò)的。歸并排序：歸并排序這里，我將一次賦值看作是一次挪動(dòng)。歸并排序

47、采用的是“一刀切”的辦法，所以其比較次數(shù)相對(duì)固定，每次遞歸的時(shí)候，都將數(shù)組切成兩半，直到切到不能再切得時(shí)候，進(jìn)行比較，用的是分而治之(Divide-and-Conquer)的思想。而賦值次數(shù)就比較多了，因?yàn)椴捎昧诉f歸的方法，每次都將數(shù)組分為兩部分的時(shí)候，都需要不斷的追加到臨時(shí)數(shù)組tempa中，然后再返回到array數(shù)組的相應(yīng)位置，所以需要來(lái)回賦值?？焖倥判颍嚎焖倥判蛳鄬?duì)就比較不穩(wěn)定了，因?yàn)槲覀內(nèi)藶榈膶⒚看芜f歸進(jìn)來(lái)的top值處的元素設(shè)為我們的pivot,在完全隨機(jī)的數(shù)組中，他的表現(xiàn)還是比較出色的，比較次數(shù)為615,快速排序這里，每次比較之后，得到了小的和大的數(shù)組之后，會(huì)返回到array里面，所以比較的次數(shù)和返回的次數(shù)是相同的。而當(dāng)我們給快速排序一個(gè)已經(jīng)排好序的數(shù)組，或是正序，或是倒序，他每