數(shù)據(jù)結(jié)構(gòu)概論第9章排序

1、數(shù)據(jù)結(jié)構(gòu)概論數(shù)據(jù)結(jié)構(gòu)概論第9章 排序董黎剛浙江工商大學(xué)信電學(xué)院1. 排序的基本概念9.1 排序的基本概念9.1.1 背景 查找要取得好的效果，做一些預(yù)處理很重要，比如排序。 哪些查找要排序？ 折半查找 分塊查找要求部分有序 二叉排序樹 平衡二叉樹9.1 排序的基本概念9.1.2 排序的概念 排序：有n個(gè)記錄的序列R1，R2，Rn，其相應(yīng)關(guān)鍵字的序列是K1，K2，Kn 。通過排序，要求找出當(dāng)前下標(biāo)序列1，2，n的一種排列p1，p2，pn，使得相應(yīng)關(guān)鍵字滿足如下的非遞減（或非遞增）關(guān)系，即：Kp1 Kp2 Kpn ，這樣就得到一個(gè)按關(guān)鍵字有序的記錄序列：Rp1，Rp2，Rpn。評(píng)價(jià)：排序的含義很簡(jiǎn)

2、單，但是描述不簡(jiǎn)單9.1 排序的基本概念9.1.2 排序的概念 整個(gè)排序過程完全在內(nèi)存中進(jìn)行，稱為內(nèi)部排序。 由于待排序記錄數(shù)量太大，內(nèi)存無(wú)法容納全部記錄，排序過程中需要借助外部存儲(chǔ)設(shè)備（簡(jiǎn)稱外存，比如硬盤）才能完成，稱為外部排序。 內(nèi)存的存儲(chǔ)容量小，但存取速度高；外存的存儲(chǔ)容量大，但速度較低。 外存包括順序存取設(shè)備（比如，磁帶）和直接存取設(shè)備（比如，磁盤）兩類。9.1 排序的基本概念9.1.2 排序的概念 問題：內(nèi)部排序和外部排序是指排序方法還是某個(gè)具體的排序。 回答：一般來(lái)說(shuō)，內(nèi)部排序和外部排序是指某個(gè)具體的排序。而外部排序方法是指空間復(fù)雜度相對(duì)較大（比如O(n)）的排序算法。 問題：外部

3、排序是因?yàn)閿?shù)據(jù)量大還是空間復(fù)雜度大？ 回答：外部排序算法的空間復(fù)雜度比較大，因此在數(shù)據(jù)量非常大的時(shí)候，內(nèi)存可能不夠排序操作而需要外存空間。9.1 排序的基本概念9.1.2 排序的概念穩(wěn)定排序和不穩(wěn)定排序 比如： 1，2，8，2，9，排序后成為1，2，2，8，9，則該排序算法是不穩(wěn)定的。 假設(shè)Ki=Kj(1in，1jn，ij)，若在排序前的序列中Ri領(lǐng)先于Rj(即ij)，經(jīng)過排序后得到的序列中Ri仍領(lǐng)先于Rj，則稱所用的排序方法是穩(wěn)定的； 反之，當(dāng)相同關(guān)鍵字的領(lǐng)先關(guān)系在排序過程中可能發(fā)生變化，則稱所用的排序方法是不穩(wěn)定的。9.1 排序的基本概念9.1.2 排序的概念 問題：穩(wěn)定排序的好處是什么？

4、 穩(wěn)定排序算法對(duì)多關(guān)鍵字排序有利。比如撲克牌既要排花色（次要順序），又要排數(shù)字（主要順序）。 先排花色，黑桃在紅心之前； 然后排數(shù)字，黑桃3和紅心3的數(shù)字一樣。穩(wěn)定算法還是會(huì)保留原來(lái)黑桃3在紅心3之前的先后關(guān)系。9.1 排序的基本概念9.1.2 排序的概念 問題：怎么證明算法是穩(wěn)定的或者不穩(wěn)定？ 證明穩(wěn)定很難，但是證明不穩(wěn)定只需要提供一個(gè)反例。9.1 排序的基本概念9.1.4 排序中需要的存儲(chǔ)結(jié)構(gòu)（1）以順序表作為存儲(chǔ)結(jié)構(gòu)排序過程：對(duì)記錄本身進(jìn)行物理重排（即通過關(guān)鍵字之間的比較判定，將記錄移到合適的位置）。移動(dòng)操作可能比較多。（2）以（動(dòng)態(tài)）鏈表作為存儲(chǔ)結(jié)構(gòu)排序過程：無(wú)須移動(dòng)記錄，僅需修改指針

5、。9.1 排序的基本概念9.1.4 排序中需要的存儲(chǔ)結(jié)構(gòu)（3）建立包括關(guān)鍵字和記錄位置下標(biāo)的索引表排序前Keyi8437ti1234Keyi3478ti3241排序后9.1 排序的基本概念9.1.4 排序中需要的存儲(chǔ)結(jié)構(gòu) 使用索引表的排序過程： 排序前令索引表包括keyi和ti=i(0in)。 若排序算法中要求交換記錄i和記錄j，則只需交換keyi和keyj ，ti和tj即可。排序過程中不移動(dòng)記錄本身。 等排序結(jié)束后，再按照表中所規(guī)定的次序調(diào)整各記錄。9.1 排序的基本概念9.1.4 排序中需要的存儲(chǔ)結(jié)構(gòu)（4）建立只包含記錄位置下標(biāo)的輔助表排序前ti1234ti3241排序后用Keyti方式獲

