數(shù)據(jù)結構第章排序2選擇排序歸并排序基數(shù)排序ppt課件

1、武漢科技大學Wuhan University of Science and Technology張 凱計算機學院 軟件工程系2019年3月12日:第第1010章章 內部排序內部排序選擇排序 (直接排序、堆排序)概述插入排序 (直接排序、折半排序、希爾排序)交換排序 (冒泡排序、快速排序)歸并排序基數(shù)排序:v選擇排序選擇排序10.4 選擇排序選擇排序根本思想： 第i趟在n-i+1(i=1,2,n-1)個記錄中選取關鍵字最小的記錄作為有序序列中的第i個記錄。1.簡單項選擇擇排序2.樹形選擇排序3.堆排序:v簡單項選擇擇排序簡單項選擇擇排序 10.4 選擇排序選擇排序排序過程： 首先經(jīng)過 n 1 次

2、關鍵字比較，從 n 個記錄中找出關鍵字最小的記錄，將它與第一個記錄交換。 再經(jīng)過 n 2 次比較，從剩余的 n 1 個記錄中找出關鍵字次小的記錄，將它與第二個記錄交換。 反復上述操作，共進展 n 1 趟排序后，排序終了。 :v簡單項選擇擇排序簡單項選擇擇排序 10.4 選擇排序選擇排序例： 初始： 49 38 65 97 76 13 27 jjjjjjki =1 13 49 一趟： 13 38 65 97 76 49 27 i =2 二趟： 13 27 65 97 76 49 38 三趟： 13 27 38 97 76 49 65 四趟： 13 27 38 49 76 97 65 五趟： 13

