1、1排序的基本概念插入排序交換排序選擇排序歸并排序基數排序各種方法的比較第11章 排序什么是排序(Sorting)？簡單地說，排序就是將一組雜亂無章的數據按一定的規律排列起來（遞增或遞減）。排序是計算機中經常遇到的操作。排序的概念數據表(Data List) 待排序的記錄的有限集合。 關鍵字(Key) 作為排序依據的各記錄中的屬性域。數據表： R1 ，R2 ， R3 ， Rn 關鍵字序列： k1 ， k2 ， k3 ， kn 排序(Sorting)使一組任意排列的數據表變成一組按關鍵字線性有序（遞增或遞減）的數據表。數據表： R1 ，R2 ， R3 ， Rn 關鍵字序列： k1 ， k2 ， k

2、3 ， kn 其中：遞增次序 ： k1 k2 k3 kn 或 遞減次序 ： k1 k2 k3 kn 排序前：排序后：排序的概念例：5，2，8，5* 排序后為：2，5，5*，8 是穩定排序 排序后為：2，5*，5，8 是不穩定排序排序的分類排序算法的穩定性 關鍵字相同的記錄在排序過程中保持前后次序不變的排序稱穩定排序，否則稱不穩定排序。內排序與外排序 *內排序是指在排序過程中記錄全部存放在內存的排序； *外排序是指在排序過程中數據量太大，不能同時存放在內存，在排序過程中不斷進行內、外存之間數據交換的排序。5數據表的存儲方式 *順序存儲方式通過移動記錄的相對存儲位置實現排序。排序的分類*鏈式存儲方

3、式通過各結點修改指針實現排序30 11 44 77 22 8811 22 30 44 77 88排序前排序后h30 11 44 77 22h30 11 44 77 22 排序前排序后6排序的時間效率: 通常用算法執行中的數據比較次數與數據移動次數來衡量。排序的空間效率：在算法執行時所需的附加存儲空間多少來衡量。排序算法分析 為簡單起見，數據的存儲結構采用順序方式存儲，同時假定關鍵字是整數。記錄存儲數據類型如下：typedef int KeyTypetypedef struct KeyType key; /*存放關鍵字*/ InfoType data;/*存放其他數據項*/ RecType; /

4、*記錄數據類型*/RecRype Rn+1; /* R0Rn存放n個記錄*/ 按關鍵字遞增次序排序7插入排序(Insert Sorting) 基本原理 : 將一個待排序的記錄, 按其關鍵字大小, 插入到前面已經排好序的一組記錄的適當位置上, 直到記錄全部插入為止。 排序方法直接插入排序 (Insert Sort) 希爾排序 (Shell Sort)8基本思想 : 將第i個記錄插入在前i-1個有序的記錄中，使前i個記錄有序。直接插入排序 (Insert Sort)k1 ， k2 ， ki-1 ，ki有序k1 ， k2 ， ki ki-1 有序例：10，20，30，40，50，2510，20，25

5、，30，40，509主要操作3033442211 1 2 3 4 50 1 2 3 4 5 33221144304411 1 2 3 4 5 temp442211333030443333304433333030222211主要操作 步驟：*Ri 暫存temp , *將比其大的所有記錄依次后移 *temp ( Ri)插入。監視哨作用：*暫存Ri *檢測越界R0R011304410 49 38 65 97 76 13 27 490 1 2 3 4 5 6 7 8 初始 49 38 65 97 76 13 27 49第一趟第二趟 38 49 65 97 76 13 27 49493838493865

6、6565第三趟 38 49 65 97 76 13 27 49第四趟 38 49 65 97 76 13 27 49第五趟 38 49 65 76 97 13 27 49第六趟 13 38 49 65 76 97 27 49第七趟 13 27 38 49 65 76 97 499797977676977613139776654938134927279776654938274997766549主要步驟：*Ri 暫存0*將比其大的所有記錄依次后移*R0 寫入第i趟： （1）R0=Ri （2）j初值？ （3）若Rj.keyR0.key Rj后移 （4）j下一個（前移） （5）重復（3）（4）直到？

