排序算法實(shí)驗(yàn)報(bào)告參考模板

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告八種排序算法實(shí)驗(yàn)報(bào)告一、 實(shí)驗(yàn)內(nèi)容編寫(xiě)關(guān)于八種排序算法的C語(yǔ)言程序，要求包含直接插入排序、希爾排序、簡(jiǎn)單選擇排序、堆排序、冒泡排序、快速排序、歸并排序和基數(shù)排序。二、 實(shí)驗(yàn)步驟 各種內(nèi)部排序算法的比較：1. 八種排序算法的復(fù)雜度分析（時(shí)間與空間）。2. 八種排序算法的C語(yǔ)言編程實(shí)現(xiàn)。3. 八種排序算法的比較，包括比較次數(shù)、移動(dòng)次數(shù)。三、 穩(wěn)定性，時(shí)間復(fù)雜度和空間復(fù)雜度分析比較時(shí)間復(fù)雜度函數(shù)的情況：1 / 23時(shí)間復(fù)雜度函數(shù)O(n)的增長(zhǎng)情況所以對(duì)n較大的排序記錄。一般的選擇都是時(shí)間復(fù)雜度為O(nlog2n)的排序方法。時(shí)間復(fù)雜度來(lái)說(shuō)：(1)平方階(O(n2)排序 各類簡(jiǎn)單排序:

2、直接插入、直接選擇和冒泡排序； (2)線性對(duì)數(shù)階(O(nlog2n)排序 快速排序、堆排序和歸并排序； (3)O(n1+)排序,是介于0和1之間的常數(shù)。 希爾排序(4)線性階(O(n)排序 基數(shù)排序，此外還有桶、箱排序。說(shuō)明：當(dāng)原表有序或基本有序時(shí)，直接插入排序和冒泡排序?qū)⒋蟠鬁p少比較次數(shù)和移動(dòng)記錄的次數(shù)，時(shí)間復(fù)雜度可降至O（n）；而快速排序則相反，當(dāng)原表基本有序時(shí)，將蛻化為冒泡排序，時(shí)間復(fù)雜度提高為O（n2）；原表是否有序，對(duì)簡(jiǎn)單選擇排序、堆排序、歸并排序和基數(shù)排序的時(shí)間復(fù)雜度影響不大。穩(wěn)定性：排序算法的穩(wěn)定性:若待排序的序列中，存在多個(gè)具有相同關(guān)鍵字的記錄，經(jīng)過(guò)排序， 這些記錄的相對(duì)次序保

3、持不變，則稱該算法是穩(wěn)定的；若經(jīng)排序后，記錄的相對(duì) 次序發(fā)生了改變，則稱該算法是不穩(wěn)定的。穩(wěn)定性的好處：排序算法如果是穩(wěn)定的，那么從一個(gè)鍵上排序，然后再?gòu)牧硪粋€(gè)鍵上排序，第一個(gè)鍵排序的結(jié)果可以為第二個(gè)鍵排序所用?；鶖?shù)排序就是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時(shí)是不會(huì)改變的。另外，如果排序算法穩(wěn)定，可以避免多余的比較；穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序四、 設(shè)計(jì)細(xì)節(jié)排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排

4、序過(guò)程中需要訪問(wèn)外存。我們這里說(shuō)說(shuō)八大排序就是內(nèi)部排序。1. 插入排序-直接插入排序（Straight lnsertion Sort）基本思想： 將一個(gè)記錄插入到已排序好的有序表中，從而得到一個(gè)新，記錄數(shù)增1的有序表。即：先將序列的第1個(gè)記錄看成是一個(gè)有序的子序列，然后從第2個(gè)記錄逐個(gè)進(jìn)行插入，直至整個(gè)序列有序?yàn)橹埂Ｒc(diǎn)：設(shè)立哨兵，作為臨時(shí)存儲(chǔ)和判斷數(shù)組邊界之用。直接插入排序示例：如果碰見(jiàn)一個(gè)和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒(méi)有改變，從原無(wú)序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。時(shí)效分析：時(shí)間復(fù)雜度：O（n2）2. 插入

