第9章內(nèi)排序2

1、1主要內(nèi)容29.1 9.1 排序的基本概念排序的基本概念9.2 9.2 插入排序插入排序9.3 9.3 交換排序交換排序9.4 9.4 選擇排序選擇排序9.5 9.5 歸并排序歸并排序9.6 9.6 分配排序分配排序9.7 9.7 性能比較性能比較 選擇排序的主要操作是選擇，其主要思想是：每趟排序在當(dāng)前待排序序列中選出關(guān)鍵碼最小的記錄，添加到有序序列中。 有序序列有序序列1 12 2i i-1-1i in nk k無序序列無序序列n ni+i+1 11 12 2i i-1-1i ii i交換交換最小記錄最小記錄9.4 9.4 選擇排序選擇排序常用的選擇排序算法：常用的選擇排序算法： （1 1）

2、直接選擇排序）直接選擇排序 （2 2）堆排序）堆排序39.4.1 9.4.1 直接選擇排序直接選擇排序41 1、基本思想、基本思想 每經(jīng)過一趟比較就找出一個(gè)最小值，與待排序列最前面的每經(jīng)過一趟比較就找出一個(gè)最小值，與待排序列最前面的位置互換位置互換. . 2 2、優(yōu)點(diǎn)：、優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單實(shí)現(xiàn)簡(jiǎn)單3 3、缺點(diǎn)：、缺點(diǎn)：每趟只能確定一個(gè)元素，表長(zhǎng)為每趟只能確定一個(gè)元素，表長(zhǎng)為n n時(shí)需要時(shí)需要n-1n-1趟趟 4 4、前提：、前提：順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu) 9.4 9.4 選擇排序選擇排序50 1 2 3 4 5最小者最小者5、直接選擇排序的過程直接選擇排序的過程9.4.1 9.4.1 直接選擇排序

3、直接選擇排序6最小者最小者0 1 2 3 4 5結(jié)果結(jié)果各趟排序后的結(jié)果各趟排序后的結(jié)果9.4.1 9.4.1 直接選擇排序直接選擇排序解決方法：解決方法： 設(shè)置一個(gè)整型變量設(shè)置一個(gè)整型變量indexindex，用于記錄在一趟比較的用于記錄在一趟比較的過程中關(guān)鍵碼最小的記錄位置。過程中關(guān)鍵碼最小的記錄位置。 如何在無序區(qū)中記錄關(guān)鍵碼最小的記錄？如何在無序區(qū)中記錄關(guān)鍵碼最小的記錄？indexindexindexindex indexindex需解決的關(guān)鍵問題需解決的關(guān)鍵問題? ?79.4.1 9.4.1 直接選擇排序直接選擇排序解決方法： 第i趟簡(jiǎn)單選擇排序的待排序區(qū)間是ri rn，則ri是無序

4、區(qū)第一個(gè)記錄，所以，將index所記載的關(guān)鍵碼最小的記錄與ri交換。如何確定最小記錄交換后的最終位置？如何確定最小記錄交換后的最終位置？需解決的關(guān)鍵問題需解決的關(guān)鍵問題? ?89.4.1 9.4.1 直接選擇排序直接選擇排序97、直接選擇排序的算法直接選擇排序的算法void SelectSort ( elemtype L,int n ) for ( i = 1; i n; i+ ) /*總共進(jìn)行n-1次排序*/ k = i; for ( j = i+1; j n; j+) /*在剩余記錄序列中選擇最小的記錄*/ if ( rj =1; i-); i=1; i-) HeapAdjust(r, i

5、, n) HeapAdjust(r, i, n) ;/;/將序列將序列rinrin建成堆建成堆 關(guān)鍵問題關(guān)鍵問題1 1：如何新建堆？如何新建堆？189.4.2 9.4.2 堆排序堆排序關(guān)鍵問題關(guān)鍵問題2 2：如何處理堆頂記錄？：如何處理堆頂記錄？49 25 21 25* 16 081 2 3 4 5 6對(duì)對(duì)應(yīng)應(yīng)交換交換08 25 21 25* 16 491 2 3 4 5 6對(duì)對(duì)應(yīng)應(yīng)123456123456199.4.2 9.4.2 堆排序堆排序算法描述：算法描述： r1rn-i+1; r1rn-i+1; 解決方法：解決方法： 第第 i i 次處理堆頂是將堆頂記錄次處理堆頂是將堆頂記錄r1r1