6、得關(guān)鍵字的值9.1 排序的基本概念9.1.4 排序中需要的存儲(chǔ)結(jié)構(gòu) 使用輔助表的排序過程： 排序前令輔助表ti=i(0in)。 若排序算法中要求交換記錄i和記錄j，則只需交換ti和tj即可。排序過程中不移動(dòng)記錄本身。 等排序結(jié)束后，再按照表中所規(guī)定的次序調(diào)整各記錄。 索引表或輔助表適合于難于在（動(dòng)態(tài)）鏈表上實(shí)現(xiàn)的排序方法。9.1 排序的基本概念9.1.5 排序算法的評(píng)價(jià) 時(shí)間復(fù)雜度 排序算法的時(shí)間開銷主要是關(guān)鍵字的比較和記錄的移動(dòng)。 執(zhí)行時(shí)間不僅依賴于問題的規(guī)模，還取決于輸入實(shí)例中數(shù)據(jù)的狀態(tài)，這時(shí)就有最好、最差或平均時(shí)間復(fù)雜度的區(qū)分。 空間復(fù)雜度 如空間復(fù)雜度是O(1)，則稱之為就地排序(In

7、-Place Sort)方法。 非就地排序方法一般要求的空間復(fù)雜度為O(n)。 穩(wěn)定性2. 插入類排序（1）9.2.1 背景 插入類排序基本思想：在一個(gè)已排好序的記錄子集的基礎(chǔ)上，每一步將下一個(gè)待排序的記錄有序插入到已排好序的記錄子集中，直到將所有待排記錄全部插入為止。 種類：直接插入、折半插入和希爾排序9.2 插入類排序直接插入和折半插入9.2 插入類排序直接插入和折半插入9.2.1 背景 插入排序與打撲克時(shí)整理手上的牌非常類似。摸來(lái)的第1張牌無(wú)須整理，此后每次從桌上的牌(無(wú)序區(qū))中摸1張并插入左手的牌(有序區(qū))中正確的位置上。 為了找到這個(gè)正確的位置，須自左向右(或自右向左)將摸來(lái)的牌與左

8、手中已有的牌逐一比較。9.2.2 直接插入排序 排序?qū)嵗撼跏紶顟B(tài) 4862 35 77 55 14 35 98 第1趟插入后 48 6235 77 55 14 35 98第2趟插入后 35 48 6277 55 14 35 98 第3趟插入后 35 48 62 7755 14 35 98 第4趟插入后 35 48 55 62 7714 35 98 第5趟插入后 14 35 48 55 62 7735 98 第6趟插入后 14 35 35 48 55 62 7798 第7趟插入后 14 35 35 48 55 62 77 98 9.2 插入類排序直接插入和折半插入大括號(hào)內(nèi)為有序區(qū)（當(dāng)前已排好序

9、的記錄子集合），大括號(hào)外是無(wú)序區(qū)。9.2.2 直接插入排序 第4趟插入的過程：開始狀態(tài) 35 48 62 7755 14 35 98 55 35 48 62 77 14 35 98 55 35 48 62 77 14 35 98 55 35 48 62 77 14 35 98 35 48 55 62 77 14 35 98 9.2 插入類排序直接插入和折半插入大括號(hào)內(nèi)為有序區(qū)（當(dāng)前已排好序的記錄子集合），大括號(hào)外是無(wú)序區(qū)。9.2.2 直接插入排序 直接插入排序的動(dòng)畫9.2 插入類排序直接插入和折半插入9.2.2 直接插入排序 算法過程：將第i個(gè)記錄的關(guān)鍵字Ki從后往前順次與其前面記錄的關(guān)鍵字K

10、i-1，Ki-2，K1進(jìn)行比較，將所有關(guān)鍵字大于Ki的記錄依次向后移動(dòng)一個(gè)位置，直到遇見一個(gè)關(guān)鍵字小于或者等于Ki的記錄Kj，此時(shí)Kj后面必為空位置，將第i個(gè)記錄插入空位置即可。 算法要點(diǎn)： 使用監(jiān)視哨r0臨時(shí)保存待插入的記錄； 從后往前查找應(yīng)插入的位置； 查找與移動(dòng)用同一循環(huán)完成。9.2 插入類排序直接插入和折半插入9.2.2 直接插入排序算法分析 它只需要一個(gè)輔助空間r0?？臻g復(fù)雜度是O(1)。 從時(shí)間耗費(fèi)角度來(lái)看，主要時(shí)間耗費(fèi)在關(guān)鍵字比較和移動(dòng)元素上。 最好情況（只需要跟已排好序的最末尾記錄比較）：總的比較次數(shù)為：n-1，有監(jiān)視哨情況下，總的移動(dòng)次數(shù)為2（n-1）。9.2 插入類排序直接

