數(shù)據(jù)結(jié)構(gòu)練習(xí)

1、數(shù)據(jù)結(jié)構(gòu)練習(xí)1填寫(xiě)下面表格，對(duì)以下幾種排序方法進(jìn)行比較：排序方法平均時(shí)間復(fù)雜度最壞情況空間復(fù)雜度是否穩(wěn)定選擇排序直接選擇排序O(n 2)O(n2)O(1)不穩(wěn)定堆排序O(nlog 2n)O(nlog 2n)O(1)不穩(wěn)定插入排序直接接插入排序O(n 2)O(n2)O(1)穩(wěn)定拆半接插入排序O(nlog 2n)O(n2)O(1)穩(wěn)定Shell 排序O(nlog 2n)O(nlog 2n)O(1)不穩(wěn)定冒泡排序交換排序O(n 2)O(n2)O(1)穩(wěn)定快速排序O(nlog 2n)O(n2)O(1)不穩(wěn)定歸并排序2-路歸并排序O(nlog 2習(xí)題O(nlog2n)O(n)穩(wěn)定n)一填空題O(nlog

2、 2n)O(nlog 2n)O(1)不穩(wěn)定紅黑樹(shù)1 進(jìn)棧序列是 1、 2、 3、 4，進(jìn)棧過(guò)程中可以出棧，則可能的出棧序列有個(gè)，不可能的出棧序列是O(N+K) 。O(N+K)O(N+K)穩(wěn)定線性排序計(jì)數(shù)排序桶排序O(N)O(N)O(N)穩(wěn)定基數(shù)排序O(d(n+rd)O(d(n+rd)O(rd)穩(wěn)定解釋：時(shí)間復(fù)雜度O(d(n+rd) ：其中分配為O（ n）；收集為O（ rd）（ r 為基、d 為“分配收集”的趟數(shù)）2 具有 N 個(gè)元素的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front 和 rear 分別指向隊(duì)頭元素的前一位置和隊(duì)尾元素的位置，則判斷隊(duì)空的和隊(duì)滿的條件分別是f=r和f=rmodm+1。 求 此

3、 隊(duì) 列 中 元 素 個(gè) 數(shù) 的 計(jì) 算 公 式 為 ：(r+m)-f-1) mod m +1。入隊(duì)運(yùn)算：r:=r mod m+1出隊(duì)運(yùn)算：f:=f mod m + 13 單鏈表是非順序線性的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，鏈棧和鏈隊(duì)分別是和4線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)定的，在線性表的鏈接存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)訪問(wèn)決定的。元素存儲(chǔ)地址次序元素存儲(chǔ)指針地址決5深度為 5 的二叉樹(shù)至多有結(jié)點(diǎn)數(shù)為31。6 數(shù)據(jù)結(jié)構(gòu)即數(shù)據(jù)的邏輯結(jié)構(gòu)包括順性存儲(chǔ)結(jié)構(gòu)非線性結(jié)構(gòu)三種類型，樹(shù)型結(jié)構(gòu)和圖型結(jié)構(gòu)稱為？、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)非線性結(jié)構(gòu)。、四種基本存儲(chǔ)方法：（ 1）順序存儲(chǔ)方法（2）鏈接存儲(chǔ)方法（

4、3）索引存儲(chǔ)方法（4）散列存儲(chǔ)方法二選擇題1 有一個(gè) 10 階對(duì)稱矩陣，采用壓縮存儲(chǔ)方式，以行序?yàn)橹餍虼鎯?chǔ)，1，則 A74的地址為（C）A13B18C33D2 線性表采用鏈表存儲(chǔ)時(shí)其存儲(chǔ)地址D。A必須是連續(xù)的B部分地址必須是連續(xù)的C一定是不連續(xù)的D連續(xù)不連續(xù)都可以A0040的地址為3 下列敘述中錯(cuò)誤的是C。A串是一種特殊的線性表，其特殊性體現(xiàn)在數(shù)據(jù)元素是一個(gè)字符B棧和隊(duì)列是兩種特殊的線性表，棧的特點(diǎn)是后進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)先出。C線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表4 一棵二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)如題圖4-1 所示，若中序遍歷該二叉樹(shù)，則遍歷次序?yàn)锳.56