6、與序列中第與序列中第n-i+1n-i+1個(gè)記錄個(gè)記錄rn-i+1rn-i+1交換。交換。關(guān)鍵問題關(guān)鍵問題2 2：如何處理堆頂記錄？：如何處理堆頂記錄？209.4.2 9.4.2 堆排序堆排序關(guān)鍵問題關(guān)鍵問題3 3：怎樣將剩余記錄調(diào)整成一個(gè)新堆？怎樣將剩余記錄調(diào)整成一個(gè)新堆？21* *算法描述：算法描述：HeapAdjust(r, 1, n-i);解決方法：解決方法： 第第 i 次調(diào)整剩余記錄，此時(shí)，剩余記錄有次調(diào)整剩余記錄，此時(shí)，剩余記錄有n-i個(gè)，個(gè)，調(diào)整根結(jié)點(diǎn)至第調(diào)整根結(jié)點(diǎn)至第n-i個(gè)記錄。個(gè)記錄。9.4.2 9.4.2 堆排序堆排序例:對(duì)剛才建好的大根堆進(jìn)行排序：22交換交換 1號(hào)與號(hào)與

7、 6 號(hào)記錄號(hào)記錄 r1 rn492525*21160812345649 25 21 25* 16 08初始最大堆初始最大堆1365429.4.2 9.4.2 堆排序堆排序2316 25* 21 08 25 49交換交換 1號(hào)與號(hào)與 5 號(hào)記錄號(hào)記錄從從 1 號(hào)到號(hào)到 5 號(hào)號(hào) 重新重新調(diào)整為最大堆調(diào)整為最大堆082525*21164912345613654225 25* 21 08 16 499.4.2 9.4.2 堆排序堆排序24交換交換 1 號(hào)與號(hào)與 4 號(hào)記錄號(hào)記錄從從 1號(hào)到號(hào)到 4號(hào)號(hào) 重新重新調(diào)整為最大堆調(diào)整為最大堆1234561365429.4.2 9.4.2 堆排序堆排序25

8、08 16 21 25* 25 49交換交換 1號(hào)與號(hào)與3 號(hào)記錄號(hào)記錄從從 1 號(hào)到號(hào)到 3號(hào)號(hào) 重新重新調(diào)整為最大堆調(diào)整為最大堆1234561365429.4.2 9.4.2 堆排序堆排序2608 16 21 25* 25 49交換交換 1 號(hào)與號(hào)與2 號(hào)記錄號(hào)記錄排序完畢。排序完畢。從從 1 號(hào)到號(hào)到 2 號(hào)號(hào) 重新重新調(diào)整為最大堆調(diào)整為最大堆1234561365429.4.2 9.4.2 堆排序堆排序void HeapSort(elemtype h,int n) / /* * 對(duì)順序表對(duì)順序表* *h h進(jìn)行堆排序進(jìn)行堆排序 * */ / for(i=n/2；i=1；i-) Heapa

9、djust(h，i，n)； for(i=n；i=2；i-) temp=h1; h1=hi； hi=temp; /* HeapSort */ 27/ /* *將將hi.nhi.n建成大頂堆建成大頂堆 * */ / /* * 堆頂與堆底元素交換堆頂與堆底元素交換 * */ / /* *對(duì)對(duì)h1.i-1h1.i-1重新調(diào)整為堆重新調(diào)整為堆* */ /Heapadjust(h，1，i-1)；堆排序算法堆排序算法9.4.2 9.4.2 堆排序堆排序28void Heapajust(elemtype r，int s，int m) /* 對(duì)rs進(jìn)行調(diào)整使其成為大頂堆 */ temp=rs；child=2*s