11、插入和折半插入9.2.2 直接插入排序算法分析 最壞情況（需要跟已排好序的記錄全部進(jìn)行比較）：總的比較次數(shù)為： 。總的移動(dòng)次數(shù)是 ，因此，時(shí)間復(fù)雜度為O(n2)。 當(dāng)n值較小時(shí)，n和n2的差別也較小，即直接插入排序的最好時(shí)間復(fù)雜度O(n)和最壞時(shí)間復(fù)雜度0(n2)差別不大。 直接插入排序是穩(wěn)定的排序方法。9.2 插入類排序直接插入和折半插入2(2)(1)2ninni2(4)(1)(1)2ninni9.2.3 折半插入排序 算法思路：查找插入位置可以用“折半查找”實(shí)現(xiàn)，則直接插入排序就變成為折半插入排序。 以上例中插入98為例，采用折半插入排序?qū)ふ也迦胛恢茫?.2 插入類排序直接插入和折半插入9

12、.2.3 折半插入排序 以上例中第6趟插入98為例，采用折半插入排序?qū)ふ也迦胛恢玫倪^程如圖所示（low所指的是插入位置）：9.2 插入類排序直接插入和折半插入9.2.3 折半插入排序 如果插入77，采用折半插入排序?qū)ふ业牟迦胛恢脩?yīng)該是low所指位置的下一個(gè)：9.2 插入類排序直接插入和折半插入9.2.3 折半插入排序算法分析 采用折半插入，可減少關(guān)鍵字的比較次數(shù)。每插入一個(gè)元素，需要比較的次數(shù)最大為折半判定樹的深度，如插入第i個(gè)元素時(shí),則需進(jìn)行l(wèi)og2i次比較，因此插入n-1個(gè)元素的關(guān)鍵字的平均比較次數(shù)為O(nlog2n)。 折半插入與直接插入相比較，改善了算法中比較次數(shù)的數(shù)量級(jí)，但其并未改變

13、移動(dòng)次數(shù)，所以折半插入排序的總的時(shí)間復(fù)雜度仍然是O(n2)。9.2 插入類排序直接插入和折半插入3. 插入類排序（2）9.3 插入類排序希爾排序9.3.1 背景 折半插入對(duì)直接插入的改進(jìn)是減少比較次數(shù)。那么移動(dòng)次數(shù)能否減少？ 直接插入和折半插入的移動(dòng)基本上是相鄰位置移動(dòng)，如果能夠?qū)崿F(xiàn)位置的遠(yuǎn)程移動(dòng)，可減少移動(dòng)次數(shù)。希爾排序采用分組插入排序的方法實(shí)現(xiàn)了這一點(diǎn)。9.3 插入類排序希爾排序9.3.2 希爾排序 希爾排序的動(dòng)畫9.3 插入類排序希爾排序9.3.2 希爾排序 希爾排序（Shell Sort）又稱縮小增量（間隔）法 希爾排序?qū)嵗僭O(shè)，增量序列的取值依次為：5，3，1初始狀態(tài)： 49，38，

14、65，97，76，13，27，49，55，04增量為5的排序后：9.3 插入類排序希爾排序9.3.2 希爾排序 希爾排序?qū)嵗隽繛?的排序后：增量為1的排序后： 04，13，38，27，49，49，55，65，76，97 注意：上例中兩個(gè)49的位置發(fā)生了改變，顯然，希爾排序是不穩(wěn)定排序。13，04，49，38，27，49，55，65，97，769.3 插入類排序希爾排序9.3.2 希爾排序 好的增量序列的共同特征： 最后一個(gè)增量必須為1。 應(yīng)該盡量避免序列中的值(尤其是相鄰的值)互為倍數(shù)的情況。9.3 插入類排序希爾排序9.3.3 希爾排序性能分析 希爾排序的時(shí)間性能優(yōu)于直接插入排序的原因：

15、當(dāng)列表初態(tài)基本有序或n值較小時(shí)，直接插入排序的性能還不錯(cuò)。 在希爾排序能實(shí)現(xiàn)遠(yuǎn)距離的記錄間比較和交換，而直接插入排序中只能相鄰記錄間交換。 Sedgewick等人提出了最差時(shí)間復(fù)雜度是O(n4/3)的增量序列，比如1, 5, 19, 41, 109, . . . 。 希爾排序是不穩(wěn)定的。4. 交換類排序9.4 交換類排序9.4.1 背景 交換類排序基本思想：兩兩比較待排序記錄的關(guān)鍵字，發(fā)現(xiàn)兩個(gè)記錄的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的記錄為止。 種類：冒泡排序和快速排序9.4 交換類排序9.4.1 背景 冒泡排序可能是同學(xué)們最早聽說(shuō)、最不容易被忘記的排序算法，但是它是最差的排序算法之一。 快速

16、排序則是性能最好的排序算法之一?？焖倥判蚴怯?guó)計(jì)算機(jī)科學(xué)家C.A.R.Hoare（1934-）于1962年提出的一種劃分交換排序。它采用了一種分治的策略。9.4 交換類排序9.4.2 冒泡排序 冒泡排序（Bubble Sort）又稱為氣泡排序，相鄰比序法 算法思想：將被排序的記錄Ri看作是重量為Ri.key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡，就使其向上飄浮。如此反復(fù)進(jìn)行，直到最后任何兩個(gè)氣泡都是輕者在上，重者在下為止。9.4 交換類排序9.4.3 冒泡排序?qū)嵗?冒泡排序的動(dòng)畫9.4 交換類排序9.4.3 冒泡排序?qū)嵗?9 13 13 13