5、排序希爾排序（Shells Sort）希爾排序是1959 年由D.L.Shell 提出來(lái)的，相對(duì)直接排序有較大的改進(jìn)。希爾排序又叫縮小增量排序基本思想：先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。操作方法：1. 選擇一個(gè)增量序列t1，t2，tk，其中titj，tk=1；2. 按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k 趟排序；3. 每趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長(zhǎng)度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。希爾排序的示例：算

6、法的實(shí)現(xiàn)：我們簡(jiǎn)單處理增量序列：增量序列d = n/2 ,n/4, n/8 .1n為要排序數(shù)的個(gè)數(shù)即：先將要排序的一組記錄按某個(gè)增量d（n/2,n為要排序數(shù)的個(gè)數(shù)）分成若干組子序列，每組中記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行直接插入排序，然后再用一個(gè)較小的增量（d/2）對(duì)它進(jìn)行分組，在每組中再進(jìn)行直接插入排序。繼續(xù)不斷縮小增量直至為1，最后使用直接插入排序完成排序。時(shí)效分析：希爾排序時(shí)效分析很難，關(guān)鍵碼的比較次數(shù)與記錄移動(dòng)次數(shù)依賴于增量因子序列d的選取，特定情況下可以準(zhǔn)確估算出關(guān)鍵碼的比較次數(shù)和記錄的移動(dòng)次數(shù)。目前還沒(méi)有人給出選取最好的增量因子序列的方法。增量因子序列可以有各種取法，有取奇數(shù)

7、的，也有取質(zhì)數(shù)的，但需要注意：增量因子中除1 外沒(méi)有公因子，且最后一個(gè)增量因子必須為1。希爾排序方法是一個(gè)不穩(wěn)定的排序方法。3. 選擇排序簡(jiǎn)單選擇排序（Simple Selection Sort）基本思想：在要排序的一組數(shù)中，選出最小（或者最大）的一個(gè)數(shù)與第1個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最?。ɑ蛘咦畲螅┑呐c第2個(gè)位置的數(shù)交換，依次類推，直到第n-1個(gè)元素（倒數(shù)第二個(gè)數(shù)）和第n個(gè)元素（最后一個(gè)數(shù)）比較為止。簡(jiǎn)單選擇排序的示例：操作方法：第一趟，從n 個(gè)記錄中找出關(guān)鍵碼最小的記錄與第一個(gè)記錄交換；第二趟，從第二個(gè)記錄開(kāi)始的n-1 個(gè)記錄中再選出關(guān)鍵碼最小的記錄與第二個(gè)記錄交換；以此類推.

8、第i 趟，則從第i 個(gè)記錄開(kāi)始的n-i+1 個(gè)記錄中選出關(guān)鍵碼最小的記錄與第i 個(gè)記錄交換，直到整個(gè)序列按關(guān)鍵碼有序。4. 選擇排序堆排序（Heap Sort）堆排序是一種樹(shù)形選擇排序，是對(duì)直接選擇排序的有效改進(jìn)。基本思想：堆的定義如下：具有n個(gè)元素的序列（k1,k2,.,kn),當(dāng)且僅當(dāng)滿足時(shí)稱之為堆。由堆的定義可以看出，堆頂元素（即第一個(gè)元素）必為最小項(xiàng)（小頂堆）。若以一維數(shù)組存儲(chǔ)一個(gè)堆，則堆對(duì)應(yīng)一棵完全二叉樹(shù)，且所有非葉結(jié)點(diǎn)的值均不大于(或不小于)其子女的值，根結(jié)點(diǎn)（堆頂元素）的值是最小(或最大)的。如：（a）大頂堆序列：（96, 83,27,38,11,09) (b) 小頂堆序列：（1