10、；/*temp暫存rs值，child是其左孩子*/ while(child=m) /*檢查是否到達(dá)當(dāng)前堆尾，未到尾則整理*/ if(childm&rchild=rchild) break;/*根大則不必調(diào)整，函數(shù)結(jié)束*/ else /*否則子女中的大者上移*/ s=child； /*將根下降到子女位置并繼續(xù)向下整理！*/ rs=temp； /直到自下而上都滿足堆定義，再放置入口結(jié)點(diǎn)針對(duì)結(jié)點(diǎn)針對(duì)結(jié)點(diǎn) s 的堆調(diào)整函數(shù)的堆調(diào)整函數(shù)HeapAdjust ： 從結(jié)點(diǎn)從結(jié)點(diǎn)s開始到開始到當(dāng)前堆尾當(dāng)前堆尾m為止，自上向下比較，如果子女的為止，自上向下比較，如果子女的值大于雙親結(jié)點(diǎn)的值，則互相交換，

11、即把局部調(diào)整為大根堆。值大于雙親結(jié)點(diǎn)的值，則互相交換，即把局部調(diào)整為大根堆。rs=rchild；child=child*2;9.4.2 9.4.2 堆排序堆排序練習(xí)：練習(xí)：已知序列503，87，512，61，908，170，897，275，653，462，寫出采用堆排序法對(duì)該序列作升序排列的第一趟結(jié)果。29第一趟結(jié)果：908,653,897,503,462,170,512,275,61,879.4.2 9.4.2 堆排序堆排序305、堆排序算法分析：、堆排序算法分析： 時(shí)間效率： O(nlog2n)。因?yàn)檎麄€(gè)排序過程中需要調(diào)用n-1次堆頂點(diǎn)的調(diào)整，而每次堆排序算法本身耗時(shí)為log2n； 空間效

12、率：O(1)。僅在第二個(gè)for循環(huán)中交換記錄時(shí)用到一個(gè)臨時(shí)變量temp。 穩(wěn)定性： 不穩(wěn)定。 優(yōu)點(diǎn)：對(duì)小文件效果不明顯，但對(duì)大文件有效。9.4.2 9.4.2 堆排序堆排序主要內(nèi)容319.1 9.1 排序的基本概念排序的基本概念9.2 9.2 插入排序插入排序9.3 9.3 交換排序交換排序9.4 9.4 選擇排序選擇排序9.5 9.5 歸并排序歸并排序9.6 9.6 分配排序分配排序9.7 9.7 性能比較性能比較9.5 9.5 歸并排序歸并排序321、基本思想：將若干有序序列逐步歸并，最終得到一個(gè)有序序列。 （歸并排序主要是二路歸并排序）2、二路歸并排序：可以把一個(gè)長(zhǎng)度為n 的無序序列看成

13、是 n 個(gè)長(zhǎng)度為 1 的有序子序列 ，首先做兩兩歸并，得到 n / 2 個(gè)長(zhǎng)度為 2 的有序子序列 ；再做兩兩歸并，如此重復(fù)，直到最后得到一個(gè)長(zhǎng)度為 n 的有序序列。需解決的關(guān)鍵問題需解決的關(guān)鍵問題?如何將兩個(gè)有序序列合成一個(gè)有序序列？如何將兩個(gè)有序序列合成一個(gè)有序序列？怎樣完成一趟歸并？怎樣完成一趟歸并？如何控制二路歸并的結(jié)束？如何控制二路歸并的結(jié)束？33212525* 936272083716544921 2525* 4962 9308 7216 375416 37 5421 25 25* 4908 62 72 9308 21 25 25* 49 62 72 9308 16 21 25 2

14、5* 37 49 54 62 72 93len=1len=2len=4len=8len=1616 37 54整個(gè)歸并排序僅需整個(gè)歸并排序僅需 log2n 趟趟關(guān)鍵問題：關(guān)鍵問題：如何將兩個(gè)有序序列合成一個(gè)有序序列？如何將兩個(gè)有序序列合成一個(gè)有序序列？602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j609.5 9.5 歸并排序歸并排序34kkk在歸并過程中，可能會(huì)破壞原在歸并過程中，可能會(huì)破壞原來的有序序列，所以，將歸并來的有序序列，所以，將歸并的結(jié)果存入另外一個(gè)數(shù)組中。的結(jié)果存入另外一個(gè)數(shù)組中。 關(guān)鍵問題：關(guān)鍵問題：如何將