17、13 1338 49 27 27 27 2765 38 49 38 38 3897 65 38 49 49 4976 97 65 49 49 4913 76 97 65 65 6527 27 76 97 76 7649 49 49 76 97 97初始 第一趟結(jié)果 第二趟結(jié)果 第三趟結(jié)果 第四趟結(jié)果 第五趟結(jié)果9.4 交換類排序9.4.4 冒泡排序注意點(diǎn) 若在某一趟排序中未發(fā)現(xiàn)氣泡位置的交換，則說(shuō)明待排序的無(wú)序區(qū)中所有氣泡均滿足輕者在上，重者在下的原則，因此，冒泡排序過程可在此趟排序后終止。 實(shí)際使用中，既可以從左到右（或從下到上）冒泡，也可以從右到左（或從上到下）冒泡；既可以冒大數(shù)，也可以冒

18、小數(shù)。9.4 交換類排序9.4.5 冒泡排序算法分析 算法的最好時(shí)間復(fù)雜度。若列表的初始狀態(tài)是正序的，一趟掃描即可完成排序。所需的關(guān)鍵字比較次數(shù)C和記錄移動(dòng)次數(shù)M均達(dá)到最小值：Cmin=n-1，Mmin=0。因此，最好的時(shí)間復(fù)雜度為O(n)。9.4 交換類排序9.4.5 冒泡排序算法分析 算法的最壞時(shí)間復(fù)雜度。若列表的初始狀態(tài)是反序的，需要進(jìn)行n-1趟排序。每趟排序要進(jìn)行n-i次關(guān)鍵字的比較(1in-1)，且每次比較都必須移動(dòng)記錄3次來(lái)達(dá)到交換記錄位置。在這種情況下，比較和移動(dòng)次數(shù)均達(dá)到最大值：Cmax=n(n-1)/2，Mmax=3n(n-1)/2。因此，最壞時(shí)間復(fù)雜度為O(n2)。9.4

19、交換類排序9.4.5 冒泡排序算法分析 算法的平均時(shí)間復(fù)雜度為O(n2)。雖然冒泡排序不一定要進(jìn)行n-1趟，但由于它的記錄移動(dòng)次數(shù)較多，故平均時(shí)間性能比直接插入排序要差得多。 算法空間復(fù)雜度是O(1)，即冒泡排序是就地排序。 冒泡排序是穩(wěn)定的。9.4 交換類排序9.4.6 快速排序 快速排序（Quick Sort）算法思想：設(shè)當(dāng)前待排序的無(wú)序區(qū)為Rlow.high，在Rlow.high中任選一個(gè)記錄（一般選第一個(gè)記錄）作為樞軸(Pivot)，以此樞軸將當(dāng)前無(wú)序區(qū)劃分為左、右兩個(gè)較小的子區(qū)間，并使左邊子區(qū)間中所有記錄均小于等于樞軸記錄，右邊的子區(qū)間中所有記錄均大于等于樞軸記錄。這稱為第一次劃分。

20、接下來(lái)通過劃分算法對(duì)左、右子區(qū)間進(jìn)行第二次、第三次劃分。9.4 交換類排序9.4.6 快速排序 快速排序的動(dòng)畫9.4 交換類排序9.4.7 快速排序?qū)嵗?快速排序的第一趟劃分劃分的目的是以第一個(gè)記錄（即49）為樞軸，把所有記錄分成兩部分。初始4938659776132749lowhigh初始4938659776132749lowhigh1次交 2738659776134949換之后 low high 2738659776134949 low high 2738659776134949 low high2次交2738499776136549換之后low high設(shè)置low和high分別指向第一個(gè)

21、和最后一個(gè)記錄如果low比high指向的關(guān)鍵字值大，就交換9.4 交換類排序9.4.7 快速排序?qū)嵗?次交2738499776136549換之后low high2738499776136549 low high3次交2738139776496549換之后low high2738139776496549 low high4次交2738134976976549換之后low high2738134976976549low high完成(273813)49(76976549) low/high9.4 交換類排序9.4.8 比較快速排序和希爾排序 在交換角度上，快速排序與希爾排序比較相似，把相鄰位置的移

22、動(dòng)/交換改成不相鄰位置的移動(dòng)/交換。 在處理的“問題規(guī)?！苯嵌壬?，快速排序與希爾排序有點(diǎn)相反，它先處理一個(gè)較大規(guī)模，然后逐漸把處理的規(guī)模降低，最終達(dá)到排序的目的。9.4 交換類排序9.4.9 快速排序算法分析 快速排序的時(shí)間主要耗費(fèi)在劃分操作上，對(duì)長(zhǎng)度為k的區(qū)間進(jìn)行劃分，共需k-1次關(guān)鍵字的比較。 好的劃分是左右區(qū)間中的記錄數(shù)大致相同，壞的劃分是1個(gè)區(qū)間為空，另一個(gè)區(qū)間比劃分前的無(wú)序區(qū)中記錄數(shù)少1。前者導(dǎo)致最好時(shí)間復(fù)雜度，后者導(dǎo)致最壞時(shí)間復(fù)雜度。 最好時(shí)間復(fù)雜度情況下，劃分的次數(shù)為O(log2n)，而每次劃分比較次數(shù)不超過n，故整個(gè)排序過程所需要的關(guān)鍵字比較總次數(shù)O(nlog2n)。9.4 交