5、7A.C.DBEGACFH DGEBHFCA 1 2 34B.ABDEGCFHD.ABCDEFGH567891011 12 13 14ABCDEFGH題圖4-18設(shè)一棵二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)如題圖A完全二叉樹(shù)BD深度為3 的二叉樹(shù)4-2 所示，則該二叉樹(shù)是滿二叉樹(shù)C深度為C.4 的二叉樹(shù)12345678910111234567題圖4-29設(shè) T 是 Huffman 樹(shù)，它具有6 個(gè)樹(shù)葉，且各樹(shù)葉的權(quán)分別為那么該樹(shù)的非葉子結(jié)點(diǎn)的權(quán)之和為A。A51B21C 30D491， 2， 3， 4，5， 6。7設(shè)有一無(wú)向圖的鄰接矩陣如下所示，則該圖所有頂點(diǎn)的度之和為C。a b c d ea 01110b 1

6、0 1 0 1 c 1 1 0 0 0 d 1 0 0 0 0 e 0 1 0 0 0A8B9C10D 118已知二叉樹(shù)的后序遍歷序列是遍歷序列是D。A defbagcB abcdgefCfedbgca ，中序遍歷序列是dfebagc dbaefcgD abdefcg，則該二叉樹(shù)的先序9由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹(shù)，共有A3B4C5D6C種不同的形態(tài)。10在一個(gè)具有A nBn 個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要 n+1 C n/2 D n-1D條邊11對(duì)線性表進(jìn)行折半（二分）查找時(shí)，要求線性表必須B。A以順序方式存儲(chǔ)B以順序方式存儲(chǔ)且數(shù)據(jù)元素有序C以鏈表方式存儲(chǔ)D以鏈表方式存儲(chǔ)且數(shù)據(jù)元素有序1

7、2順序查找一個(gè)具有n 個(gè)元素的線性表，其時(shí)間復(fù)雜度為A，二分查找一個(gè)具有n 個(gè)元素的線性表，其時(shí)間復(fù)雜度為B。2A O(n)B O(log2n)CO(n)D O(nlog 2n)13. 從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列中的正確位置上，此方法稱為直接插入排序；從未排序序列中挑選元素，并將其放入已排序序列中的一端，此方法稱為直接選擇排序；依次將每?jī)蓚€(gè)相臨的有序表合并成一個(gè)有序表的排序方法稱為歸并排序；當(dāng)兩個(gè)元素比較出現(xiàn)反序時(shí)就相互交換位置的排序方法稱為交換排序；A歸并排序B 選擇排序C交換排序D插入排序三簡(jiǎn)述下面的幾個(gè)概念：?jiǎn)捂湵恚?棧、隊(duì)列，排序二叉樹(shù)。

8、A四簡(jiǎn)述空串和空格串的區(qū)別。五一棵度為 2 的樹(shù)與二叉樹(shù)有何區(qū)別？BC六試分別畫(huà)出具有3 個(gè)結(jié)點(diǎn)的樹(shù)和具有3 個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)。4-3DEF七已知一二叉樹(shù)如題圖所示，1 用二叉鏈表和順序存儲(chǔ)方式分別存儲(chǔ)此二叉樹(shù)。畫(huà)出GH相應(yīng)的存儲(chǔ)結(jié)構(gòu)圖。圖 4-32 寫(xiě)出此二叉樹(shù)的中序、先序、后序遍歷序列。八已知一無(wú)向圖如題圖4-4所示，請(qǐng)給出該圖的11 每個(gè)頂點(diǎn)的度。232 鄰接矩陣43 鄰接表4 按上述的鄰接表寫(xiě)出廣度和深度遍歷序列。56九已知一組數(shù)據(jù)元素為（46， 75， 18， 54， 15， 27， 42， 39，88， 67）題圖 4-41 利用直接插入排序方法，寫(xiě)出每次插入后的結(jié)果。