15、兩個(gè)有序序列合成一個(gè)有序序列？如何將兩個(gè)有序序列合成一個(gè)有序序列？602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j609.5 9.5 歸并排序歸并排序3536算法思想（以升序?yàn)槔合扔脙蓚€(gè)指針分別指向兩個(gè)序列的第一個(gè)數(shù)據(jù)元素，進(jìn)行比較，取出較小者，然后將其所在序列的指針后移，重復(fù)以上過程，直到指針達(dá)到序列的末尾，這時(shí)將另一個(gè)序列的剩余元素依次順序放到有序序列的后面即可。關(guān)鍵問題：關(guān)鍵問題：如何將兩個(gè)有序序列合成一個(gè)有序序列？如何將兩個(gè)有序序列合成一個(gè)有序序列？s m m+1 t r s t r1 ijk9.5 9.5 歸

16、并排序歸并排序37具體步驟：將兩個(gè)有序序列rs.m和rm+1.t歸并為有序序列r1s.t的過程： i=s；j=m+1；k=s； 若im 或 jt，執(zhí)行(4)； 比較ri和rj關(guān)鍵字,將較小的存入r1中: 如果ri rj； r1k=ri；i+； k+；執(zhí)行； 否則，r1k=rj; j+; k+;執(zhí)行； 將尚未處理完的子表中元素存入r1； 如果i=m，將rim存入r1kt； 如果j=t，將rjt存入r1kt； 合并結(jié)束。9.5 9.5 歸并排序歸并排序void Merge (int r , int r1 , int s, int m, int t ) i=s; j=m+1; k=s; while

17、(i=m & j=t) if (ri=rj) else while (i=m) /收尾處理收尾處理 r1k+=ri+; /前一個(gè)子序列前一個(gè)子序列 while (j=t) r1k+=rj+; /后一個(gè)子序列后一個(gè)子序列 算法描述：算法描述：r1k=ri；i+；k+; r1k=rj；j+；k+;9.5 9.5 歸并排序歸并排序38關(guān)鍵問題：關(guān)鍵問題：如何將兩個(gè)有序序列合成一個(gè)有序序列？如何將兩個(gè)有序序列合成一個(gè)有序序列？602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j60子序列的長(zhǎng)度一定相等嗎子序列的長(zhǎng)度一定相等嗎?

18、9.5 9.5 歸并排序歸并排序39關(guān)鍵問題：關(guān)鍵問題：怎樣完成一趟歸并？怎樣完成一趟歸并？602031544556520 605 3144 556560 20 31 5 44 55 65 5 20 31 60 44 55 65在一趟歸并中，除最后一個(gè)有序序列外，其它有序在一趟歸并中，除最后一個(gè)有序序列外，其它有序序列中記錄的個(gè)數(shù)相同，用長(zhǎng)度序列中記錄的個(gè)數(shù)相同，用長(zhǎng)度h表示。表示。9.5 9.5 歸并排序歸并排序40關(guān)鍵問題：關(guān)鍵問題：怎樣完成一趟歸并？怎樣完成一趟歸并？現(xiàn)在的任務(wù)是把若干個(gè)長(zhǎng)度為現(xiàn)在的任務(wù)是把若干個(gè)長(zhǎng)度為h的有序序列和最后一個(gè)長(zhǎng)的有序序列和最后一個(gè)長(zhǎng)度有可能小于度有可能小于

19、h的有序序列歸并，設(shè)的有序序列歸并，設(shè)i指向待歸并序列的指向待歸并序列的第一個(gè)記錄，有三種情況：第一個(gè)記錄，有三種情況：若若in-2h+1，則相鄰兩個(gè)有序表的長(zhǎng)度均為則相鄰兩個(gè)有序表的長(zhǎng)度均為h，執(zhí)行執(zhí)行一次歸并，完成后一次歸并，完成后i加加2h，準(zhǔn)備進(jìn)行下一次歸并；準(zhǔn)備進(jìn)行下一次歸并；20 605 3144 5565 70ihi=1n-2h+1=5n-2h+1算法描述：算法描述：while (in-2h+1) Merge (r, r1, i, i+h-1, i+2*h-1); i+=2*h;9.5 9.5 歸并排序歸并排序41若若in-h+1，則表示仍有兩個(gè)相鄰有序表，一個(gè)長(zhǎng)則表示仍有兩個(gè)相