23、換類排序9.4.9 快速排序算法分析 最壞時(shí)間復(fù)雜度情況下，快速排序必須做n-1次劃分，第i次劃分開始時(shí)區(qū)間長(zhǎng)度為n-i+1，所需的比較次數(shù)為n-i(1in-1)，故總的比較次數(shù)達(dá)到最大值：Cmax = 因?yàn)榭焖倥判虻挠涗浺苿?dòng)次數(shù)不大于比較的次數(shù)，所以快速排序的最壞時(shí)間復(fù)雜度應(yīng)為0(n2)，最好時(shí)間復(fù)雜度為O(nlog2n)。就平均性能而言，它是基于關(guān)鍵字比較的內(nèi)部排序算法中速度最快者，平均時(shí)間復(fù)雜度為O(nlog2n)。1111(1)2nniin nnii 9.4 交換類排序9.4.9 快速排序算法分析 空間復(fù)雜度?？焖倥判蛩惴ㄔ谶f歸時(shí)需要一個(gè)棧保存樞軸位置。若每次劃分較為均勻，則其遞歸樹的

24、高度為O(log2n)，故遞歸后需?？臻g為O(log2n)。最壞情況下，遞歸樹的高度為O(n)，所需的?？臻g為O(n)。 快速排序是非穩(wěn)定的，例如列表2，2，1經(jīng)過快速排序后會(huì)變成1，2，2。5. 選擇類排序（1）9.5 選擇類排序簡(jiǎn)單選擇和樹形選擇9.5.1 背景 交換類排序中，交換操作比較多；而選擇類排序中，比較操作較多，交換操作較少：通過多次比較找到記錄的最后位置后，再一次性交換到位。 選擇類排序基本思想：每一趟從待排序的記錄中選出關(guān)鍵字最?。ɑ蜃畲螅┑挠涗?，順序放在已排好序的記錄的最后，直到全部記錄排序完畢。 選擇類排序種類：簡(jiǎn)單選擇排序、樹形選擇排序和堆排序9.5 選擇類排序簡(jiǎn)單選擇

25、和樹形選擇9.5.2 簡(jiǎn)單選擇排序 簡(jiǎn)單選擇排序又稱為直接選擇排序（Straight Selection Sort） 算法思想：第i趟簡(jiǎn)單選擇排序是指通過n-i次關(guān)鍵字的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i個(gè)記錄進(jìn)行交換。共需進(jìn)行i-1趟比較，直到所有記錄排序完成為止。9.5 選擇類排序簡(jiǎn)單選擇和樹形選擇9.5.3 簡(jiǎn)單選擇排序?qū)嵗跏缄P(guān)鍵字 49 38 65 97 76 13 27 49第一趟排序后 13 38 65 97 76 49 27 49第二趟排序后 13 27 65 97 76 49 38 49第三趟排序后 13 27 38 97 76 49 65 49第四趟排

26、序后 13 27 38 49 76 97 65 49 第五趟排序后 13 27 38 49 49 97 65 76第六趟排序后 13 27 38 49 49 65 97 76第七趟排序后 13 27 38 49 49 65 76 97最后排序結(jié)果 13 27 38 49 49 65 76 979.5 選擇類排序簡(jiǎn)單選擇和樹形選擇9.5.3 簡(jiǎn)單選擇排序?qū)嵗?簡(jiǎn)單選擇排序的動(dòng)畫9.5 選擇類排序簡(jiǎn)單選擇和樹形選擇9.5.4 簡(jiǎn)單選擇排序算法分析 最好情況下，即待排序記錄就已經(jīng)是正序排列，則不需要移動(dòng)記錄。最壞情況下，即待排序記錄按逆序排列，則需要移動(dòng)記錄的次數(shù)最多為3（n-1）。 無(wú)論記錄初始狀

27、態(tài)如何，在第i趟排序中選出最小關(guān)鍵字的記錄，需做n-i次比較，因此，總的比較次數(shù)為：n(n-1)/2。因此，平均時(shí)間復(fù)雜度為O(n2)。 簡(jiǎn)單選擇排序是一個(gè)就地排序。 簡(jiǎn)單選擇排序是不穩(wěn)定的，比如2，2，1，第一趟排序后為1，2，2。9.5 選擇類排序簡(jiǎn)單選擇和樹形選擇9.5.5 樹形選擇排序 樹形選擇排序（Tree Selection Sort）（又稱錦標(biāo)賽排序，Tournament Sort） 算法思想：先把待排序的n個(gè)記錄的關(guān)鍵字兩兩進(jìn)行比較，取出較小者。然后再在 n/2 個(gè)較小者中，采用同樣的方法進(jìn)行比較選出每?jī)蓚€(gè)中的較小者，如此反復(fù)，直至選出最小關(guān)鍵字記錄為止。9.5 選擇類排序簡(jiǎn)單