9、2，36，24，85，47，30，53，91）初始時(shí)把要排序的n個(gè)數(shù)的序列看作是一棵順序存儲(chǔ)的二叉樹(shù)（一維數(shù)組存儲(chǔ)二叉樹(shù)），調(diào)整它們的存儲(chǔ)序，使之成為一個(gè)堆，將堆頂元素輸出，得到n 個(gè)元素中最小(或最大)的元素，這時(shí)堆的根節(jié)點(diǎn)的數(shù)最小（或者最大）。然后對(duì)前面(n-1)個(gè)元素重新調(diào)整使之成為堆，輸出堆頂元素，得到n 個(gè)元素中次小(或次大)的元素。依此類推，直到只有兩個(gè)節(jié)點(diǎn)的堆，并對(duì)它們作交換，最后得到有n個(gè)節(jié)點(diǎn)的有序序列。稱這個(gè)過(guò)程為堆排序。因此，實(shí)現(xiàn)堆排序需解決兩個(gè)問(wèn)題：1. 如何將n 個(gè)待排序的數(shù)建成堆；2. 輸出堆頂元素后，怎樣調(diào)整剩余n-1 個(gè)元素，使其成為一個(gè)新堆。首先討論第二個(gè)問(wèn)題：

10、輸出堆頂元素后，對(duì)剩余n-1元素重新建成堆的調(diào)整過(guò)程。調(diào)整小頂堆的方法：1）設(shè)有m 個(gè)元素的堆，輸出堆頂元素后，剩下m-1 個(gè)元素。將堆底元素送入堆頂（最后一個(gè)元素與堆頂進(jìn)行交換），堆被破壞，其原因僅是根結(jié)點(diǎn)不滿足堆的性質(zhì)。2）將根結(jié)點(diǎn)與左、右子樹(shù)中較小元素的進(jìn)行交換。3）若與左子樹(shù)交換：如果左子樹(shù)堆被破壞，即左子樹(shù)的根結(jié)點(diǎn)不滿足堆的性質(zhì)，則重復(fù)方法 （2）.4）若與右子樹(shù)交換，如果右子樹(shù)堆被破壞，即右子樹(shù)的根結(jié)點(diǎn)不滿足堆的性質(zhì)。則重復(fù)方法 （2）.5）繼續(xù)對(duì)不滿足堆性質(zhì)的子樹(shù)進(jìn)行上述交換操作，直到葉子結(jié)點(diǎn)，堆被建成。稱這個(gè)自根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的調(diào)整過(guò)程為篩選。如圖：再討論對(duì)n 個(gè)元素初始建堆的

11、過(guò)程。建堆方法：對(duì)初始序列建堆的過(guò)程，就是一個(gè)反復(fù)進(jìn)行篩選的過(guò)程。1）n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，則最后一個(gè)結(jié)點(diǎn)是第個(gè)結(jié)點(diǎn)的子樹(shù)。2）篩選從第個(gè)結(jié)點(diǎn)為根的子樹(shù)開(kāi)始，該子樹(shù)成為堆。3）之后向前依次對(duì)各結(jié)點(diǎn)為根的子樹(shù)進(jìn)行篩選，使之成為堆，直到根結(jié)點(diǎn)。如圖建堆初始過(guò)程：無(wú)序序列：（49，38，65，97，76，13，27，49）算法的實(shí)現(xiàn)：從算法描述來(lái)看，堆排序需要兩個(gè)過(guò)程，一是建立堆，二是堆頂與堆的最后一個(gè)元素交換位置。所以堆排序有兩個(gè)函數(shù)組成。一是建堆的滲透函數(shù)，二是反復(fù)調(diào)用滲透函數(shù)實(shí)現(xiàn)排序的函數(shù)。時(shí)效分析：設(shè)樹(shù)深度為k，。從根到葉的篩選，元素比較次數(shù)至多2(k-1)次，交換記錄至多k 次。所以，在