20、鄰有序表，一個(gè)長(zhǎng)度為度為h，另一個(gè)長(zhǎng)度小于另一個(gè)長(zhǎng)度小于h，則執(zhí)行兩個(gè)有序表的歸并，則執(zhí)行兩個(gè)有序表的歸并，完成后退出一趟歸并。完成后退出一趟歸并。20 605 3144 5565ihi=5n-2h+1=4n-h+1=6n-2h+1n-h+1=n-h+1) for (k=i; k=n; k+) r1k=rk; 9.5 9.5 歸并排序歸并排序43void MergePass (int r , int r1 , int n, int h)/對(duì)r做一趟歸并，結(jié)果存入r1 i=1; while (in-2h+1) /長(zhǎng)度均為h的區(qū)間合并 Merge (r, r1, i, i+h-1, i+2*h-1

21、); i+=2*h; if (in-h+1) /長(zhǎng)度不相等的區(qū)間合并 Merge (r, r1, i, i+h-1, n); else for (k=i; k=n; k+) /只有一個(gè)區(qū)間 r1k=rk;一趟歸并排序算法一趟歸并排序算法9.5 9.5 歸并排序歸并排序44解決方法：解決方法： 開始時(shí)，有序序列的長(zhǎng)度開始時(shí)，有序序列的長(zhǎng)度h=1，結(jié)束時(shí)，有序序結(jié)束時(shí)，有序序列的長(zhǎng)度列的長(zhǎng)度h=n，用有序序列的長(zhǎng)度來控制排序的結(jié)束。用有序序列的長(zhǎng)度來控制排序的結(jié)束。關(guān)鍵問題：關(guān)鍵問題：如何控制二路歸并的結(jié)束？如何控制二路歸并的結(jié)束？9.5 9.5 歸并排序歸并排序45算法描述：void Merge

22、Sort (int r , int r1 , int n ) h=1; while (hn) MergePass (r, r1, n, h); /一次合并 h=2*h; /區(qū)間擴(kuò)大 MergePass (r1, r, n, h); /再次合并 h=2*h; 關(guān)鍵問題：關(guān)鍵問題：如何控制二路歸并的結(jié)束？如何控制二路歸并的結(jié)束？9.5 9.5 歸并排序歸并排序46二路歸并排序算法的性能分析二路歸并排序算法的性能分析時(shí)間性能：時(shí)間性能： 二路歸并排序的時(shí)間復(fù)雜度等于歸并趟數(shù)與每一趟時(shí)間復(fù)雜度的乘積。而歸并趟數(shù)為log2n。每一趟歸并就是將兩兩有序子區(qū)間合并成一個(gè)有序子區(qū)間，而每一對(duì)有序子區(qū)間歸并時(shí)，

23、記錄的比較次數(shù)均小于等于記錄的移動(dòng)次數(shù)，而記錄的移動(dòng)次數(shù)等于數(shù)組中記錄的個(gè)數(shù)n，即每一趟歸并的時(shí)間復(fù)雜度為O(n)。因此，二路歸并排序的時(shí)間復(fù)雜度為O(nlog2n)?？臻g性能：空間性能： 算法在執(zhí)行時(shí)，需要占用與原始記錄序列同樣數(shù)量的存儲(chǔ)空間，因此空間復(fù)雜度為O(n)。穩(wěn)定性：穩(wěn)定性： 穩(wěn)定9.5 9.5 歸并排序歸并排序47練習(xí)：一組記錄的排序碼為（25，48，16，35，79，82，23，40，36，72）,其中含有5個(gè)長(zhǎng)度為2的有序表，按歸并排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為（ ）.48（16 25 35 48 23 40 79 82 36 72）9.5 9.5 歸并排序歸并排序

24、主要內(nèi)容499.1 9.1 排序的基本概念排序的基本概念9.2 9.2 插入排序插入排序9.3 9.3 交換排序交換排序9.4 9.4 選擇排序選擇排序9.5 9.5 歸并排序歸并排序9.6 9.6 分配排序分配排序9.7 9.7 性能比較性能比較1. 1. 什么是什么是“多關(guān)鍵字多關(guān)鍵字”排序？實(shí)現(xiàn)方法？排序？實(shí)現(xiàn)方法？例1：對(duì)一副撲克牌該如何排序？ 若規(guī)定花色和面值的順序關(guān)系為： 花色： 面值：2 3 4 5 6 7 8 9 10 J Q K A 可以先按花色排序，花色相同者再按面值排序； 也可以先按面值排序，面值相同者再按花色排序。多關(guān)鍵字排序的實(shí)現(xiàn)方法通常有兩種： 最高位優(yōu)先法MSD