9、2 利用快速排序方法，寫(xiě)出每趟排序后的結(jié)果。3 利用 2- 路歸并排序方法，寫(xiě)出每趟歸并后的結(jié)果。4 利用冒泡排序方法，寫(xiě)出每趟排序后的結(jié)果。十假定一個(gè)表為（32， 75，63， 48，94， 25，36， 18，70），散列空間為0.10 ，1 若采用除留余數(shù)法構(gòu)造表，哈希函數(shù)為H（ K） =K MOD 11，用線性探測(cè)法解決沖突，試畫(huà)出哈希表，并求在等概率情況下的平均查找長(zhǎng)度。2 若采用除留余數(shù)法構(gòu)造表，哈希函數(shù)為H（ K） =K MOD 11，用鏈地址法解決沖突，試畫(huà)出哈希表，并求在等概率情況下的平均查找長(zhǎng)度。十一有 8 個(gè)帶權(quán)結(jié)點(diǎn)，權(quán)值為（ 3， 7， 8，2， 6， 10， 14，

10、9），試以它們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(shù)（要求每個(gè)結(jié)點(diǎn)左子樹(shù)的權(quán)值小于等于右子樹(shù)的權(quán)值），并計(jì)算出帶權(quán)路徑長(zhǎng)度。十二一對(duì)稱陣 A n*n，若只存儲(chǔ)此對(duì)稱陣的上半三角元，寫(xiě)出以行為主序存儲(chǔ)和以列為主序存儲(chǔ)時(shí)計(jì)算每一元素A ij 存儲(chǔ)地址的公式。十三算法設(shè)計(jì)1 寫(xiě)出在循環(huán)單鏈表L 中查找查找第 i 個(gè)元素的算法：SEARCH （ L ， i）。2 設(shè)有如下題圖4-3 的單鏈表，鏈表頭指針為H ，寫(xiě)一個(gè)將鏈表進(jìn)行逆轉(zhuǎn)的算法，逆轉(zhuǎn)以后的鏈表為題圖4-4 所示。HaaaNULL12n題圖 4-3 單鏈表示意圖HaaaNULLnn-11題圖 4-4 單鏈表示意圖3 假定用一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表表示循環(huán)隊(duì)

11、列（循環(huán)鏈隊(duì)），該隊(duì)列只設(shè)一個(gè)隊(duì)尾指針，不設(shè)頭指針，試編寫(xiě)下面的算法：A 向循環(huán)鏈隊(duì)中插入一個(gè)元素x 的算法（入隊(duì)） 。B 從循環(huán)鏈隊(duì)中刪除一個(gè)結(jié)點(diǎn)（出隊(duì)）。4 數(shù)組 AN 存放循環(huán)隊(duì)列中的元素， 同時(shí)設(shè)兩個(gè)變量分別存儲(chǔ)隊(duì)尾元素的位置和隊(duì)列中實(shí)際元素個(gè)數(shù)。A 寫(xiě)出此隊(duì)列的隊(duì)滿條件。B 寫(xiě)出此隊(duì)列的出、入隊(duì)算法。5 設(shè) LA 和 LB 為兩個(gè)順序存儲(chǔ)的線性表，且元素按非遞減排列，寫(xiě)出算法將其合并為L(zhǎng)C ，且 LC 中的元素也按非遞減排列。6 已知一個(gè)由n 個(gè)整數(shù)組成的線性表，請(qǐng)定義該線性表的一種存儲(chǔ)結(jié)構(gòu)，并用C 語(yǔ)言編寫(xiě)算法，實(shí)現(xiàn)將 n 個(gè)元素中所有大于等于20 的整數(shù)放在所有小于等于20 的整

12、數(shù)之后，要求算法的時(shí)間復(fù)雜度為O（ n） , 空間復(fù)雜度為O（1）。7 編寫(xiě)算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。8 編寫(xiě)一個(gè)按層次順序（同一層自左向右）遍歷二叉樹(shù)的算法。文中代碼見(jiàn)原文鏈接： 非基于比較的排序在計(jì)算機(jī)科學(xué)中， 排序是一門(mén)基礎(chǔ)的算法技術(shù)， 許多算法都要以此作為基礎(chǔ)， 不同的排序算法有著不同的時(shí)間開(kāi)銷和空間開(kāi)銷。 排序算法有非常多種， 如我們最常用的快速排序和堆排序等算法，這些算法需要對(duì)序列中的數(shù)據(jù)進(jìn)行比較，因?yàn)楸环Q為 基于比較的排序 。基于比較的排序算法是不能突破O(NlogN)的。簡(jiǎn)單證明如下：N 個(gè)數(shù)有 N! 個(gè)可能的排列情況，也就是說(shuō)基于比較的排序算法的判定樹(shù)有比較次數(shù)至少為