12、建好堆后，排序過(guò)程中的篩選次數(shù)不超過(guò)下式：而建堆時(shí)的比較次數(shù)不超過(guò)4n 次，因此堆排序最壞情況下，時(shí)間復(fù)雜度也為：O(nlogn )。5. 交換排序冒泡排序（Bubble Sort）基本思想：在要排序的一組數(shù)中，對(duì)當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對(duì)相鄰的兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們互換。冒泡排序的示例：6. 交換排序快速排序（Quick Sort）基本思想：1）選擇一個(gè)基準(zhǔn)元素,通常選擇第一個(gè)元素或者最后一個(gè)元素,2）通過(guò)一趟排序講待排序的記錄分割成獨(dú)立的兩部分，其中一部分記錄的元素值均比基準(zhǔn)

13、元素值小。另一部分記錄的元素值比基準(zhǔn)值大。3）此時(shí)基準(zhǔn)元素在其排好序后的正確位置4）然后分別對(duì)這兩部分記錄用同樣的方法繼續(xù)進(jìn)行排序，直到整個(gè)序列有序?？焖倥判虻氖纠海╝） 一趟排序的過(guò)程：（b） 排序的全過(guò)程：時(shí)效分析： 快速排序是通常被認(rèn)為在同數(shù)量級(jí)（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按關(guān)鍵碼有序或基本有序時(shí)，快排序反而蛻化為冒泡排序。為改進(jìn)之，通常以“三者取中法”來(lái)選取基準(zhǔn)記錄，即將排序區(qū)間的兩個(gè)端點(diǎn)與中點(diǎn)三個(gè)記錄關(guān)鍵碼居中的調(diào)整為支點(diǎn)記錄。快速排序是一個(gè)不穩(wěn)定的排序方法。7. 歸并排序（Merge Sort）基本思想：歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以

14、上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。歸并排序示例：算法的實(shí)現(xiàn)：1 個(gè)元素的表總是有序的。所以對(duì)n 個(gè)元素的待排序列，每個(gè)元素可看成1 個(gè)有序子表。對(duì)子表兩兩合并生成n/2個(gè)子表，所得子表除最后一個(gè)子表長(zhǎng)度可能為1 外，其余子表長(zhǎng)度均為2。再進(jìn)行兩兩合并，直到生成n 個(gè)元素按關(guān)鍵碼有序的表。8. 桶排序/基數(shù)排序(Radix Sort)基本思想：是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的，先按低優(yōu)先級(jí)排序，再按高優(yōu)先級(jí)排序。最后的次序就是高優(yōu)先級(jí)

15、高的在前，高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前。基數(shù)排序基于分別排序，分別收集，所以是穩(wěn)定的。五、 程序設(shè)計(jì)1、 直接插入排序算法的實(shí)現(xiàn)2、 希爾排序算法的實(shí)現(xiàn)3、 簡(jiǎn)單選擇排序算法的實(shí)現(xiàn)4、 堆排序算法的實(shí)現(xiàn)5、 冒泡排序算法優(yōu)化后的實(shí)現(xiàn)6、 快速排序算法的實(shí)現(xiàn)7、 歸并排序算法的實(shí)現(xiàn)8、 基數(shù)排序算法的實(shí)現(xiàn) 六、 測(cè)試結(jié)果1、 直接插入排序算法的實(shí)現(xiàn)有如下結(jié)果： 2、 希爾排序算法的實(shí)現(xiàn)有如下結(jié)果：3、 簡(jiǎn)單選擇排序算法的實(shí)現(xiàn)4、 堆排序算法的實(shí)現(xiàn)5、 冒泡排序算法優(yōu)化后的實(shí)現(xiàn)6、 快速排序算法的實(shí)現(xiàn)7、 歸并排序算法的實(shí)現(xiàn)8、 基數(shù)排序算法的實(shí)現(xiàn) 七、 總結(jié)反思 本次對(duì)于八種排序的系統(tǒng)學(xué)習(xí)，利