25、(Most Significant Digit first) 最低位優(yōu)先法LSD (Least Significant Digit first)509.6.1 9.6.1 多關(guān)鍵字排序多關(guān)鍵字排序51因?yàn)橛蟹纸M，故此算法需遞歸實(shí)現(xiàn)。例：初始關(guān)鍵字序列T=（32, 13, 27, 32*, 19，33），請(qǐng)分別用MSD和LSD進(jìn)行排序，并討論其優(yōu)缺點(diǎn)。法法1（MSD）：）：原始序列：32, 13, 27, 32*, 19， 33 先按高位Ki1 排序：（13, 19）, 27, （32, 32*，33） 再按低位Ki2 排序 ： 13, 19 ， 27, 32, 32*, 33法法2（LSD）：

26、）： 原始序列： 32, 13, 27, 32*, 19 ，33 先按低位Ki2排序： 32, 32*, 13, 33, 27, 19 再按高位Ki1排序： 13, 19 , 27, 32, 32*, 33無需分組，易編程實(shí)現(xiàn)！9.6.1 9.6.1 多關(guān)鍵字排序多關(guān)鍵字排序52 設(shè)n 個(gè)記錄的序列為：V0, V1, , Vn-1 ，可以把每個(gè)記錄Vi 的單關(guān)鍵碼 Ki 看成是一個(gè)d元組（Ki1, Ki2, , Kid），則其中的每一個(gè)分量Kij ( 1 j d ) 也可看成是一個(gè)關(guān)鍵字。4注1： Ki1最高位，Kid最低位；Ki共有d位，可看成d元組；注2： 每個(gè)分量Kij (1 j d )

27、 有radix種取值，則稱radix為基數(shù)。26(9, 8, 4)(0, 1, , 9)（a, b, , z）(d, i, a, n)310例1：關(guān)鍵碼984可以看成是 元組；基數(shù)radix 為 。例2：關(guān)鍵碼dian可以看成是 元組；基數(shù)radix 為 。u相關(guān)概念：9.6.1 9.6.1 多關(guān)鍵字排序多關(guān)鍵字排序53例：T=（02，77，70，54，64，21，55，11），用LSD排序。分析：各關(guān)鍵字可視為2元組；每位的取值范圍是：0-9；即基數(shù)radix 10 。因此，特設(shè)置10個(gè)隊(duì)列，并編號(hào)為0-9。1155216454707702原始序列12345678先對(duì)低位掃描出隊(duì)012345

28、678910個(gè)隊(duì)列1、計(jì)算機(jī)怎樣實(shí)現(xiàn)LSD算法？分配過程收集過程下一步775564540211217012345678出隊(duì)后序列775554，64217002，119.6.2 基數(shù)排序540123456789再次入隊(duì)再次出隊(duì)再對(duì)高位掃描小結(jié)：小結(jié)：排序時(shí)經(jīng)過了反復(fù)的“分配”和“收集”過程。當(dāng)對(duì)關(guān)鍵字所有的位進(jìn)行掃描排序后，整個(gè)序列便從無序變?yōu)橛行蛄恕?75564540211217012345678出隊(duì)后序列706454211102再次分配再次收集7770645554211102再次出隊(duì)后序列這種LSD排序方法稱為：基數(shù)排序基數(shù)排序，77，55 基數(shù)排序不需要進(jìn)行排序碼的比較，它采用“分配”與“