3、 27 38 49 65 97 76 六趟： 13 27 38 49 65 76 97 排序終了：六趟： 13 27 38 49 65 76 97 kki =6 i =3 i =4 i =5 比較次數(shù) n - 1 n - 2 n - 6 :v簡單項選擇擇排序算法描畫簡單項選擇擇排序算法描畫10.4 選擇排序選擇排序void SelectSort (SqList &L) / 對順序表對順序表 L 作簡單項選擇擇排作簡單項選擇擇排序序 for (i = 1; i L.length; + i) k = i; for ( j = i+1; j = n; j+) if (L.rj.key L.r

4、k.key) k = j; if (i != k) L.riL.rk; / 與第與第 i 個記錄交換個記錄交換 / SelectSort :v簡單項選擇擇排序算法分析簡單項選擇擇排序算法分析10.4 選擇排序選擇排序 由于存在著不相鄰元素之間的互換，因此，簡單項選擇擇排序是“不穩(wěn)定的 。 算法實現(xiàn)共需求進展n-1 次選擇，每次選擇需求進展n-i次比較(1in-1)，而每次交換最多需3次挪動，因此，總的比較次數(shù) C = n(n-1)/2，總的挪動次數(shù) M = 3(n-1)。故其時間復雜度為O(n2)。 空間效率：O(1)交換時用到一個暫存單元:v樹形選擇排序樹形選擇排序 (又稱錦標賽排序又稱錦標

5、賽排序 )10.4 選擇排序選擇排序根本思想：與體育競賽時的淘汰賽類似。 首先對 n 個記錄的關鍵字進展兩兩比較，得到 n/2 個優(yōu)勝者(關鍵字小者)，作為第一步比較的結果保管下來。然后在這 n/2 個較小者之間再進展兩兩比較，如此反復，直到選出最小關鍵字的記錄為止。例：關鍵字序列T= 21，25，49，25*，16，08，63，請給出錦標賽排序的詳細實現(xiàn)過程。:08Winner (勝者)2108086325*2121254925*160863r1注：為便于自動處置，建議每個記錄多開兩個特殊分量：keyotherinfoIndex(結點位置編號）結點位置編號）Tag（是否參加比較）（是否參加比

6、較）初態(tài)補足2k( k=log2n )個葉子結點第一趟：Tree8Tree9Tree10Tree11Tree12Tree13Tree14Tree15:第二趟：082108086325*2121254925*160863161616r2Winner (勝者)求次小值16時,只需比較2次，即只比較log2n -1次。令其Tag0,不參與比較:令其Tag0,不參與比較第三趟：162116166325*2121254925*160863r3Winner (勝者)6321:082108086325*2121254925*1608636321第四趟：r4Winner (勝者)252525:08210808

7、6325*2121254925*1608631616166321252525第五趟：r5Winner (勝者)25*25*:082108086325*2121254925*160863161616632125252525*25*第六趟：r6Winner (勝者)494949:082108086325*2121254925*160863161616632125252525*25*494949第七趟：r7Winner (勝者)63:v樹形選擇排序算法樹形選擇排序算法10.4 選擇排序選擇排序勝者樹數(shù)據(jù)結點類的定義DataNode Type data; /數(shù)據(jù)值數(shù)據(jù)值 int index; /結點在

8、滿二叉樹中順序號結點在滿二叉樹中順序號int active; /參選標志：參選標志：=1, 參選參選, =0, 不參選不參選:錦標賽排序的算法錦標賽排序的算法 void TournamentSort ( Type a , int n ) int bottomRowSize = PowerOfTwo ( n ); /乘冪值乘冪值 計算滿足計算滿足n的的2的最小次冪的數(shù)的最小次冪的數(shù)int TreeSize = 2*bottomRowSize-1; /總結點個數(shù)總結點個數(shù)int loadindex = bottomRowSize-1; /內結點個數(shù)內結點個數(shù)DataNode treeTreeSiz

9、e;int j = 0; /從從 a 向勝者樹外結點復制數(shù)據(jù)向勝者樹外結點復制數(shù)據(jù)for ( int i = loadindex; i TreeSize; i+) treei.index = i; if ( j n ) treei.active = 1; treei.data = aj+; else treei.active = 0; i = loadindex; /進展初始比較選擇最小的項進展初始比較選擇最小的項while ( i ) j = i;while ( j 2*i ) if ( !treej+1.active|treej.data treej+1.data ) /勝者送入雙親勝者送

10、入雙親tree(j-1)/2 = treej; elsetree(j-1)/2 = treej+1;j += 2;i = (i-1)/2; / i 退到雙親退到雙親, 直到直到 i=0為止為止for ( i = 0; i n-1; i+) /處置其它n-1個數(shù)據(jù)ai = tree0.data; /送出最小數(shù)據(jù)treetree0.index.active = 0; /失去參選資歷 UpdateTree ( tree, tree0.index ); /調整an-1 = tree0.data; / TournamentSort :錦標賽排序中的調整算法錦標賽排序中的調整算法 void UpdateT

11、ree ( DataNode *tree, int i ) if ( i %2 = 0 )tree(i-1)/2 = treei-1; /i偶數(shù)偶數(shù), 對手左結點對手左結點elsetree(i-1)/2 = treei+1; /i奇數(shù)奇數(shù), 對手右結點對手右結點i = (i-1) / 2; /向上調整向上調整 while ( i ) /直到直到 i=0if ( i %2 = 0) j = i-1;else j = i+1;if ( !treei.active | !treej.active )if ( treei.active )tree(i-1)/2 = treei; /i可參選可參選, i

12、上上else tree(i-1)/2 = treej; /否那么否那么, j上上else /兩方都可參選兩方都可參選 if ( treei.data treej.data ) tree(i-1)/2 = treei; /關鍵碼小者上關鍵碼小者上else tree(i-1)/2 = treej;i = (i-1) / 2; / i上升到雙親上升到雙親:v樹形選擇排序算法分析樹形選擇排序算法分析10.4 選擇排序選擇排序 錦標賽排序構成的樹是滿(完全)二叉樹，其深度為 log2n +1，其中 n為待排序元素個數(shù)。 時間復雜度：O(nlog2n) n個記錄各自比較約log2n次 空間效率：O(n)

13、勝者樹的附加內結點共有n-1個！ 穩(wěn)定性：穩(wěn)定 左右結點一樣者左為先n =2k = 葉子總數(shù):v堆排序堆排序10.4 選擇排序選擇排序1. 什么是堆？堆的定義：設有n個元素的序列k1，k2，kn，當且僅當滿足下述關系之一時，稱之為堆。 ki k2iki k2i+1ki k2iki k2i+1或者i=1, 2, n/22. 怎樣建堆？3. 怎樣堆排序？解釋：假設讓滿足以上條件的元素序列(k1，k2，kn)依次排成一棵完全二叉樹，那么此樹的特點是：樹中一切結點的值均大于(或小于)其左右孩子，此樹的根結點(即堆頂)必最大(或最小) 。:v堆排序堆排序10.4 選擇排序選擇排序082546495867

14、234561大根堆918566765867234561557例：有序列T1=08, 25, 49, 46, 58, 67和序列T2=91, 85, 76, 66, 58, 67, 55,判別它們能否 “堆？小根堆小頂堆 最小堆大頂堆最大堆:v怎樣建堆？怎樣建堆？10.4 選擇排序選擇排序 將排序碼 k1,k2,k3 ,kn 表示成一棵完全二叉樹，然后從第 n/2 個排序碼即最右邊的非終端結點開場挑選，使由該結點作為根結點組成的子二叉樹符合堆的定義，然后從第 n/2 - 1個排序碼反復剛剛操作，直到第一個排序碼即根止。這時候，該二叉樹符合堆的定義，初始堆曾經(jīng)建立。:v怎樣建堆？怎樣建堆？10.4

15、 選擇排序選擇排序212525491608123456例：關鍵字序列T= (21，25，49，25，16，08，請建大根堆為便于了解，先將原始序列畫成完全二叉樹的方式21i=3:49而且21還該當向下比較！i=1: 21小于25和49，要調整！49大于08，不用調整；i=2: 25大于等于25和16，不用調整；完全二叉樹的最右一個非終端結點編號必為n/2 ！(性質5)注：終端結點即葉子沒有任何子女，無需單獨調整。:v怎樣建堆？怎樣建堆？10.4 選擇排序選擇排序這個自堆頂至葉子的調整過程稱為“挑選。 挑選: 假假設完全二叉樹的某一個結點i，它的左、右子樹已是堆。需求將R2i.key與R2i+1

16、.key之中的最小者與Ri.key比較，假設Ri.key較大那么交換，這有能夠破壞下一級堆。于是繼續(xù)采用上述方法構造下一級堆，直到完全二叉樹中結點i構成堆為止。:v怎樣建堆？怎樣建堆？10.4 選擇排序選擇排序:v怎樣建堆？怎樣建堆？10.4 選擇排序選擇排序 void HeapAdjust(SqList H， int s， int m) /知知H.rs.m中記錄的關鍵字除中記錄的關鍵字除H.rs.key之外均滿足堆的定義，之外均滿足堆的定義，/本函數(shù)調整本函數(shù)調整H.rs的關鍵字，使的關鍵字，使H.rs.m成為一個大頂堆成為一個大頂堆 rc = H.rs; for (j=2*s; j=m;

17、j*=2) /沿沿key較大的孩子結點向下挑選較大的孩子結點向下挑選, j為為key較大的記錄的下標較大的記錄的下標 if(j0;-i) /把把H.r1.length建成大頂堆建成大頂堆 HeapAdjust(H,i,H.length); for(i=H.length; i1; -i) /將堆頂記錄和當前未經(jīng)排將堆頂記錄和當前未經(jīng)排 /序子序列序子序列H.r.1.i中最后一個記錄相互交換中最后一個記錄相互交換 H.r1 H.ri； HeapAdjust(H,1,i-1); /將將H.R1.i-1重新調整為大頂堆重新調整為大頂堆 /HeapSort :v附附1：基于初始堆進展堆排序的算法步驟：基

18、于初始堆進展堆排序的算法步驟10.4 選擇排序選擇排序1.堆的第一個對象V0具有最大的關鍵碼，將V0與Vn對調，把具有最大關鍵碼的對象交換到最后，再對前面的n-1個對象，運用堆的調整算法，重新建立堆。結果具有次最大關鍵碼的對象又上浮到堆頂，即V0位置。2.再對調V0和Vn-1，調用對前n-2個對象重新調整，如此反復，最后得到全部排序好的對象序列。:rc = H.rs; j = 2s; jm &H.rj.keyH.rj+1.key+ j; / 指向右兄弟j H.rj.keyH.rs=H.rj; s=j;j=2*j; /指向左孩子NNNYYYH.rsm中除rs外，其他具有堆特征現(xiàn)調整rs的

19、值 ，使H.rsm為堆附2：算法流程比較左右孩子大小，j指向大者比較大孩子與rc的大小假設大向上浮:v堆排序的效率分析堆排序的效率分析10.4 選擇排序選擇排序 在整個堆排序中，共需求進展 n+n/2 -1 次挑選運算，每次挑選運算進展雙親和孩子或兄弟結點的排序碼的比較和挪動次數(shù)都不會超越完全二叉樹的深度。故每次挑選運算的時間復雜度為O(log2n)，那么整個堆排序過程的時間復雜度為O(nlog2n) 。 堆排序在最壞情況下，時間復雜度也為O(nlog2n)。相對于快速排序，這是堆排序的最大優(yōu)點。此外，堆排序僅需一個記錄大小輔助存儲空間供交換運用。 由于存在著不相鄰元素之間的互換，因此，堆排序

20、是一種不穩(wěn)定的排序方法。:v堆排序的效率分析堆排序的效率分析10.4 選擇排序選擇排序 時間效率： O(nlog2n)。由于整個排序過程中需求調用n-1次HeapAdjust( )算法， HeapAdjust( )而算法本身耗時為log2n； 空間效率：O(1)。僅在第二個for循環(huán)中交換記錄時用到一個暫時變量temp。 穩(wěn)定性： 不穩(wěn)定。 優(yōu)點：對少量數(shù)據(jù)效果不明顯，但對大量數(shù)據(jù)有效。:v歸并排序歸并排序10.5 歸并排序歸并排序歸并排序的根本思想是：將兩個(或以上)的有序表組成新的有序表。更實踐的意義：可以把一個長度為n的無序序列看成是 n 個長度為 1 的有序子序列 ，首先做兩兩歸并，得

21、到 n / 2 個長度為 2 的子序列 ；再做兩兩歸并，如此反復，直到最后得到一個長度為n 的有序序列。:v歸并排序歸并排序10.5 歸并排序歸并排序初始關鍵字： 49 38 65 97 76 13 27 一趟歸并后： 38 49 65 97 13 76 27 二趟歸并后： 38 49 65 97 13 27 76 三趟歸并后： 13 27 38 49 65 76 97 看成是 n 個有序的子序列(長度為 1)，然后兩兩歸并。 得到 n/2 個長度為2 或 1 的有序子序列。 :v歸并排序歸并排序10.5 歸并排序歸并排序例：關鍵字序列T= 21，25，49，25*，93，62，72，08，3

22、7，16，54，請給出歸并排序的詳細實現(xiàn)過程。:212525*9362720837165449212525* 49629308721637541637542125 25* 4908627293082125 25* 4962729308162125 25* 374954 627293len=1len=2len=4len=8len=16163754整個歸并排序僅需log2n趟:v一趟歸并排序算法一趟歸并排序算法 (兩路有序并為一路兩路有序并為一路) 10.5 歸并排序歸并排序void Merge (SR，&TR，i, m, n) / 將有序的SRim和SRm+1n歸并為有序的TRin fo

23、r(k=i , j=m+1; i=m & j=n; +k ) if ( SRi= SRj )TRk=SRi+; else TRk=SRj+; / 將SR中記錄由小到大地并入TR if (i=m) TRkn=SRim; / 將剩余的SRim復制到TR if (j=n) TRkn=SRjn; / 將剩余的SRjn復制到TR / Merge:v遞歸方式的兩路歸并排序算法遞歸方式的兩路歸并排序算法10.5 歸并排序歸并排序 void MSort (SR，&TR1，s, t) / 將無序的SRst歸并排序為TR1st if ( s=t )TR1s=SRs; / 當len=1時前往 els

24、e m=(s+t)/2; / 將SR st平分為SR sm和SR m+1t MSort (SR，&TR2，s, m); / 將SR 一分為二, 2分為4 / 遞歸地將SR sm歸并為有序的TR2sm MSort (SR，&TR2，m+1, t ); / 遞歸地將SR m+1t歸并為有序的TR2m+1t Merge(TR2， TR1， s, m, t ); / 將TR2 sm和TR2 m+1t歸并到TR1 st / MSort簡言之，先由“長無序變成“短有序， 再從“短有序歸并為“長有序。初次調用時為L, TR, 1, length:v歸并排序算法分析歸并排序算法分析10.5 歸

25、并排序歸并排序 時間效率 O(nlog2n) 一趟歸并排序的操作是：調用n/2h次算法merge將SR1.n中前后相鄰且長度為h的有序段進展兩兩歸并，得到前后相鄰長度為2h的有序段，并存放在TR1.n中，整個歸并排序需求進展log2n趟，所以算法總的時間復雜度為O(nlog2n)。 空間效率 O(n) 由于需求一個與原始序列同樣大小的輔助序列(TR)。這正是此算法的缺陷。 穩(wěn)定性：穩(wěn)定:v基數(shù)排序基數(shù)排序 10.6 基數(shù)排序基數(shù)排序 要討論的問題：1. 什么是“多關鍵字排序？實現(xiàn)方法？2. 單邏輯關鍵字怎樣“按位值排序？根本思想：借助多關鍵字排序的思想對單邏輯關鍵字進展排序。即：用關鍵字不同的

26、位值進展排序。:v基數(shù)排序基數(shù)排序 10.6 基數(shù)排序基數(shù)排序 1. 什么是“多關鍵字排序？實現(xiàn)方法？例1：對一副撲克牌該如何排序？假設規(guī)定花樣和面值的順序關系為：花樣： 面值：2 3 4 5 6 7 8 9 10 J Q K A(1)可以先按花樣排序，花樣一樣者再按面值排序；(2)可以先按面值排序，面值一樣者再按花樣排序。:v基數(shù)排序基數(shù)排序 10.6 基數(shù)排序基數(shù)排序 1. 什么是“多關鍵字排序？實現(xiàn)方法？例2：職工分房該如何排序？規(guī)定：先以總分排序職稱分工齡分；總分一樣者，再按配偶總分排序，其次按配偶職稱、工齡、人口等等排序。:v基數(shù)排序基數(shù)排序 10.6 基數(shù)排序基數(shù)排序 多關鍵字排序

27、的實現(xiàn)方法通常有兩種： 最高位優(yōu)先法MSD (Most Significant Digit first) 最低位優(yōu)先法LSD (Least Significant Digit first):v基數(shù)排序基數(shù)排序 10.6 基數(shù)排序基數(shù)排序 例：對一副撲克牌該如何排序？答：假設規(guī)定花樣為第一關鍵字高位，面值為第二關鍵字低位，那么運用MSD和LSD方法都可以到達排序目的。MSD方法的思緒：先設立4個花樣“箱，將全部牌按花樣分別歸入4個箱內每個箱中有13張牌；然后對每個箱中的牌按面值進展插入排序或其它穩(wěn)定算法。LSD方法的思緒：先按面值分成13堆每堆4張牌，然后對每堆中的牌按花樣進展排序用插入排序等穩(wěn)

28、定的算法。:v基數(shù)排序基數(shù)排序 10.6 基數(shù)排序基數(shù)排序 2. 單邏輯關鍵字怎樣“按位值排序？設n個記錄的序列為：V0, V1, , Vn-1 ，可以把每個記錄Vi 的單關鍵碼 Ki 看成是一個d元組Ki1, Ki2, , Kid，那么其中的每一個分量Kij ( 1 j d ) 也可看成是一個關鍵字。注1: Ki1最高位，Kid最低位；Ki共有d位，可看成d元組注2: 每個分量Kij (1 j d ) 有radix種取值，那么稱radix為基數(shù)思緒：:v基數(shù)排序基數(shù)排序 10.6 基數(shù)排序基數(shù)排序 426(9, 8, 4)(0, 1, , 9)a, b, , z(d, i, a, n)310

29、例1：關鍵碼984可以看成是 元組；基數(shù)radix 為 。例2：關鍵碼dian可以看成是 元組；基數(shù)radix 為 。:v基數(shù)排序基數(shù)排序 10.6 基數(shù)排序基數(shù)排序 :v基數(shù)排序基數(shù)排序 10.6 基數(shù)排序基數(shù)排序 例：初始關鍵字序列T=32, 13, 27, 32*, 19，33，請分別用MSD和LSD進展排序，并討論其優(yōu)缺陷。由于有分組，故此算法需遞歸實現(xiàn)。法1MSD：原始序列：32, 13, 27, 32*, 19， 33 先按高位Ki1 排序：13, 19, 27, 32, 32*，33 再按低位Ki2 排序 ： 13, 19 ， 27, 32, 32*, 33法2LSD： 原始序列

30、： 32, 13, 27, 32*, 19 ，33 先按低位Ki2排序： 32, 32*, 13, 33, 27, 19 再按高位Ki1排序： 13, 19 , 27, 32, 32*, 33無需分組，易編程實現(xiàn)！:例：T=02，77，70，54，64，21，55，11，用LSD排序。分析：各關鍵字可視為2元組；每位的取值范圍是：0-9；即基數(shù)radix 10 。因此，特設置10個隊列，并編號為0-9。1155216454707702原始序列12345678先對低位掃描出隊012345678910個隊列計算機怎樣實現(xiàn)LSD算法？分配過程搜集過程下一步7755645402112170123456

31、78出隊后序列775554，6421，117002又稱散列過程！:0123456789再次入隊再次出隊再對高位掃描小結：排序時經(jīng)過了反復的“分配和“搜集過程。當對關鍵字一切的位進展掃描排序后，整個序列便從無序變?yōu)橛行蛄恕?75564540211217012345678出隊后序列70，776454，55211102再次分配再次搜集7770645554211102再次出隊后序列這種LSD排序方法稱為： 基數(shù)排序:v基數(shù)排序基數(shù)排序 10.6 基數(shù)排序基數(shù)排序 討論：所用隊列是順序構造，浪費空間，能否改用鏈式構造？用鏈隊列來實現(xiàn)基數(shù)排序鏈式基數(shù)排序: 針對針對 d 元組中的每一位分量，把原始鏈表中元

32、組中的每一位分量，把原始鏈表中的一切記錄的一切記錄, 按按Kij的取值，讓的取值，讓 j = d, d-1, , 1， 先先“分配分配到到radix個鏈隊列中去；個鏈隊列中去； 然后再按各鏈隊列的順序，依次把記錄從鏈隊列中然后再按各鏈隊列的順序，依次把記錄從鏈隊列中“搜集搜集起來；起來； 分別用這種分別用這種“分配分配、“搜集搜集的運算逐趟進展排序；的運算逐趟進展排序； 在最后一趟在最后一趟“分配分配、“搜集搜集 完成后，一切記錄就按完成后，一切記錄就按其關鍵碼的值從小到大排好序了。其關鍵碼的值從小到大排好序了。v鏈式基數(shù)排序鏈式基數(shù)排序10.6 基數(shù)排序基數(shù)排序 實現(xiàn)思緒：: 請實現(xiàn)以下關鍵

33、字序列的鏈式基數(shù)排序：T=614，738，921，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原始序列鏈表：r0從最低位 i = 3開場排序，f 是隊首指針，e 為隊尾指針第一趟搜集讓隊尾指針ei 鏈接到下一非空隊首指針fi+1 即可530790921101614485215306637738r0:第一趟搜集的結果：e0 e1 e2 e

34、3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9第二趟分配按次低位 i = 2 530790921101614485215306637738第二趟搜集讓隊尾指針ei 鏈接到下一非空隊首指針fi+1 530790921101614485215306637738r0r0:第二趟搜集的結果：530790921101614485215306637738e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4

35、 f5 f6 f7 f8 f9第三趟分配按最高位 i = 1 第三趟搜集讓隊尾指針ei 鏈接到下一非空隊首指針fi+1 530790921101614485215306637738r0r0排序終了！:v基數(shù)排序算法分析基數(shù)排序算法分析10.6 基數(shù)排序基數(shù)排序 假設有n 個記錄, 每個記錄的關鍵字有d 位，每個關鍵字的取值有radix個, 那么需求radix個隊列, 進展d趟“分配與“搜集。因此時間復雜度：O( d ( n+radix ) )。基數(shù)排序需求添加n+2radix個附加鏈接指針，空間效率低 空間復雜度：O(radix).穩(wěn)定性：穩(wěn)定。(不斷前后有序)。用途：假設基數(shù)radix一樣，對于記錄個數(shù)較多而關鍵碼位數(shù)較少的情況，運用鏈式基數(shù)排序較好。特點：不用比較和挪動，改用分配和搜集，時間效率高！:v各種內部排序方法的比較各種內部排序方法的比較10.7 內部排序方法的比較內部排序方法的比較排序方法最好時間平均時間最壞時間輔助空間穩(wěn)定性直接插入排序O(n)O(n2)O(n2)O(1)穩(wěn)定希爾排序 O(n1.3) O(1)不穩(wěn)定直接選擇排序O(n2)O(n2)O(n2)O(1)不穩(wěn)定堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不穩(wěn)定冒泡排序O(n)O(n2)O(n2)O(1)穩(wěn)定快速排序O(nlog2n