16、用圖標(biāo)的記憶能夠很好的幫助學(xué)習(xí)?；撕荛L(zhǎng)時(shí)間終于把排序的基礎(chǔ)學(xué)了一下，這段時(shí)間學(xué)了很多東西，總結(jié)一下：學(xué)的排序算法有：插入排序，合并排序，冒泡排序，選擇排序，希爾排序，堆排序，快速排序，基數(shù)排序。比較一下學(xué)習(xí)后的心得。我不是很清楚他們的時(shí)間復(fù)雜度，也真的不知道他們到底誰(shuí)快誰(shuí)慢，因?yàn)闀?shū)上的推導(dǎo)我確實(shí)只是小小了解，并沒(méi)有消化。也沒(méi)有完全理解他們的精髓，所以又什么錯(cuò)誤的還需要高手指點(diǎn)。1.排序穩(wěn)定，所謂排序穩(wěn)定就是指：如果兩個(gè)數(shù)相同，對(duì)他們進(jìn)行的排序結(jié)果為他們的相對(duì)順序不變。例如A=1,2,1,2,1這里排序之后是A = 1,1,1,2,2 穩(wěn)定就是排序后第一個(gè)1就是排序前的第一個(gè)1，第二個(gè)1就是排

17、序前第二個(gè)1，第三個(gè)1就是排序前的第三個(gè)1。同理2也是一樣。這里用顏色標(biāo)明了。不穩(wěn)定呢就是他們的順序不應(yīng)和開(kāi)始順序一致。也就是可能會(huì)是A=1,1,1,2,2這樣的結(jié)果。2.感覺(jué)誰(shuí)最好，在我的印象中快速排序是最好的，時(shí)間復(fù)雜度：n*log(n)，不穩(wěn)定排序。原地排序。他的名字很棒，快速嘛。當(dāng)然快了。我覺(jué)得他的思想很不錯(cuò)，分治，而且還是原地排序，省去和很多的空間浪費(fèi)。速度也是很快的，n*log(n)。但是有一個(gè)軟肋就是如果已經(jīng)是排好的情況下時(shí)間復(fù)雜度就是n*n,不過(guò)在加入隨機(jī)的情況下這種情況也得以好轉(zhuǎn)，而且他可以做任意的比較，只要你能給出兩個(gè)元素的大小關(guān)系就可以了。適用范圍廣，速度快。3.插入排序

18、：n*n的時(shí)間復(fù)雜度，穩(wěn)定排序，原地排序。插入排序是我學(xué)的第一個(gè)排序，速度還是很快的，特別是在數(shù)組已排好了之后，用它的思想來(lái)插入一個(gè)數(shù)據(jù)，效率是很高的。因?yàn)椴挥萌颗?。他的?shù)據(jù)交換也很少，只是數(shù)據(jù)后移，然后放入要插入的數(shù)據(jù)。（這里不是指調(diào)用插入排序，而是用它的思想）。我覺(jué)得，在數(shù)據(jù)大部分都排好了，用插入排序會(huì)給你帶來(lái)很大的方便。數(shù)據(jù)的移動(dòng)和交換都很少。4.冒泡排序，n*n的時(shí)間復(fù)雜度，穩(wěn)定排序，原地排序。冒泡排序的思想很不錯(cuò)，一個(gè)一個(gè)比較，把小的上移，依次確定當(dāng)前最小元素。因?yàn)樗?jiǎn)單，穩(wěn)定排序，而且好實(shí)現(xiàn)，所以用處也是比較多的。還有一點(diǎn)就是加上哨兵之后他可以提前退出。5.選擇排序，n*n的時(shí)間

19、復(fù)雜度， 穩(wěn)定排序，原地排序。選擇排序就是冒泡的基本思想，從小的定位，一個(gè)一個(gè)選擇，直到選擇結(jié)束。他和插入排序是一個(gè)相反的過(guò)程，插入是確定一個(gè)元素的位置，而選擇是確定這個(gè)位置的元素。他的好處就是每次只選擇確定的元素，不會(huì)對(duì)很多數(shù)據(jù)進(jìn)行交換。所以在數(shù)據(jù)交換量上應(yīng)該比冒泡小。6.插入排序，選擇排序，冒泡排序的比較，他們的時(shí)間復(fù)雜度都是n*n。我覺(jué)得他們的效率也是差不多的，我個(gè)人喜歡冒泡一些，因?yàn)橐盟臅r(shí)候數(shù)據(jù)多半不多，而且可以提前的返回已經(jīng)排序好的數(shù)組。而其他兩個(gè)排序就算已經(jīng)排好了，他也要做全部的掃描。在數(shù)據(jù)的交換上，冒泡的確比他們都多。舉例說(shuō)明插入一個(gè)數(shù)據(jù)在末尾后排序，冒泡只要一次就能搞定，而