13、 log(N!)=O(NlogN)( 斯特林公式 ) 。N! 個(gè)葉子結(jié)點(diǎn)，而非基于比較的排序，如計(jì)數(shù)排序， 桶排序，和在此基礎(chǔ)上的基數(shù)排序，則可以突破O(NlogN)時(shí)間下限。 但要注意的是， 非基于比較的排序算法的使用都是有條件限制的， 例如元素的大小限制， 相反，基于比較的排序則沒(méi)有這種限制 ( 在一定范圍內(nèi) ) 。但并非因?yàn)橛袟l件限制就會(huì)使非基于比較的排序算法變得無(wú)用， 對(duì)于特定場(chǎng)合有著特殊的性質(zhì)數(shù)據(jù)， 非基于比較的排序算法則能夠非常巧妙地解決。本文著重介紹三種線性的非基于比較的排序算法：計(jì)數(shù)排序、桶排序與基數(shù)排序。 計(jì)數(shù)排序首先從 計(jì)數(shù)排序 (Counting Sort)開(kāi)始介紹起，假

14、設(shè)我們有一個(gè)待排序的整數(shù)序列A，其中元素的最小值不小于0 ，最大值不超過(guò)K 。建立一個(gè)長(zhǎng)度為K 的線性表C，用來(lái)記錄不大于每個(gè)值的元素的個(gè)數(shù)。算法思路如下：?掃描序列A，以 A 中的每個(gè)元素的值為索引，把出現(xiàn)的個(gè)數(shù)填入可以表示A 中值為 i 的元素的個(gè)數(shù)。對(duì)于 C 從頭開(kāi)始累加，使Ci-Ci+Ci-1。這樣， Ci的元素的個(gè)數(shù)。C 中。此時(shí)Ci就表示 A 中值不大于i? 按照統(tǒng)計(jì)出的值，輸出結(jié)果。由線性表 C 我們可以很方便地求出排序后的數(shù)據(jù)，定義B 為目標(biāo)的序列， Orderi為排名第 i 的元素在 A 中的位置，則可以用以下方法統(tǒng)計(jì)。CPP1/* Memo: 計(jì)數(shù)排序 */23#inclu

15、de 4#include 5#include 6#include 7#include 8usingnamespacestd ;9voidCountingSort( int * A, int * B, int * Order, int N, intK )10 11121314151617181920212223int* C=newint K+1 ;inti;memset ( C, 0, sizeof( int) * ( K+1) ;for( i =1; i =N; i +)/ 把 A 中的每個(gè)元素分配C A i + ;for( i =2; i =1; i - )B C A i =A i ;/按照

16、統(tǒng)計(jì)的位置，將值輸出到B24 中，將順序輸出到 Order 中2526Order C A i =i ;27C A i - ;2829 30 int main ()31 32int * A, * B, * Order,N =15 ,K =10 ,i ;33A=newint N+1;34B=newint N+1;353637383940414243444546474849Order=newint N+1 ;for( i =1; i =N; i +)A i =rand ()%K+1; /生成 1.K的隨機(jī)數(shù)printf( Before CS:/n ) ;for( i =1; i =N; i +)pr

17、intf( %d ,A i );CountingSort( A,B,Order,N,K) ;printf( /nAfter CS:/n ) ;for( i =1; i =N; i +)printf( %d ,B i );printf( /nOrder: /n ) ;for( i =1; i =N; i +)printf( %d ,Order i ) ;return0;程序運(yùn)行效果如下：Before CS:After CS:Order:顯然地，計(jì)數(shù)排序的時(shí)間復(fù)雜度為 O(N+K) ，空間復(fù)雜度為 O(N+K) 。當(dāng) K 不是很大時(shí)，這是一個(gè)很有效的線性排序算法。 更重要的是， 它是一種 穩(wěn)定排序