28、選擇和樹形選擇9.5.6 樹形選擇排序?qū)嵗?初始狀態(tài) 49 38 65 97 76 13 27 49 下面求最小關(guān)鍵字 從而得到最小關(guān)鍵字139.5 選擇類排序簡(jiǎn)單選擇和樹形選擇9.5.6 樹形選擇排序?qū)嵗?下面求次小關(guān)鍵字，把13改成 從而得到最小關(guān)鍵字27。按照這樣的方式可以排出其他關(guān)鍵字9.5 選擇類排序簡(jiǎn)單選擇和樹形選擇9.5.7 樹形選擇排序算法分析 由于含有n個(gè)葉子結(jié)點(diǎn)的完全二叉數(shù)的深度為 log2n +1（根據(jù)二叉樹性質(zhì)4），則在樹型選擇排序中，每選擇一個(gè)小關(guān)鍵字需要進(jìn)行 log2n 次比較( 除第一次選擇最小關(guān)鍵字需要n-1次比較)，因此其時(shí)間復(fù)雜度為O(nlog2n)。 移動(dòng)

29、記錄次數(shù)不超過比較次數(shù)。 故總的算法時(shí)間復(fù)雜度為O(nlog2n)。6. 選擇類排序（2）9.6 選擇類排序堆排序9.6.1 背景 樹形選擇排序比簡(jiǎn)單選擇排序好的地方是把關(guān)鍵字之間的大小關(guān)系保存下來(lái)以便后面再次利用，減少了比較次數(shù)。 堆排序有進(jìn)一步改善：保存大小關(guān)系不再需要額外空間，從而降低了空間復(fù)雜度。9.6 選擇類排序堆排序9.6.2 堆排序的相關(guān)概念 堆是一種特殊的樹形結(jié)構(gòu)（而且是完全二叉樹），每個(gè)結(jié)點(diǎn)都有一個(gè)值（即每個(gè)記錄的關(guān)鍵字值）。 堆的特點(diǎn)是根結(jié)點(diǎn)的值最小或最大（兩者分別稱為小根堆和大根堆），且堆中任一子樹也是堆。我們這里用的堆實(shí)際上是二叉堆(Binary Heap)，類似地可定

30、義k叉堆。9.6 選擇類排序堆排序9.6.2 堆排序的相關(guān)概念 通常采用順序結(jié)構(gòu)存儲(chǔ)堆。記錄存放在數(shù)組r1.n之中，各記錄按照樹的層次遍歷順序?qū)?yīng)各結(jié)點(diǎn)。9.6 選擇類排序堆排序9.6.3 堆排序中的操作 基本操作篩選 當(dāng)堆頂元素改變時(shí)，對(duì)堆進(jìn)行調(diào)整（即把待調(diào)整記錄逐步向下“篩”），使之恢復(fù)成為規(guī)范的堆。 構(gòu)建堆 一個(gè)任意序列可以建立一個(gè)對(duì)應(yīng)的完全二叉樹 反復(fù)利用“篩選”法，自底向上逐層把所有子樹調(diào)整為堆，直到將整個(gè)完全二叉樹調(diào)整為堆。9.6 選擇類排序堆排序9.6.3 堆排序中的操作 構(gòu)建堆的實(shí)例已知關(guān)鍵字序列：49，38，65，97，76，13，27，49，通過篩選算法建立小根堆。自第n/

31、2個(gè)記錄開始進(jìn)行篩選建堆 9.6 選擇類排序堆排序9.6.3 堆排序中的操作 構(gòu)建堆的實(shí)例建立小根堆。9.6 選擇類排序堆排序9.6.4 堆排序?qū)⒋判蛴涗洶凑斩训亩x建初堆，并輸出堆頂元素；把堆中的最后一個(gè)記錄放到堆頂，然后利用篩選法將剩下的元素重新篩選建成為一個(gè)新堆，再輸出堆頂元素；重復(fù)執(zhí)行步驟n-1次進(jìn)行篩選,而依次輸出的堆頂元素組成一個(gè)有序的序列。9.6 選擇類排序堆排序9.6.4 堆排序 堆排序?qū)嵗?9.6 選擇類排序堆排序9.6.4 堆排序 堆排序?qū)嵗?9.6 選擇類排序堆排序9.6.4 堆排序 堆排序?qū)嵗?9.6 選擇類排序堆排序9.6.4 堆排序 堆排序?qū)嵗?9.6 選擇類排序

32、堆排序9.6.4 堆排序 堆排序?qū)嵗?9.6 選擇類排序堆排序9.6.4 堆排序 堆排序?qū)嵗?9.6 選擇類排序堆排序9.6.4 堆排序 堆排序?qū)嵗?9.6 選擇類排序堆排序9.6.4 堆排序 堆排序的動(dòng)畫 9.6 選擇類排序堆排序9.6.5 堆排序分析 堆排序的時(shí)間主要耗費(fèi)在建初始堆和調(diào)整建新堆時(shí)進(jìn)行的反復(fù)“篩選”上。 對(duì)深度為k的堆，篩選算法中進(jìn)行的關(guān)鍵字的比較次數(shù)至多為2（k-1）次。 n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為： log2n +1，則調(diào)整建新堆時(shí)調(diào)用篩選過程n-1次總共進(jìn)行的比較次數(shù)不超過：2（ log2(n-1) + log2(n-2) + log22 ） 2n log2n 9.6