29、收集”的辦法，是一種借助多關(guān)鍵碼排序的思想實(shí)現(xiàn)單關(guān)鍵字排序的方法。即：用關(guān)鍵字不同的位值進(jìn)行排序。552、基數(shù)排序的基本思想9.6.2 基數(shù)排序563、基數(shù)排序算法的實(shí)現(xiàn)思路 設(shè)待排序的數(shù)據(jù)元素關(guān)鍵字是m位d進(jìn)制整數(shù)（不足 m位的關(guān)鍵字在高位補(bǔ)0），設(shè)置d個(gè)隊(duì)列，令其編號(hào)分別為0,1,2,d-1。（1）按關(guān)鍵字最低位的數(shù)值依次把各數(shù)據(jù)元素放到相應(yīng)的隊(duì)列中；（2）按照隊(duì)列號(hào)從小到大和進(jìn)入隊(duì)列中數(shù)據(jù)元素的先后次序收集分配在各隊(duì)列中的數(shù)據(jù)元素；這樣，就形成了數(shù)據(jù)元素集合的一個(gè)新的排列，稱這樣的一次排序過程為一次基數(shù)排序。（3）再對(duì)得到的數(shù)據(jù)元素序列按關(guān)鍵字次低位的數(shù)值依次把各數(shù)據(jù)元素放到相應(yīng)的隊(duì)列中

30、，重復(fù)收集過程，當(dāng)完成了第m次基數(shù)排序后，就得到了排好序的數(shù)據(jù)元素序列。9.6.2 基數(shù)排序57用鏈隊(duì)列來實(shí)現(xiàn)基數(shù)排序鏈?zhǔn)交鶖?shù)排序?qū)崿F(xiàn)思路：實(shí)現(xiàn)思路： 針對(duì) d 元組中的每一位分量，把原始鏈表中的所有記錄, 按Kij的取值， j = d, d-1, , 1， 先“分配”到radix個(gè)鏈隊(duì)列中去； 然后再按各鏈隊(duì)列的順序，依次把記錄從鏈隊(duì)列中“收集”起來； 分別用這種“分配”、“收集”的運(yùn)算逐趟進(jìn)行排序； 在最后一趟“分配”、“收集” 完成后，所有記錄就按其關(guān)鍵碼的值從小到大排好序了。3、基數(shù)排序算法的實(shí)現(xiàn)思路9.6.2 基數(shù)排序 例：請(qǐng)實(shí)現(xiàn)以下關(guān)鍵字序列的鏈?zhǔn)交鶖?shù)排序：T=（614，738，9

31、21，485，637， 101，215，530，790，306）614921485637738101215530790306第一趟分配第一趟分配e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9原始序列靜態(tài)鏈表：r0（從最低位 i = 3開始排序，f 是隊(duì)首指針，e 為隊(duì)尾指針）第一趟收集第一趟收集（讓隊(duì)尾指針ei 鏈接到下一非空隊(duì)首指針fi+1 即可）530790921101614485215306637738r05859第一趟收集的結(jié)果：第一趟收集的結(jié)果：e0 e1

32、 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9第二趟分配第二趟分配（按次低位 i = 2 ）530790921101614485215306637738第二趟收集第二趟收集（讓隊(duì)尾指針ei 鏈接到下一非空隊(duì)首指針fi+1 ）530790921101614485215306637738r0r060第二趟收集的結(jié)果：第二趟收集的結(jié)果：530790921101614485215306637738e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637

33、101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9第三趟分配（按最高位第三趟分配（按最高位 i = 1 ）第三趟收集第三趟收集（讓隊(duì)尾指針ei 鏈接到下一非空隊(duì)首指針fi+1 ）530790921101614485215306637738r0r0排序結(jié)束！時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：若每個(gè)關(guān)鍵碼有d 位，需要重復(fù)執(zhí)行d 趟“分配”與“收集”。每趟對(duì) n 個(gè)對(duì)象進(jìn)行“分配”，對(duì)radix個(gè)隊(duì)列進(jìn)行“收集”?？倳r(shí)間復(fù)雜度為O(d*n)?？臻g復(fù)雜度：空間復(fù)雜度：算法中需要d次使用n個(gè)結(jié)點(diǎn)臨時(shí)存放n個(gè)數(shù)據(jù)元素，所以空間復(fù)雜度為O（n）。穩(wěn)定性：穩(wěn)定性：基數(shù)排序是穩(wěn)定的排序方法。9.6.3 基數(shù)排序算法分析61主要內(nèi)容629.1 9.1 排序的基本概念排序的基本概念9.2 9.2 插入排序插入排序9.3 9.