18、算法 ，即排序后的相同值的元素原有的相對(duì)位置不會(huì)發(fā)生改變 ( 表現(xiàn)在 Order 上 ) ，這是計(jì)數(shù)排序很重要的一個(gè)性質(zhì)，就是根據(jù)這個(gè)性質(zhì)，我們才能把它應(yīng)用到基數(shù)排序。桶排序可能你會(huì)發(fā)現(xiàn)， 計(jì)數(shù)排序似乎饒了點(diǎn)彎子，比如當(dāng)我們剛剛統(tǒng)計(jì)出C，Ci 可以表示A 中值為 i 的元素的個(gè)數(shù)，此時(shí)我們直接順序地掃描C，就可以求出排序后的結(jié)果。的確是這樣，不過(guò)這種方法不再是計(jì)數(shù)排序，而是桶排序 (Bucket Sort)，確切地說(shuō)，是桶排序的一種特殊情況。用這種方法，可以很容易寫(xiě)出程序，比計(jì)數(shù)排序還簡(jiǎn)單，只是不能求出穩(wěn)定的Order 。CPP12/* Memo:桶排序特殊實(shí)現(xiàn) */3 #include 4

19、#include 5 #include 6 #include 7 #include 8usingnamespacestd;9voidBucketSort( int* A, int * B, int N, int K )1011int* C=new int K+1 ;12inti,j,k;13memset ( C, 0, sizeof ( int)*(K+1) ;14for( i =1; i =N; i +) / 把 A 中的每個(gè)元素按照值放入桶中15C A i + ;1617for( i =j =1; i = K; i + ,j=k ) / 統(tǒng)計(jì)每個(gè)桶元素的個(gè)數(shù)，并輸1819出到 B2021f

20、or( k =j ; kj +C i ; k +)22B k =i ;23 24 int main ()25 26int* A, * B,N =1000 ,K =1000 ,i;27A=newint N+1 ;28B=newint N+1 ;29for( i =1; i =N; i +)30A i =rand ()%K+1; /生成 1.K的隨機(jī)數(shù)31BucketSort( A,B,N,K) ;3233for( i =1; i =N; i +)34printf ( %d ,B i );35return0;36這種特殊實(shí)現(xiàn)的方式時(shí)間復(fù)雜度為 O(N+K) 素都要在 K 的范圍內(nèi)。更一般的，如果我

21、們的，空間復(fù)雜度也為O(N+K)K 很大，無(wú)法直接開(kāi)出O(K)，同樣要求每個(gè)元的空間該如何呢？首先定義桶， 桶為一個(gè)數(shù)據(jù)容器，每個(gè)桶存儲(chǔ)一個(gè)區(qū)間內(nèi)的數(shù)。依然有一個(gè)待排序的整數(shù)序列 A ，元素的最小值不小于0 ，最大值不超過(guò)K 。假設(shè)我們有M 個(gè)桶，第i 個(gè)桶 Bucketi存儲(chǔ) i*K/M至 (i+1)*K/M之間的數(shù)，有如下桶排序的一般方法：?掃描序列A，根據(jù)每個(gè)元素的值所屬的區(qū)間，放入指定的桶中( 順序放置) 。? 對(duì)每個(gè)桶中的元素進(jìn)行排序，什么排序算法都可以，例如快速排序。? 依次收集每個(gè)桶中的元素，順序放置到輸出序列中。對(duì)該算法簡(jiǎn)單分析，如果數(shù)據(jù)是期望平均分布的，則每個(gè)桶中的元素平均個(gè)