7、（6）R?=R0i的初值？ 終值？11第i趟： （1）R0=Ri （2）j初值？ （3）若Rj.keyR0.key Rj后移 （4）j下一個（前移） （5）重復（3）（4）直到？ （6）R?=R0i的初值？ 終值？insertsort(rectype R ,n) for(i=?;id1 d2 d2 . (通常d1=n/2 di+1=di/2),每趟將數據表分成di組, 分別對各組進行直接插入排序, 直到最后全部記錄在一組為止。15n=10gap=5 49 38 65 97 76 13 27 49 55 044976389765134927550449133827654955970476gap=

8、355270449653876499738765513042765494997gap=2gap=11327554997766538044904491338275549657697659776043827497665380449注:希爾排序開始時增量大, 分組多, 各組含記錄較少,故各組插入快. 后來雖然增量逐漸減小, 各組含記錄增多, 但各組已基本有序, 所以插入速度仍較快.*每趟從Ri開始處理, i=?*Ri要插入前面有序的子序列中, 子序列中每個記錄間隔gap.*每趟gap=gap/2 直到?16*每趟從Ri開始處理, i=?*Ri要插入前面有序的子序列中, 子序列中每個記錄間隔gap。*

9、每趟gap=gap/2 直到?shellsort(rectype R , int n) gap=n/2; while(?) for(i=?;i0 & Rj.keytemp.key) Rj+gap=Rj; j=j-gap; R?=temp; gap=gap/2; 希爾排序的算法穩定性:不穩定的排序。 （關鍵字相同的記錄會交換次序）希爾排序算法分析時間性能: T(n)= O(nlog2n)空間性能:在排序過程中，只需附加一個存儲單元暫存當前處理記錄。 S(n)=O(1)18交換排序 ( Exchange Sort ) 基本原理：兩兩比較待排序記錄的關鍵字,若發生逆序(即排列順序與排序后的次序正好相

10、反)，則交換之。直到所有記錄都排好序為止。交換排序方法冒泡排序(Bubble Sort)快速排序(Quick Sort)19基本思想：在待排序子序列 中，兩兩比較相鄰記錄的關鍵字，若逆序，則交換。冒泡排序 (Bubble Sort)關鍵字子序列: ki , ki+1 , knkn-1 與kn , kn-2與kn-1 ki 與ki+1 進行比較若逆序，則交換。2055221133442211335544113333445522113344334455221133441155115511221122逆序逆序逆序正序主要操作 由于關鍵字小的記錄不斷上浮，象小氣泡一樣，故稱為起泡排序。注：在一趟排序中

11、，將關鍵字最小的記錄頂到第一位。2133445522111 2 3 4 53344552211334455221133223322223333553344552211551155115511445544554455逆序逆序逆序正序從前向操作注：將子序列中最大記錄沉到最后一個221 2 3 4 5 6 7 8 初始 49 38 65 97 76 13 27 49第一趟 49 38 65 97 76 13 27 494938384965493897496576657697137697139713972727972797499749第二趟 38 49 65 76 13 27 49 97第三趟 38

12、49 65 13 27 49 76 97第四趟 38 49 13 27 49 65 76 97第五趟 38 13 27 49 49 65 76 97第六趟 13 27 38 49 49 65 76 973849386576496513761376132727762776494976493849381338271365381338381313491365134913381365272765134927274913382727654949652749492738273849主要步驟：兩兩相鄰記錄比較，若逆序，則交換。多少趟？注：當某趟沒有交換時，沒有必要進行下一趟。9749497649652749

13、492738493827如何解決？設置一個標志flag每趟：*初始時flag=0 *若有交換flag=1當本趟結束時，若flag為1，則需要進行下一趟。 若flag為0，則排序結束。23每趟： （1）j初值為1，終值i=? （2）flag=false （3）若Rj.keyRj+1.key Rj與Rj+1交換 flag=true （4）重復（3） （5）若flag=？,則結束排序。每趟進行比較的次數依次遞減，第一趟 i的初值？ 終值？bubblesort( rectype R, int n) flag=?; i=?; while(? ) flag=0; for(j=0; jRj+1.key) t

14、emp=Rj; Rj=Rj+1; Rj+1=temp; flag=1; i?; 冒泡排序的算法24冒泡排序的算法分析時間性能：冒泡排序算法由兩重循環組成，外循環的次數主要是由各趟有無交換而決定；內循環表明完成一趟排序所需進行的記錄關鍵字間的比較和記錄的交換。*最好情況：初始時按關鍵字遞增有序（正序） 比較次數: C=n -1 (僅需一趟排序） 移動次數: M=0 (這一趟沒有逆序） O(n)*最壞情況：初始時關鍵字遞減有序（逆序）O(n2)*平均情況： T(n)=O(n2)穩定性:穩定的排序。 （關鍵字相同的記錄不會交換次序）冒泡排序的算法分析時間性能: T(n)=O(n2) 但在數據表基本有

15、序的情況下效率比較高空間性能:排序在排序過程中，只需附加一個存儲單元用于交換。 S(n)=O(1)26快速排序 (Quick Sort)基本思想是任取待排序子序列中的一個記錄 (例如取第一個) 作為基準, 按照該記錄關鍵字的大小, 將整個子序列劃分為左右兩個子序列： 左側所有記錄的關鍵字都小于基準記錄的關鍵字右側所有記錄的關鍵字都大于或等于基準記錄的關鍵字klow , klow+1 , , khighklow , klow+1, klow , khigh基準記錄則排在這兩個子序列中間(這也是該記錄的最終排序的位置)。然后分別對這兩個子序列重復施行上述方法，直到所有的記錄都排在相應位置上為止。小

16、大272125493516081 2 3 4 5 6pivot213525164908temp暫存基準212549351608212108082525161649492121基本思想：將后面所有關鍵字小于基準關鍵字的記錄移到前面，將前面所有關鍵字大小基準關鍵字的記錄移動后面。反復交替操作： *從后向前找到第一個關鍵字小于基準的記錄與基準交換， *從前向后找到第一個關鍵字大于基準的記錄與基準交換。21210821252521281 2 3 4 5 6 7 8 初始 49 38 65 97 76 13 27 49第一趟temp49pivotji276527651313979749 27 38 13

17、76 97 65 4949反復交替操作： *從后向前找到第一個關鍵字小于基準的記錄前移 *從前向后找到第一個關鍵字大于基準的記錄后移設置指針j（從后向前掃描）設置指針i（從前向后掃描）劃 分在Rlow.high劃分的主要步驟：（1）初值？（2）temp=Rlow（3）從后向前：當Rj=temp時，j-;（4）Rj前移？（5）從前向后：當Ritemp時，j-;（4）Rj前移？（5）從前向后：當Ritemp.key) j-; if( ?) R?=Rj;i+; while(? & Ri.keytemp.key) i+; if(?) R?=Ri;j-; return ?;301 2 3 4 5 6 7

18、 8 初始 49 38 65 97 76 13 27 49第一趟pivot 27 38 1376 97 65 49 49快速排序49132738769749 654965Rs.t快速排序主要步驟：(遞歸）（1）在Rs.t進行劃分，確定基準的位置k（2）在Rs.?進行快速排序（3）在R?.t進行快速排序遞歸出口？31主要步驟：(遞歸） Rs.t （1）在Rs.t進行劃分，確定基準的位置i（2）在Rs.?進行快速排序（3）在R?.t進行快速排序遞歸出口？快速排序的算法quicksort( R,s,t)rectype R ;int s,t; if( ?) i=partition(R,s,t); /*

19、劃分并確定基準位置*/ quicksort(R,s,?); /*遞歸處理左序列*/ quicksort(R,?,t); /*遞歸處理右序列*/ 32時間性能：取決于每一次劃分的結果。快速排序的算法分析*最壞情況：每次劃分選取的基準都是當前無序區中關鍵字最小（或最大）的記錄，劃分的結果只是一個區間，則排序必須做n-1趟，每一趟中需做n-i次比較，所以最大比較次數為：33用第一個對象作為基準對象快速排序退化的例子 08 16 21 25 25* 49081 2 3 4 5 6 pivot初始16 16 21 25 25* 49 08i = 121 21 25 25* 49 16i = 2 0825

20、 25 25* 49 21i = 3 16 08 25* 4925*25i = 4 21 16 084925*i = 525 21 16 08快速排序的算法分析*最好情況：每次所取的基準都是當前無序區的“中值”記錄，劃分的結果是基準的左右兩個無序子區間的長度大致相等。 設C(n)表示對長度為n 的序列進行快速排序所需的比較次數，它等于劃分所需的比較次數n-1，加上平分后左右兩個無序子區間進行快速排序所需的比較次數。假設數據長度n=2k k=log2n快速排序的算法分析穩定性:不穩定的排序。 （關鍵字相同的記錄會交換次序）時間性能: 最壞時間T(n)=O(n2) 最好時間T(n)=O(nlog2

21、n） 已證明，平均時間T(n)=O(nlog2n)空間性能:排序算法是利用遞歸實現的，排序過程中需附加棧空間用于存儲遞歸各層信息，則 S(n)=O(log2n)36選擇排序(Selection Sort)基本原理: 在待排序的子序列中, 選擇關鍵字最小(或最大)的記錄, 存放在已排序的子序列中。 排序方法直接選擇排序(Straight Select Sort) 堆排序(Heap Sort)37基本思想 :在子序列中選擇具有最小(或最大)關鍵字的記錄, 若它不是這子序列中的第一位，則將它調入到第一位上。直接選擇排序 (Straight Select Sort)ki ， ki+1 ， ，knkd

22、， k2 ， k1 ki-1 最小(或最大)例：30，20，50，10，40，7010，20，50，30，40，70kd381 2 3 4 5 6 7 8 初始 49 65 38 97 76 13 27 49第一趟 49 65 38 97 76 13 27 49131349第六趟 13 27 38 49 49 97 65 76第二趟 13 65 38 97 76 49 27 49第三趟 13 27 38 97 76 49 65 49第四趟 13 27 38 97 76 49 65 49第五趟 13 27 38 49 76 97 65 49第七趟 13 27 38 49 49 65 97 762

23、7652749389749497649656597766797主要步驟:在子序列中選擇關鍵字最小的記錄交換到子序列的第一位.第i趟子序列的區間?第i趟:(1)從Ri Rn中選擇最小關鍵字的記錄Rk;(2)若k!=i, 則Ri與Rk交換.39直接選擇排序的算法第i趟:(1)從RiRn中選擇最小關鍵字的記錄Rk;(2)若k!=i, 則Ri與Rk交換.selectsort ( rectype R , int n ) for ( int i = ?; i ?; i+ ) k = i; /選擇具有最小排序碼的對象 for ( j =?; j n; j+) if ( Rj.key Rk.key ) k =

24、 ?; /當前具最小排序碼的對象 if ( ? ) /對換到第 i 個位置 temp=Ri; Ri=Rk; Rk=temp; 直接選擇排序算法分析時間性能：直接選擇排序算法由兩重循環組成，外循環為n-1趟排序；內循環表明完成一趟排序所需進行的記錄關鍵字間的比較和記錄的后移。O(n2)*時間效率： T(n)=O(n2)*比較次數:直接選擇排序的比較次數與初始狀態無關. 第i趟選擇關鍵字最小的記錄要比較n-i次, 則總的比較次數為:*移動次數:最好情況是每趟關鍵字最小的記錄總是子序列中第一位,不需要交換,M=0;最壞情況是每趟都需要將關鍵字最小的記錄交換到子序列的第一,M=3(n-1). 則平均移

25、動次數為O(n).直接選擇排序的算法分析穩定性:不穩定的排序。 （關鍵字相同的記錄會交換次序）時間性能: T(n)=O(n2)空間性能:需附一個存儲單元用于交換，則 S(n)=O(1)42堆的定義： n個關鍵字序列k1, k2, . ,kn稱為堆，當且僅當該序列滿足特性：堆排序 (Heap Sort)ki k2iki k2i+1注：若將序列看成按層次編號的完全二叉樹，根據二叉樹的性質,即ki 的左右孩子正好分別為k2i 和k2i+1，因此,堆也可以說是滿足如下性質的完全二叉樹:樹中任一分支結點的值均大于或等于它的孩子結點的孩子的值.(1 i n/2 )大根堆ki k2iki k2i+1或小根堆

26、43例: ( 96, 83, 27, 38, 11, 9 )96832738119大根堆例: ( 10, 15, 56, 25, 30, 70 )101556253070小根堆注:在大根堆中根(第一個)為最大值. 在小根堆中根(第一個)為最小值.例: (42,13,91,23,24,16,5,88)421391232416588不是根堆若將序列構造成堆,就可以確定出序列中的最大( 或最小 )元素. ?構造4442139188241605234213918824160523421391232416058842 13 91 23 24 16 05 881 2 3 4 5 6 7 823912388

27、1323882388238891911388132313234288912324160513424291914291429142依次調整每一個分支結點,使其大于兩個孩子結點.注: 這種方法叫“篩選法”, 要求在其子樹中每個分支結點都滿足條件的情況下進行,因此,要依次逆序調整每個分支結點.881388132323138845“篩選法”的算法主要步驟: (在Rlow.high中調整分支結點Rlow)(1)確定兩個孩子中的大孩子Rj(2)若RiRj 則交換Ri與Rj, i=j 重復(1)(2) 直到? (由于有可能影響子樹)sift(rectype R,int low, int high) i=lo

28、w; j=2*i; temp=Ri; while( ? ) while (? & Rj.key雙親,則交換*/ i=j; j=?; /*去調整子樹*/ else break; R?=temp; 堆 排 序堆排序是一種樹型選擇排序。基本思想:將待排序的子序列k1, k2, . ,ki 構造成堆, 從而選擇出關鍵字最大(或最小)記錄.堆排序分為兩個步驟： 1、根據初始狀態，形成初始堆。 2、通過一系列的記錄交換和重新調整 進行排序。4749386597761327491 2 3 4 5 6 7 8 初始 49 38 65 97 76 13 27 499797656538temp3897494949

29、9776493838 97 76 65 49 49 13 27 389738第一趟3876654949132738重建堆只需調整根結點76383849第二趟 76 49 65 38 49 13 27 97277648274965384913276527第三趟 65 49 27 38 49 13 76 97136513492738491349134913第四趟49 49 27 38 13 65 76 971349134927381349131338第五趟 49 38 27 13 49 65 76 971349133827131338第六趟 38 13 27 49 49 65 76 9738272

30、73827第七趟 27 13 38 49 49 65 76 971327主要步驟：（1）將R1.n初建堆。（2） 重復如下操作： （子序列R1.i) *子序列中第一個記錄與最后一個交換 *重建堆49主要步驟：（1）將R1.n初建堆。（2） 重復如下操作： （子序列R1.i) *子序列中第一個 記錄與最后一個 交換 *重建堆堆排序的算法heapsort(rectype R,int n) for( i=n/2; i0; i-) sift(R,i,n); /*初建軍堆*/ for(i=?;?;i-) temp=R1; R1=Ri; Ri=temp; /*子序列首尾交換*/ sift(R,1,i-1)

31、; /*重建堆*/ 堆排序算法分析時間性能：堆排序算法分兩部分，一是整個序列初建堆；二是n-1趟的交換和重建堆。O(n)*時間效率： T(n)= O(nlog2n)*重建堆:每次重建堆時, 僅需調整根結點,最多比較log2n, 則n-1次重建堆時間效率為O(nlog2n) 。*初建堆:若n個結點的堆構成的完全二叉樹的深度為k,則有2k-1 n 2k。 在第 i 層上的分支結點數至多為 2i (i = 1, , k-1), 且調整時最多比較 2 (k-i)。堆排序的算法分析穩定性:不穩定的排序。 （關鍵字相同的記錄會交換次序）時間性能: T(n)= O(nlog2n)空間性能:需附一個存儲單元用

32、于交換，則 S(n)=O(1)52歸并排序 (Merge Sort)基本思想:通過對兩個有序記錄序列的合并來實現排序。所謂歸并是指將若干個已排好序的子序列合并成一個有序的子序列。這里是將兩個有序的子序列合并成一個有序的子序列稱二路歸并。klow , kmid , kmid , , khighklow , , khigh有序有序有序例：30，40，50，11，33，55 ，7711，30， 33， 40，50，55，77532125493516081 2 3 4 5 6 75521254935160855主要操作:掃描兩個子序列,將關鍵字小的記錄依次歸并。設指針i掃描第一個子序列設指針j掃描第二

33、個子序列 j i主要步驟:Rlow.mid.high(1)i,j初值?(2)若Ri.keyRj.key 則歸并Ri; i后移; 否則歸并Rj; j 后移;(3)重復(2) 直到?(4)剩余? RR154主要步驟:Rlow.mid.high(1)i,j初值?(2)若RiRj 則歸并Ri; i后移; 否則歸并Rj; j 后移;(3)重復(2) 直到?(4)剩余? 二路歸并算法merge ( R, low, mid, high )rectype R;int low,mid,high; rectype R1; i =low; j = mid, k = 0;R1=malloc( ); while ( i

34、 =mid & j =high ) if ( Ri.key = Rj.key ) /*兩兩比較*/ R1k = Ri; i+; k+; /*歸并Ri*/ else R1k = Rj; j+; k+; /*歸并Rj*/ while ( i=mid ) R1k = Ri; i+; k+; /*前序列有剩余*/ while ( j=high ) R1k = Rj; j+; k+; /*前序列有剩余*/ for(k=0,i=low;i=high;k+,i+) Ri=R1k;554938659776132749881638 4965 97 13 76 27 49 16 88 38 49 65 97 13

35、 27 49 76 13 27 38 49 49 65 76 97 16 88 16 88 13 16 27 38 49 49 65 76 88 97 4938659776132749881638 49 65 97 13 76 27 49 16 88 38 49 65 97 13 27 49 76 16 88 13 27 38 49 49 65 76 97 16 88 歸并排序 二路歸并：將相鄰的的兩個有序的序列合并成一個有序的序列。 設每趟子序列的長度為length。初始狀態：每個子序列的長度為length=1(只含一個記錄）。初始每一趟歸并排序：兩兩等長的子序列合并，最后的剩余不完整子序列

36、？兩種情況：（1）剩余一個子序列（2）兩個不完整序列56每一趟歸并排序：兩兩等長的子序列合并，最后的剩余不完整子序列？兩種情況：（1）剩余一個子序列（2）兩個不完整序列一趟歸并算法mergepass ( R, length, n )rectype ;int length, n; i = 0; for ( i=0;i+2*length-1n;i=i+2*length) /* 歸并兩個等長的子序列*/ merge( R, i, i+length-1, i+2*length-1); if ( i+length-1n ) merge(R, i, i+length-1, n-1); /*剩余兩個不完整的

37、子序列*/ 57mergesort ( rectype R , int n ) length = 1; while ( length n ) mergepass ( R, length, n ); length= 2*length;(二路)歸并排序的算法主要思想：在R和R1兩個數據表中一趟一趟交替歸并。每一趟歸并后，子序列的長度擴大一倍，即length=2*length 其初值length=1歸并排序算法分析時間性能：每一趟歸并需將一個數據表的所有記錄歸并到另一個數據表中，則一趟歸并的時間效率為O(n)。歸并排序共需約log2n趟，則總的時間效率為 T(n)=O(nlog2n) 空間性能:需附

38、一個數據表存儲空間用于交替歸并，則 S(n)=O(n)穩定性:穩定的排序。 （關鍵字相同的記錄不會交換次序）基數排序(Radix Sort)多關鍵字排序示例 *每張撲克牌有兩個“關鍵字”:花色和面值 (它們之間有次序的優先)。 *可以先對花色排序，或先對面值排序多關鍵字有序:在數據表 R1,R1,., Rn中，每個記錄Ri含d個關鍵字(Ki1,Ki2,., Kid)。若對序列中的任意兩個記錄Ri和Rj都有 (Ki1,Ki2,., Kid) (Kj1,Kj2,., Kjd) 則稱序列對關鍵字(Ki1,Ki2,., Kid)有序，且K1稱為最高位關鍵字，Kd稱為最低位關鍵字。基 數 排 序基本原理

39、:采用“分配”和“收集”兩種運算, 用對多關鍵字進行排序的思想實現對單關鍵字進行排序。此時可將單關鍵字K看成是一個子關鍵字組：(Ki1,Ki2,., Kid)排序過程：設關鍵字共有d位，讓j= d, d-1,.,1, 依次執行d次“分配”與“收集”。546732414477543233634587例:324154323363546744774587543232413363546744774587324133635432546744774587324133634477458754325467個位十位百位千位61基數排序的基本要求(1)確定所有關鍵字的最大位數d.(2)將各關鍵字按最大位補齊. (

40、數字前補0, 字符串后補空格)(3)確定進制r. (數字r=10,16, 字符r=26)(4)利用單鏈表鏈接所有記錄.(5)附加r個鏈式隊列.typedef struct node keytype datad; datatype other; struct node ;RecType;RecType *headMAXR,*tailMAXR;62head0 head1 head2 head3 head4 head5 head6 head7 head8 head9 tail0 tail1 tail2 tail3 tail4 tail5 tail6 tail7 tail8 tail9 546732414477543233634587L546732414477543233634587543233635467447745873241L分配收集第一趟排序63head0 head1 head2 head3 head4 head5 head6 head7 head8 head9 tail0 tail1 tail2 tail3 tail4 tail5 tail6 tail7 tail8 tail9 324154323363546744774587L32414477543233634587324133635467447745875432L分配收集第二