33、 選擇類排序堆排序9.6.5 堆排序分析 因此，堆排序在最壞情況下，其時(shí)間復(fù)雜度也為O(nlog2n)，這是堆排序的最大優(yōu)點(diǎn)。 堆排序是一種不穩(wěn)定的排序方法 堆排序不適用于待排序記錄個(gè)數(shù)n較少的情況，但對(duì)于n較大時(shí)還是很有效的。7. 歸并排序9.7 歸并排序9.7.1 背景 與快速排序一樣，歸并排序也是采取分治法。 歸并排序與樹形選擇排序有相似性，要注意區(qū)別。 歸并排序(Merge Sort)基本思想：將兩個(gè)或兩個(gè)以上有序列表合并成一個(gè)新的有序列表。 在歸并排序中，關(guān)注最多的就是2路歸并。9.7 歸并排序9.7.2 兩路歸并排序算法思想：假設(shè)初始序列含有n個(gè)記錄， 首先將這n個(gè)記錄看成n個(gè)有序

34、的子序列，每個(gè)子序列的長(zhǎng)度為1，然后兩兩歸并，得到 n/2 個(gè)長(zhǎng)度為2（n為奇數(shù)時(shí)，最后一個(gè)序列的長(zhǎng)度為1）的有序子序列； 在此基礎(chǔ)上，再進(jìn)行兩兩歸并，如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序序列為止。9.7 歸并排序9.7.2 兩路歸并排序 算法實(shí)例9.7 歸并排序9.7.2 兩路歸并排序 歸并算法的動(dòng)畫9.7 歸并排序9.7.3 歸并排序算法分析 歸并排序中一趟歸并中要多次用到2路歸并算法，一趟歸并排序的操作是調(diào)用 n/(2h) 次合并算法將r11n中前后相鄰且長(zhǎng)度為h的有序段進(jìn)行兩兩歸并，得到長(zhǎng)度為2h的有序段，并存放在r1n中，其時(shí)間復(fù)雜度為O(n)。 整個(gè)歸并排序需進(jìn)行m（m=log2n

35、）趟2路歸并，所以無(wú)論是在最好情況下還是在最壞情況下，歸并排序的時(shí)間復(fù)雜度都為O（nlog2n）。9.7 歸并排序9.7.3 歸并排序算法分析 算法采用了順序表，在實(shí)現(xiàn)歸并排序時(shí)，需要和待排記錄等數(shù)量的輔助空間，空間復(fù)雜度為O(n)。但是，如果采用鏈表，其實(shí)可以實(shí)現(xiàn)空間復(fù)雜度為O(1)。 是一種穩(wěn)定的排序方法9.7 歸并排序9.7.4 歸并排序用于外部排序 歸并排序較多用于外部排序。外部排序可分兩步，待排序文件中的記錄分批讀入內(nèi)存，用某種內(nèi)部排序方法在內(nèi)存排序，組成有序的子文件，再存入外存。用某種歸并方法（如2路歸并法）對(duì)子文件進(jìn)行多路歸并，成為較長(zhǎng)有序子文件，再記入外存，如此反復(fù)，直到整個(gè)待

36、排序文件有序。 最初形成有序子文件長(zhǎng)取決于內(nèi)存所能提供排序區(qū)大小和最初排序策略，歸并路數(shù)取決于所能提供排序的外部設(shè)備數(shù)。9.7 歸并排序9.7.4 歸并排序用于外部排序 外部排序?qū)嵗杭僭O(shè)磁盤上存有一文件，共有3600個(gè)記錄（A1,A2,A3600），頁(yè)塊長(zhǎng)為200個(gè)記錄，供排序使用的緩沖區(qū)可提供容納600個(gè)記錄的空間，現(xiàn)要對(duì)該文件進(jìn)行排序，排序過程可按如下步驟進(jìn)行：9.7 歸并排序9.7.4 歸并排序用于外部排序 第一步：每次將三個(gè)頁(yè)塊（600個(gè)記錄）由外存讀到內(nèi)存，進(jìn)行內(nèi)排序，整個(gè)文件共得到6個(gè)初始順串R1-R6 （每一個(gè)順串占三個(gè)頁(yè)塊），然后把它們寫回到磁盤上去。 第二步：將供內(nèi)排序使用

37、的內(nèi)存緩沖區(qū)分為三塊相等的部分（即每塊可容納200個(gè)記錄），其中兩塊作為輸入緩沖區(qū)，一塊作為輸出緩沖區(qū)，然后對(duì)各順串進(jìn)行兩路歸并。8. 分配類排序桶排序9.8 分配類排序桶排序9.8.1 背景 之前的排序算法都包括了關(guān)鍵字的兩兩比較，但是也有不需要比較關(guān)鍵字的排序算法。 分配排序的基本思想：通過“分配”和“收集”過程來(lái)實(shí)現(xiàn)排序。它們的時(shí)間復(fù)雜度可達(dá)到線性階：O(n)。 分配類排序種類：桶排序（ Bucket Sort， 或稱箱排序，Bin Sort ）和基數(shù)排序。9.8 分配類排序桶排序 基本思想：設(shè)置若干個(gè)桶，依次掃描待排序的記錄R0，R1，Rn-1，把關(guān)鍵字等于k的記錄全都裝入到第k個(gè)桶里