22、數(shù)為N/M。如果對(duì)每個(gè)桶中的元素排序使用的算法是快速排序，每次排序的時(shí)間復(fù)雜度為O(N/M*log(N/M)N*log(N/M) =。則總的時(shí)間復(fù)雜度為O(N)+O(M)*O(N/M*log(N/M) = O(N+O(N + N*logN N*logM)。當(dāng) M 接近于 N 是，桶排序的時(shí)間復(fù)雜度就可以近似認(rèn)為是 O(N) 的。就是桶越多，時(shí)間效率就越高，而桶越多，空間卻就越大，由此可見(jiàn)時(shí)間和空間是一個(gè)矛盾的兩個(gè)方面。桶中元素的順序放入和順序取出是有必要的，因?yàn)檫@樣可以確定桶排序是一種法，配合基數(shù)排序是很好用的。穩(wěn)定排序算CPP12/* Memo:桶排序一般實(shí)現(xiàn) */3 #include 4

23、#include 5 #include 6 #include 7 #include 8usingnamespacestd;9structlinklist10linklist* next;1112int value;13linklist( intv,linklist* n) : value( v) ,next ( n)14 ;linklist() if( next )deletenext; 1516 inlineintcmp ( constvoid* a, constvoid* b)17return* ( int* ) a -*( int* ) b;1819 20 /*21 為了方便，我把 A

24、中元素加入桶中時(shí)是倒序放入的，而收集取出時(shí)也是倒序2223 放入序列的，所以不違背穩(wěn)定排序。24 */25 void26 27282930313233343536 桶中3738394041424344BucketSort( int* A, int* B, intN, intK )linklist* Bucket 101 , * p; / 建立桶inti,j,k,M;M=K/ 100 ;memset ( Bucket,0, sizeof( Bucket) ;for( i =1; i =N; i +)k =A i / M;/ 把 A 中的每個(gè)元素按照的范圍值放入對(duì)應(yīng)Bucket k =new li

25、nklist( A i ,Bucket k ) ;for( k =j =0; knext )B +j =p - value; / 把桶中每個(gè)元素取出， 排45 序并加入 B4647deleteBucket k ;48qsort( B+i +1,j- i, sizeof ( B 0) ,cmp ) ;4950 51 int main ()52 53int* A, * B,N =100 ,K =10000 ,i ;54A=newint N+1;55B=newint N+1;56for( i =1;i =N; i +)57A i =rand ()%K+1; / 生成 1.K的隨機(jī)數(shù)58BucketS

26、ort ( A,B,N,K) ;59for( i =1; i =N; i +)printf( %d return0;,B i ); 基數(shù)排序 下面說(shuō)到我們的重頭戲， 基數(shù)排序 (Radix Sort)。上述的基數(shù)排序和桶排序都只是在研究一個(gè)關(guān)鍵字的排序，現(xiàn)在我們來(lái)討論有多個(gè)關(guān)鍵字的排序問(wèn)題。假設(shè)我們有一些二元組 (a,b) ，要對(duì)它們進(jìn)行以a 為首要關(guān)鍵字， b 的次要關(guān)鍵字的排序。我們可以先把它們先按照首要關(guān)鍵字排序，分成首要關(guān)鍵字相同的若干堆。然后，在按照次要關(guān)鍵值分別對(duì)每一堆進(jìn)行單獨(dú)排序。最后再把這些堆串連到一起，使首要關(guān)鍵字較小的一堆排在上面。按這種方式的基數(shù)排序稱為MSD(Most

27、Significant Dight)排序。第二種方式是從最低有效關(guān)鍵字開(kāi)始排序，稱為L(zhǎng)SD(Least Significant Dight)排序。首先對(duì)所有的數(shù)據(jù)按照次要關(guān)鍵字排序，然后對(duì)所有的數(shù)據(jù)按照首要關(guān)鍵字排序。要注意的是，使用的排序算法必須是穩(wěn)定的，否則就會(huì)取消前一次排序的結(jié)果。由于不需要分堆對(duì)每堆單獨(dú)排序， LSD 方法往往比 MSD 簡(jiǎn)單而開(kāi)銷小。下文介紹的方法全部是基于LSD 的。通常，基數(shù)排序要用到計(jì)數(shù)排序或者桶排序。使用計(jì)數(shù)排序時(shí)，需要的是Order 數(shù)組。使用桶排序時(shí)， 可以用鏈表的方法直接求出排序后的順序。下面是一段用桶排序?qū)ΧM基數(shù)排序的程序：CPP12/* Memo

28、:基數(shù)排序結(jié)構(gòu)數(shù)組 */3 #include 4 #include 5 #include 6 #include 7 #include 8usingnamespace std ;9structdata10int key 2 ;1112 ;13structlinklist1415linklist* next;16data value;17linklist( data v,linklist* n) : value( v ) ,next ( n)18linklist() if( next)deletenext; 19 ;20void BucketSort( data* A, intN,intK,int

29、y )2122linklist* Bucket 101 , * p; / 建立桶2324inti,j,k,M;25M=K/ 100 +1;26memset ( Bucket,0, sizeof( Bucket) ;27for( i =1; i =N; i +)2829k =A i . key y / M;/把 A 中的每個(gè)元素按照的范圍值3031 放入對(duì)應(yīng)桶中32Bucket k =new linklist( A i ,Bucket k ) ;3334for( k =j =0; knext ) j + ;3637for( p=Bucket k ,i=1; p; p=p- next,i+)38A j - i +1 =p - value ; / 把桶中每個(gè)元素取出39del