20、選擇和插入都必須要n*n的復(fù)雜度才能搞定。7.合并排序：n*log(n)的時(shí)間復(fù)雜度， 穩(wěn)定排序，非原地排序。他的思想是分治，先分成小的部分，排好部分之后合并，因?yàn)槲覀兞硗馍暾?qǐng)的空間，在合并的時(shí)候效率是0(n)的。速度很快。貌似他的上限是n*log(n)，所以如果說(shuō)是比較的次數(shù)的話，他比快速排序要少一些。對(duì)任意的數(shù)組都能有效地在n*log(n)排好序。但是因?yàn)樗欠窃嘏判?，所以雖然他很快，但是貌似他的人氣沒(méi)有快速排序高。8.堆排序：n*log(n)的時(shí)間復(fù)雜度， 非穩(wěn)定排序，原地排序。他的思想是利用的堆這種數(shù)據(jù)結(jié)構(gòu)，堆可以看成一個(gè)完全二叉樹(shù)，所以在排序中比較的次數(shù)可以做到很少。加上他也是原地

21、排序，不需要申請(qǐng)額外的空間，效率也不錯(cuò)?？墒撬乃枷敫杏X(jué)比快速難掌握一些。還有就是在已經(jīng)排好序的基礎(chǔ)上添加一個(gè)數(shù)據(jù)再排序，他的交換次數(shù)和比較次數(shù)一點(diǎn)都不會(huì)減少。雖然堆排序在使用的中沒(méi)有快速排序廣泛，但是他的數(shù)據(jù)結(jié)構(gòu)和思想真的很不錯(cuò)，而且用它來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列，效率沒(méi)得說(shuō)。堆，還是要好好學(xué)習(xí)掌握的。9.希爾排序：n*log(n)的時(shí)間復(fù)雜度(這里是錯(cuò)誤的，應(yīng)該是nlamda(1 lamda 2), lamda和每次步長(zhǎng)選擇有關(guān)。)， 非穩(wěn)定排序，原地排序。主要思想是分治，不過(guò)他的分治和合并排序的分治不一樣，他是按步長(zhǎng)來(lái)分組的，而不是想合并那樣左一半右一半。開(kāi)始步長(zhǎng)為整個(gè)的長(zhǎng)度的一半。分成nLen/2個(gè)組，然后每組排序。接個(gè)步長(zhǎng)減為原來(lái)的一半在分組排序，直到步長(zhǎng)為1，排序之后希爾排序就完成了。這個(gè)思路很好，據(jù)說(shuō)是插入排序的升級(jí)版，所以在實(shí)現(xiàn)每組排序的時(shí)候我故意用了插入排序。我覺(jué)得他是一個(gè)特別好的排序方法了。他的缺點(diǎn)就是兩個(gè)數(shù)可能比較多次，因?yàn)閮蓚€(gè)數(shù)據(jù)會(huì)多次分不過(guò)他們不會(huì)出現(xiàn)數(shù)據(jù)的交換。效率也是很高的。10.快速排序，堆排序，合并排序，希爾排序的比較，他們的時(shí)間復(fù)雜的都是n*log(n)，我認(rèn)為在使用上快速排序最廣泛，他原地排序，雖然不穩(wěn)定，可是很多情況下排序根本就不在意他是否穩(wěn)定。他的比較次數(shù)是比較小的，因?yàn)樗褦?shù)據(jù)分成了大和小的兩部分。每次都確定了一個(gè)數(shù)