38、(分配)，然后按序號(hào)依次將各非空的桶首尾連接起來(lái)(收集)。 實(shí)例：對(duì)撲克牌按照數(shù)字排序9.8.2 基本的桶排序9.8 分配類排序桶排序 一般情況下每個(gè)桶中存放多少個(gè)關(guān)鍵字相同的記錄是無(wú)法預(yù)料的，故桶的類型應(yīng)設(shè)計(jì)成鏈表為宜。 為保證排序是穩(wěn)定的，分配過程中裝箱及收集過程中的連接必須按先進(jìn)先出原則進(jìn)行。比如，人隊(duì)操作將其插入該桶尾部，而出隊(duì)時(shí)從桶頂部開始取。 分配過程的時(shí)間是O(n)；收集過程的時(shí)間為O(m) （采用鏈表來(lái)存儲(chǔ)輸入的待排序記錄）。因此，桶排序的時(shí)間為O(m+n)。若箱子個(gè)數(shù)m的數(shù)量級(jí)為O(n)，則桶排序的時(shí)間是線性的，即O(n)。9.8.2 基本的桶排序9.8 分配類排序桶排序 假

39、如關(guān)鍵字值不是離散的，而是連續(xù)的，這就意味著有無(wú)數(shù)個(gè)關(guān)鍵字取值，為此，需要一個(gè)桶中的記錄有不同的關(guān)鍵字值。這就產(chǎn)生了擴(kuò)展的桶排序。9.8.2 基本的桶排序9.8 分配類排序桶排序基本思想： 把0，1)劃分為n個(gè)大小相同的子區(qū)間，每一子區(qū)間是一個(gè)桶。然后將n個(gè)記錄分配到各個(gè)桶中。 由于同一桶中的記錄其關(guān)鍵字不盡相同，所以必須采用關(guān)鍵字比較的排序方法(通常用插入排序)對(duì)各個(gè)桶進(jìn)行排序，然后依次將各非空桶中的記錄連接(收集)起來(lái)即可。 如果關(guān)鍵字的取值不是在0,1),那么可以先進(jìn)行歸一化處理映射到0,1)，然后再進(jìn)行上述步驟。9.8.3 擴(kuò)展的桶排序9.8 分配類排序桶排序算法實(shí)例： 對(duì)R0.9中的

40、關(guān)鍵字為(0.78，0.17，0.39，0.26，0.72，0.94，0.21， 0.12，0.23，0.68)進(jìn)行桶排序。 設(shè)立10個(gè)桶，分別是0,0.1),0.1,0.2),0.9,1) 分配關(guān)鍵字。如果所在桶已經(jīng)有關(guān)鍵字，要進(jìn)行插入排序。9.8.3 擴(kuò)展的桶排序9.8 分配類排序桶排序 收集各個(gè)桶中的鏈表，進(jìn)行首尾相連9.8.3 擴(kuò)展的桶排序9.8 分配類排序桶排序9.8.3 擴(kuò)展的桶排序桶排序算法的動(dòng)畫9.8 分配類排序桶排序 分配過程的平均時(shí)間復(fù)雜度是O(n)，但是最壞情況下所有關(guān)鍵字都進(jìn)入同一個(gè)桶，那么就產(chǎn)生了直接插入排序算法的復(fù)雜度，即O(n2)。9.8.3 擴(kuò)展的桶排序9. 分

41、配類排序基數(shù)排序9.9 分配類排序基數(shù)排序9.9.1 背景 基數(shù)排序是從多關(guān)鍵字排序解決方法中延伸而來(lái) 多關(guān)鍵字排序?qū)嵗簩⒁桓睋淇伺频呐判蜻^程看成由花色和點(diǎn)數(shù)兩個(gè)關(guān)鍵字進(jìn)行排序的問題。若規(guī)定花色和面值的順序如下（假設(shè)花色的優(yōu)先級(jí)高于點(diǎn)數(shù)）：花色：黑桃紅桃梅花方塊面值點(diǎn)數(shù)：A2310JQK因此，排序順序?yàn)椋?.9 分配類排序基數(shù)排序9.9.2 多關(guān)鍵字及排序 多關(guān)鍵字：列表中有d個(gè)獨(dú)立的關(guān)鍵字 。比如，撲克牌有兩個(gè)關(guān)鍵字：點(diǎn)數(shù)和花色。不妨假設(shè)花色的優(yōu)先級(jí)高于點(diǎn)數(shù)。 多關(guān)鍵字排序包括：“高位優(yōu)先”排序?？梢圆捎脭U(kuò)展的桶排序，只使用一次桶排序?！暗臀粌?yōu)先”排序。從低位開始多次采用桶排序。9.9 分配類排序基數(shù)排序如何對(duì)撲克牌排序? “高位優(yōu)先”排序法：先按花色分成有序的四類，在每一類中，按面值從小到大排序。 “低位優(yōu)先”排序法：有兩輪分配與收集。首先按面值從小到大把牌擺成13疊（每疊4張牌），然后將每疊牌按面值的次序收集到一起，再對(duì)這些牌按花色擺成4疊，每疊有13張牌，最后把這4疊牌按花色的次序收集到一起。9.9.2 多關(guān)鍵字及排序9.9 分配類排序基數(shù)排序9.9.3