數(shù)據(jù)結(jié)構(gòu)課件：第7章 排序

1、第七章 排 序第七章 排序7.1 基本概念7.2 插入排序7.3 交換排序7.4 選擇排序7.5 合并排序7.6 基于關(guān)鍵詞比較的排序算法分析7.7 分布排序從數(shù)學(xué)和計(jì)算機(jī)角度而言，簡(jiǎn)單地說(shuō)排序算法就是把元素按照一定的序關(guān)系列表，最常見(jiàn)的序關(guān)系是數(shù)字序和字典序。高效的排序算法有助于提高其他算法的效率，如查找算法。此外，在很多情況下，排序有助于規(guī)范化數(shù)據(jù)和便于人類閱讀、理解。盡管排序問(wèn)題本身相對(duì)于其他計(jì)算理論問(wèn)題而言并不復(fù)雜，但要設(shè)計(jì)高效的、有針對(duì)性的排序算法也并非易事，因此針對(duì)它的研究一直在持續(xù)開(kāi)展。排序，也叫分類，是將一組雜亂無(wú)章的數(shù)據(jù)按一定的規(guī)律排列起來(lái)的過(guò)程。 文件，是待排序數(shù)據(jù)對(duì)象的集

2、合；一個(gè)數(shù)據(jù)對(duì)象也叫作一個(gè)記錄，記為R1，R2，Rn關(guān)鍵詞域(key): 通常數(shù)據(jù)對(duì)象由多個(gè)屬性域(多個(gè)數(shù)據(jù)成員)組成，其中可將一個(gè)屬性域作為排序依據(jù)，該域即為關(guān)鍵詞域。關(guān)鍵詞記為：K1，K2，Kn；排序：將記錄按關(guān)鍵詞域遞增或遞減的順序排列7.1 基本概念每個(gè)文件用哪個(gè)屬性域作為關(guān)鍵詞，要視具體的應(yīng)用需要而定；即使是同一個(gè)文件表，在解決不同問(wèn)題的場(chǎng)合也可能取不同的關(guān)鍵詞域。主關(guān)鍵詞: 如果在數(shù)據(jù)表中各個(gè)對(duì)象的關(guān)鍵詞互不相同，這種關(guān)鍵詞即主關(guān)鍵詞。按照主關(guān)鍵詞排序，排序的結(jié)果是唯一的。次關(guān)鍵詞: 數(shù)據(jù)表中有些對(duì)象的關(guān)鍵詞可能相同，這種關(guān)鍵詞稱為次關(guān)鍵詞。按照次關(guān)鍵詞排序，排序的結(jié)果可能不唯一。

3、排序算法的度量指標(biāo):排序的時(shí)間開(kāi)銷(排序算法的時(shí)間復(fù)雜性):是衡量算法好壞的最重要標(biāo)志?？捎盟惴▓?zhí)行中關(guān)鍵詞的比較次數(shù)與數(shù)據(jù)的移動(dòng)次數(shù)來(lái)衡量。各算法的時(shí)間復(fù)雜性一般都按平均情況進(jìn)行估算。對(duì)那些受對(duì)象初始排列及對(duì)象個(gè)數(shù)影響較大的，需要按最好和最壞情況進(jìn)行估算。算法的空間復(fù)雜性:主要考察排序過(guò)程所需輔助存儲(chǔ)空間的大小。排序算法的穩(wěn)定性: 如果在對(duì)象序列中有兩個(gè)對(duì)象ri和rj，它們的關(guān)鍵詞ki=kj，且在排序之前對(duì)象ri排在rj前面，如果在排序之后，對(duì)象ri仍在對(duì)象rj的前面，則稱這個(gè)排序方法是穩(wěn)定的，否則稱這個(gè)排序方法是不穩(wěn)定的。排序算法有多種分類方法:從元素的存儲(chǔ)設(shè)備角度可分為內(nèi)排序（在內(nèi)存中進(jìn)

4、行）和外排序（在外存儲(chǔ)器上進(jìn)行）。按對(duì)關(guān)鍵詞的操作可分為基于關(guān)鍵詞比較的排序算法和分布排序算法。按時(shí)間代價(jià)分類：平方階排序算法，它們一般都比較簡(jiǎn)單，特點(diǎn)是容易實(shí)現(xiàn)，但時(shí)間復(fù)雜度相對(duì)較高，最壞情況下時(shí)間復(fù)雜度一般為O(n2)；線性對(duì)數(shù)階算法，以分治策略算法為主，最壞情況下時(shí)間復(fù)雜度一般為O(nlog(n). 第七章 排序7.1 基本概念7.2 插入排序 直接插入排序 希爾排序7.3 交換排序7.4 選擇排序7.5 合并排序7.6 基于關(guān)鍵詞比較的排序算法分析7.7 分布排序7.2 插入排序 例： 原有序表：(9 15 23 28 37) 20 找插入位置 : (9 15 23 28 37) 20

5、 新有序表: (9 15 20 23 28 37)插入排序思想 基于插入操作所完成的排序。 插入:將一個(gè)記錄插入到已排好序的有序表中，從而得到一個(gè)新的記錄數(shù)增一的有序表。7.2.1 直接插入排序算法1. 基本思想 待排序記錄 R1，R2， ，Rn1, Rn 第一步：R1 第二步：(R1 ), R2 第三步：(R1 , R2), R3 第 j 步：(R1，R2， ，Rj1), Rj 第 n 步: (R1，R2， ，Rn1), Rn例：j=59152823081 2 3 4 5 616162816231616一次插入過(guò)程1616原有序表中關(guān)鍵詞比Rj大的記錄數(shù)：dj比較次數(shù)：dj+1 移動(dòng)次數(shù)：

6、dj+2 2816232. 算法描述算法 InsertSort (R,n) FOR j2 TO n DO ( /每次將Rj插入到有序表R1，Rj1中 KKj. RRj. ij-1. WHILE (i0) AND (KiK) DO (Ri+1Ri. ii-1.) Ri+1R. ) 算法InsertSortA( R, s, e ) /引入虛擬記錄,Ks-1minKi| sie ISA1 逐一排序 FOR js+1 TO e DO ( ij-1KKj. RRj . WHILE KKi DO ( Ri+1Ri ii-1 ) Ri+1R ) ISA1 逐一排序 FOR js+1 TO e DO ( ij

7、-1KKj . RRj . WHILE KKi DO ( Ri+1Ri ii-l ) Ri+1R ) k1k2k3k4k0k587246j 24678872462 27 8464 7 82463 247 865 3. 算法分析 設(shè)dj是Rj左邊關(guān)鍵詞大于Kj的記錄個(gè)數(shù)，則算法InsertSortA中關(guān)鍵詞的比較次數(shù)為： 記錄的移動(dòng)次數(shù)為 最好情況下，排序前記錄已經(jīng)按關(guān)鍵詞從小到大有序排列，即dj=0。每趟只需與前面的有序部分的最后一個(gè)記錄的關(guān)鍵詞比較 1 次，記錄移動(dòng) 2 次，總的關(guān)鍵詞比較次數(shù)為 n-1，記錄移動(dòng)次數(shù)為 2(n-1)。最壞情況下：第i趟時(shí)，第i個(gè)記錄前面所有記錄的關(guān)鍵詞都比第

8、i個(gè)記錄的關(guān)鍵詞大，即dj=j-1 總的關(guān)鍵詞比較次數(shù)： 記錄移動(dòng)次數(shù)： 平均情況下，若待排序文件中記錄所有可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關(guān)鍵詞比較次數(shù)和記錄移動(dòng)次數(shù)分別為 因此，直接插入排序的時(shí)間復(fù)雜度為 O(n2)。平均情況下，考察分析 的期望值。對(duì)于序列K1，K2，Kn ，如果1ijn，且KiKj，則稱(Ki , Kj)為上述序列的一個(gè)反序?qū)?。?shí)際上， 正好是序列K1，K2，Kn的反序?qū)€(gè)數(shù)。 例 待排序記錄：8，7，2，4，6中反序?qū)Φ膫€(gè)數(shù) 是7個(gè)。則有,反序?qū)Φ钠骄鶄€(gè)數(shù) = 0+ (0+1)/2+ (0+1+2)/3+ (0123)/4(0

9、1234)/5 (012345)/6 (012n1)/n 01/22/2 3/24/25/2( n1)/2n(n1)/4即 的期望值為n(n1)/4 . 4.直接插入排序算法總結(jié)優(yōu)點(diǎn):是算法的執(zhí)行過(guò)程相當(dāng)清晰，并且書寫容易.缺點(diǎn):期望復(fù)雜性為O(n2) . 穩(wěn)定性：直接插入排序是穩(wěn)定的排序方法。最好情況是：當(dāng)被排序文件初態(tài)為正序時(shí)，算法的時(shí)間復(fù)雜度為O(n) . 輔助空間： O(1) 5. 直接插入排序算法是否可以進(jìn)一步改進(jìn)呢？直接插入排序算法中包含了一個(gè)查找過(guò)程，對(duì)前部已經(jīng)排序完的記錄執(zhí)行順序查找。這顯然是其效率低下的原因之一，是否可以通過(guò)改進(jìn)順序查找來(lái)提高排序效率呢? 通過(guò)將順序查找改為二

10、分查找，可以構(gòu)造二分插入排序算法。即在插入第j個(gè)元素時(shí)，不是像直接插入排序那樣順序?qū)ふ也迦氲奈恢?，而是采用?duì)半（或二分）的方法插入。如果文件（R1，R2，Rn）采用順序存儲(chǔ)，則對(duì)半插入排序算法可以減少關(guān)鍵詞的比較次數(shù)，但是記錄的移動(dòng)次數(shù)仍不能減少。如果文件（R1，R2，Rn）采用鏈接存儲(chǔ)，不能使用對(duì)半的方法尋找插入位置。第七章 排序7.1 基本概念7.2 插入排序 直接插入排序 希爾排序7.3 交換排序7.4 選擇排序7.5 合并排序7.6 基于關(guān)鍵詞比較的排序算法分析7.7 分布排序7.8 外排序 7.2.2 希爾(shell)排序1、希爾排序（漸減增量排序法）思想： 1959年Donald

11、 L. Shell提出Shell排序法 ，源自對(duì)直接插入算法的改進(jìn). 把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。 例 將十個(gè)數(shù)進(jìn)行希爾排序的示例。 0 1 2 3 4 5 6 7 8 9下標(biāo) 36 25 48 12 65 25 43 58 76 32d1=525434858127625363265 25 25 48 12 32 36 43 58 76 65一趟排序結(jié)果 例 將十個(gè)數(shù)進(jìn)行希爾排序的示例。 0 1 2 3 4 5 6 7 8 9下標(biāo)d2=2 25 25 48 12 32

12、36 43 58 76 65254832437625123658653243481225 25 12 32 25 43 36 48 58 76 65二趟排序結(jié)果 12 25 25 32 36 43 48 58 65 76三趟排序結(jié)果d3=1 希爾排序增量的取法： d1= = =5n/210/2d2= = =2d1/25/2d3= = =1d2/22/22、算法分析Shell算法的性能與所選取的分組長(zhǎng)度序列有很大關(guān)系。只對(duì)特定的待排序記錄序列，可以準(zhǔn)確地估算關(guān)鍵詞的比較次數(shù)和對(duì)象移動(dòng)次數(shù)。想要弄清關(guān)鍵詞比較次數(shù)和記錄移動(dòng)次數(shù)與增量選擇之間的關(guān)系，并給出完整的數(shù)學(xué)分析，至今仍然是數(shù)學(xué)難題。Shel

13、l算法的性能與所選取的分組長(zhǎng)度序列有很大關(guān)系。前面介紹的實(shí)例是最簡(jiǎn)單的分組長(zhǎng)度序列，即n/2i，最壞情況下時(shí)間復(fù)雜度為O(n2). 一般實(shí)際應(yīng)用中選擇2.2作為遞減因子效果更好，而不是2 . 如果選擇2k-1為分組長(zhǎng)度序列，最壞情況下能達(dá)到 . 第七章 排序7.1 基本概念7.2 插入排序7.3 交換排序 冒泡排序 快速排序7.4 選擇排序7.5 合并排序7.6 基于關(guān)鍵詞比較的排序算法分析7.7 分布排序7.8 外排序 7.3 交換排序反序?qū)Γ簩?duì)于序列K1, K2, , Kn, 若1iKj , 則稱(Ki,Kj)為上述序列的一個(gè)反序?qū)?。交換排序的思想：交換文件中存在的反序?qū)?，直到不存在反序?qū)?/p>

14、為止。交換排序包括：冒泡排序、分劃交換排序（快速排序）。7.3.1 冒泡排序 1、冒泡排序思想： 通過(guò)比較相鄰記錄的關(guān)鍵詞，交換存在逆序的記錄；使關(guān)鍵詞較大的記錄如氣泡一般逐漸往上“飄移”直至浮出“水面”。 i = 1090216080512 1 2 3 4 5 6 7 8 9131407 1 2 3 4 5 6 7 8 9090216080512131407i = 2 1 2 3 4 5 6 7 8 90902160805121314072、冒泡排序算法算法BSort ( R，n ) BS1 冒泡過(guò)程 FOR i=n TO 2 STEP 1 DO FOR j=1 TO i1 DO IF Kj

15、 Kj+1 THEN ( RjRj+1 ). 關(guān)鍵詞的比較次數(shù): (n-1)+(n-2)+1= (n-1)n/2經(jīng)過(guò)一趟冒泡，可以把具有最大關(guān)鍵詞的記錄移至最后（第n個(gè)位置）。第i趟冒泡，把第i大記錄放在第i個(gè)位置上。做n-1趟冒泡，就可以對(duì)所有記錄排序。發(fā)生一次記錄交換，反序?qū)Φ膫€(gè)數(shù)減少一個(gè)。排序中可能出現(xiàn)如下情況：每趟比較中，在某位置后，沒(méi)有記錄交換；最后幾趟沒(méi)有交換。i = 1090216080512 1 2 3 4 5 6 7 8 9131407 1 2 3 4 5 6 7 8 9090216080512131407i = 2 1 2 3 4 5 6 7 8 9090216080512

16、1314073、冒泡排序算法的改進(jìn)算法Bubble ( R，n ) Bubble1 終止位置初始化 BOUNDn /每趟冒泡關(guān)鍵詞比較的終止位置 Bubble2 冒泡過(guò)程 WHILE BOUND0 DO ( t0 /每趟冒泡記錄交換的最后位置 FOR j1 TO BOUND1 DO IF Kj Kj+1 THEN ( RjRj+1 . tj .) BOUNDt ) . 4、算法分析最好情形：記錄的初始排列按關(guān)鍵詞從小到大排好序時(shí)，此算法只執(zhí)行一趟起泡，做 n-1 次關(guān)鍵詞比較，不發(fā)生記錄交換；最壞情形：算法執(zhí)行了n-1趟起泡，第 i 趟 (1 i n) 做了 n- i 次關(guān)鍵詞比較，執(zhí)行了n-

17、i 次記錄交換,此時(shí)，總的關(guān)鍵詞比較次數(shù)和記錄交換次數(shù)為(n-1)n/2一般情形 假定記錄序列R1，R2，Rn所對(duì)應(yīng)的關(guān)鍵詞序列為A = K1，K2，Kn 令bj（1 j n）表示A中關(guān)鍵詞第 j 小的記錄左邊大于它的關(guān)鍵詞的個(gè)數(shù)，則文件 b1，b2，bn 稱為A的反序表. A=07, 09, 02, 16, 08, 05, 12, 14, 13 B=2, 4, 0, 2, 0, 1, 2, 1 , 0 經(jīng)過(guò)一趟冒泡后，記錄的位置發(fā)生變化，反序表也發(fā)生變化。 定理7.1 設(shè)K1，K2，Kn是序列1，2，n的一個(gè)排列，b1，b2，bn是對(duì)應(yīng)的反序表. 如果算法Bubble的一趟冒泡把K1, K2

18、, Kn改變?yōu)镵1, K2, Kn, 那么從b1, b2, bn中把每個(gè)非零元素減1, 就得到了相應(yīng)的反序表b1,b2,bn . A=07, 09, 02, 16, 08, 05, 12, 14, 13B=2, 4, 0, 2, 0, 1, 2, 1 , 0A=07, 02, 09, 08, 05, 12, 14, 13 , 16B=1, 3, 0, 1, 0, 0, 1, 0 , 0證明：如果Kj（1 j n）的左邊有大于Kj的元素，設(shè)Km = max Kt | 1 t Kj ，則由算法Bubble知，Rm一定會(huì)與Rj交換，且Rj左邊的其它元素不能與Rj交換。所以 如果Kj（1 j n）的左

19、邊沒(méi)有大于Kj的元素，即，則說(shuō)明Rj左邊的所有元素都小于Kj，從而一趟冒泡之后，Rj左邊的任何元素都不與Rj交換（因?yàn)樗鼈兌夹∮贙j），所以仍然有 . 證畢。改進(jìn)的冒泡排序算法的復(fù)雜性：5、冒泡排序算法總結(jié)時(shí)間復(fù)雜度：O(n2)（包括最壞和平均） .最好情況：當(dāng)被排序文件初態(tài)為正序時(shí)，算法的時(shí)間復(fù)雜度為O(n) . 穩(wěn)定性：冒泡排序是穩(wěn)定的排序方法。輔助存儲(chǔ)空間：O(1) . 為了進(jìn)一步提高效率，可采用氣泡上浮和下沉交替的方法。 第一趟第二趟第三趟第四趟79909090905679798888 90568879794885656563243235352732273232162716272788

20、163516163535444第七章 排序7.1 基本概念7.2 插入排序7.3 交換排序 冒泡排序 快速排序7.4 選擇排序7.5 合并排序7.6 基于關(guān)鍵詞比較的排序算法分析7.7 分布排序7.8 外排序7.3.2 分劃交換排序 1962年，Hoare提出了分劃交換排序，也叫快速排序 (Quick Sort)。算法的出發(fā)點(diǎn)： 1、通過(guò)交換反序?qū)ε判?，一次記錄交換使得文件中反序?qū)Φ臄?shù)目減少得最多; 2、一趟分劃把一個(gè)記錄直接放在其最終的位置上。1、快速排序的基本思想:任取待排序文件中的某個(gè)記錄 (例如取第一個(gè)記錄)作為基準(zhǔn)，按照該記錄的關(guān)鍵詞大小，將整個(gè)文件分劃為左右兩個(gè)子文件： 左側(cè)子文件

21、中所有記錄的關(guān)鍵詞都小于或等于基準(zhǔn)記錄的關(guān)鍵詞 右側(cè)子文件中所有記錄的關(guān)鍵詞都大于基準(zhǔn)記錄的關(guān)鍵詞基準(zhǔn)記錄排在兩個(gè)子文件中間。分別對(duì)兩個(gè)子文件重復(fù)上述方法，直到所有記錄都排在相應(yīng)位置上為止。2、快速排序算法描述QuickSort ( R ) if (R的長(zhǎng)度大于1) 將文件R分劃為兩個(gè)子文件LeftR 和 RightR; QuickSort ( LeftR );QuickSort ( RightR ); 將兩個(gè)子文件 LeftR 和 RightR合并為一個(gè)文件R; 算法QSort(R, m, n) / 快速排序的遞歸算法QSort1 遞歸出口 /Rm為基準(zhǔn)記錄，Rn+1關(guān)鍵詞最大 IF (mn

22、) THEN/ 長(zhǎng)度大于1 ( im . jn+1 . KKm . WHILE ij DO ( ii+1 WHILE KiK DO jj1 . IF ij THEN Ri Rj ) RmRj . / 對(duì) Rm.n 進(jìn)行一趟快排，j為基準(zhǔn)位置 IF mj-1 QSort ( R，m，j1 ) . / 對(duì)低子序列遞歸進(jìn)行排序 IF j+1n QSort ( R，j+1，n ) ) / 對(duì)高子序列遞歸進(jìn)行排序 (1) (2) (3) (4) (5) (6) (7) (8) (9) 70 73 69 23 93 18 11 68 100i=1j=9i=2 70 68 69 23 93 18 11 73

23、 100j=8 70 68 69 23 93 18 11 73 100i=3j=8 70 68 69 23 93 18 11 73 100i=4j=8 70 68 69 23 93 18 11 73 100i=5j=8 70 68 69 23 93 18 11 73 100i=5j=7 70 68 69 23 11 18 93 73 100i=5j=7 70 68 69 23 11 18 93 73 100i=7j=618 68 69 23 11 70 93 73 100WHILE ij DO ( ii+1 WHILE KiK DO jj1 . IF ij THEN Ri Rj ) RmRj

24、.快速排序一次分劃過(guò)程示例:18 68 69 23 11 70 93 73j=6一趟結(jié)果 11 18 68 23 69 70 73 93j=5三趟結(jié)果11 18 23 68 69 70 73 93最終結(jié)果多趟快速排序過(guò)程示例 11 18 23 68 69 70 73 93四趟結(jié)果j=411 18 69 23 68 70 73 93j=2二趟結(jié)果j=8 18 68 69 23 11 70 93 73j=611 18 69 23 68 70 93 73j=2 11 18 68 23 69 70 93 73j=511 18 23 68 69 70 73 93最終結(jié)果 11 18 23 68 69 7

25、0 73 93j=8j=4算法QSort(R，m，n) IF m n THEN ( im . jn+1 . KKm . QSort1；/一次分劃程序段 IF mj-1 QSort ( R，m，j1 ) .L1: IF j+1n QSort ( R，j+1，n ). L2: ) 棧 L0 1 8 6 L m n j L1 1 5 2 L2 3 5 5 L1 3 4 4 18 68 69 23 11 70 93 73j=611 18 69 23 68 70 93 73j=2 11 18 68 23 69 70 93 73j=511 18 23 68 69 70 73 93最終結(jié)果 11 18 23

26、 68 69 70 73 93j=8j=4棧 L0 1 8 6 L m n j L1 1 5 2 L2 3 5 5 算法QSort(R，m，n) IF m n THEN ( im . jn+1 . KKm . QSort1；/一次分劃程序段 IF mj-1 QSort ( R，m，j1 ) .L1: IF j+1n QSort ( R，j+1，n ). L2: ) 18 68 69 23 11 70 93 73j=611 18 69 23 68 70 93 73j=2 11 18 68 23 69 70 93 73j=511 18 23 68 69 70 73 93最終結(jié)果 11 18 23

27、68 69 70 73 93j=8j=4棧 L0 1 8 6 L m n j L1 1 5 2 算法QSort(R，m，n) IF m n THEN ( im . jn+1 . KKm . QSort1；/一次分劃程序段 IF mj-1 QSort ( R，m，j1 ) .L1: IF j+1n QSort ( R，j+1，n ). L2: ) 18 68 69 23 11 70 93 73j=611 18 69 23 68 70 93 73j=2 11 18 68 23 69 70 93 73j=511 18 23 68 69 70 73 93最終結(jié)果 11 18 23 68 69 70 7

28、3 93j=8j=4棧 L0 1 8 6 L m n j 算法QSort(R，m，n) IF m n THEN ( im . jn+1 . KKm . QSort1；/一次分劃程序段 IF mj-1 QSort ( R，m，j1 ) .L1: IF j+1n QSort ( R，j+1，n ). L2: ) 18 68 69 23 11 70 93 73j=611 18 69 23 68 70 93 73j=2 11 18 68 23 69 70 93 73j=511 18 23 68 69 70 73 93最終結(jié)果 11 18 23 68 69 70 73 93j=8j=4棧 L0 1 8

29、6 L m n j L2 7 8 8 算法QSort(R，m，n) IF m n THEN ( im . jn+1 . KKm . QSort1；/一次分劃程序段 IF mj-1 QSort ( R，m，j1 ) .L1: IF j+1n QSort ( R，j+1，n ). L2: ) 18 68 69 23 11 70 93 73j=611 18 69 23 68 70 93 73j=2 11 18 68 23 69 70 93 73j=511 18 23 68 69 70 73 93最終結(jié)果 11 18 23 68 69 70 73 93j=8j=4棧 L0 1 8 6 L m n j

30、算法QSort(R，m，n) IF m n THEN ( im . jn+1 . KKm . QSort1；/一次分劃程序段 IF mj-1 QSort ( R，m，j1 ) .L1: IF j+1n QSort ( R，j+1，n ). L2: ) 18 68 69 23 11 70 93 73j=611 18 69 23 68 70 93 73j=2 11 18 68 23 69 70 93 73j=511 18 23 68 69 70 73 93最終結(jié)果 11 18 23 68 69 70 73 93j=8j=4棧空 L m n j 算法QSort(R，m，n) IF m n THEN

31、( im . jn+1 . KKm . QSort1；/一次分劃程序段 IF mj-1 QSort ( R，m，j1 ) .L1: IF j+1n QSort ( R，j+1，n ). L2: ) 3、算法分析算法Qsort是遞歸的算法，其遞歸樹(shù)如圖所示。一個(gè)結(jié)點(diǎn)表示一次遞歸調(diào)用。快速排序的趟數(shù)取決于遞歸樹(shù)的深度。每次分劃后，基準(zhǔn)記錄的左右子序列長(zhǎng)度相同，是最理想的情況。7093731869682311一次分劃過(guò)程(R,m,n)，有兩個(gè)記錄與基準(zhǔn)記錄比較兩次，其余的記錄和基準(zhǔn)記錄各比較一次。關(guān)鍵詞的比較次數(shù)為n-m+2。 (1) (2) (3) (4) (5) (6) (7) (8) (9)

32、70 73 69 23 93 18 11 68 100i=1j=9i=2 70 68 69 23 93 18 11 73 100j=8 70 68 69 23 93 18 11 73 100i=3j=8 70 68 69 23 93 18 11 73 100i=4j=8 70 68 69 23 93 18 11 73 100i=5j=8 70 68 69 23 93 18 11 73 100i=5j=7 70 68 69 23 11 18 93 73 100i=5j=7 70 68 69 23 11 18 93 73 100i=7j=618 68 69 23 11 70 93 73 1004、

33、快速排序算法總結(jié)時(shí)間復(fù)雜度: O(n2)/最壞 . 時(shí)間復(fù)雜度: O(nlog2n) /最好和平均輔助空間： O(log2n) .穩(wěn)定性：快速排序是不穩(wěn)定的排序方法?？焖倥判蚍椒▽?duì)于 n 較大的平均情況而言，是目前內(nèi)部排序中最好、最快的排序方法。但當(dāng) n 很小時(shí)，這種排序方法往往比其它簡(jiǎn)單排序方法還慢。第七章 排序7.1 基本概念7.2 插入排序7.3 交換排序7.4 選擇排序 直接選擇排序 堆排序7.5 合并排序7.6 基于關(guān)鍵詞比較的排序算法分析7.7 分布排序7.8 外排序 7.4 選擇排序 思想：對(duì)待排序的文件進(jìn)行n次選擇操作，其中第i次選擇第i小(或大)的記錄放在第i(或n-i+1)

34、的位置上。 直接選擇排序、堆排序7.4.1 直接選擇排序 1、直接選擇排序思想： 選擇第 i （i = 1,2, , n-1）大的記錄的具體辦法：在剩余的n-i+1個(gè)記錄中進(jìn)行一趟比較，確定出第i大記錄，放在第n-i+1位置上。 17 78 6 54 34 38 17 38 6 54 34 78 17 38 6 34 54 782、直接選擇排序算法算法 SSort (R, n) /待排序文件(R1,R2,Rn)SS1 排序 FOR j=n TO 2 STEP 1 DO ( /從1到j(luò)找最大元素的下標(biāo)t t1 . FOR i2 TO j DO IF KtKi THEN ti RjRt ) / 將

35、Rt放到第j個(gè)位置上 (1) (2) (3) (4) (5) (6) i t 21 25 49 25* 16 08 2 1 初始序列 2 算法 SSort（R，n） FOR j=n TO 2 STEP -1 DO ( t1 . FOR i2 TO j DO IF Kt Ki THEN ti Rj Rt) 21 25 49 25* 16 08 3 2 21 25 49 25* 16 08 4 3 21 25 49 25* 16 08 5 3 21 25 49 25* 16 08 6 3 21 25 08 25* 16 49 21 25 49 25* 16 08一趟直接選擇排序過(guò)程示例多趟直接選擇

36、排序過(guò)程示例 (1) (2) (3) (4) (5) (6) t 1 21 25 08 25* 16 49 2 2 21 16 08 25* 25 49 4 3 21 16 08 25* 25 49 1 5 08 16 21 25* 25 49 21 25 49 25* 16 08 3 初始序列 4 08 16 21 25* 25 49 2 3、算法分析直接選擇排序的關(guān)鍵詞比較次數(shù)與記錄的初始排列無(wú)關(guān)。假定整個(gè)待排序文件有 n 個(gè)記錄，則第 i 趟選擇所需的比較次數(shù)是 n-i 次?？偟年P(guān)鍵詞比較次數(shù)為 (n-1)+(n-2)+1= (n-1)n/2記錄交換次數(shù)是選擇的趟數(shù): n-1. 4、直接

37、選擇排序算法總結(jié)時(shí)間復(fù)雜度: O(n2)（包括最好、最壞和平均） . 穩(wěn)定性：不穩(wěn)定的排序方法。輔助空間： O(1) . 優(yōu)點(diǎn)：簡(jiǎn)單、書寫容易第七章 排序7.1 基本概念7.2 插入排序7.3 交換排序7.4 選擇排序 直接選擇排序 堆排序7.5 合并排序7.6 基于關(guān)鍵詞比較的排序算法分析7.7 分布排序7.8 外排序7.4.2 堆排序1、堆排序的原理 選擇排序的關(guān)鍵：找最大記錄 堆排序：利用淘汰賽的方式尋找當(dāng)前序列中的最大記錄淘汰賽的思想：對(duì)n個(gè)選手，兩兩比賽，得到 n/2 個(gè)優(yōu)勝者，作為第一輪的結(jié)果；然后對(duì)這n/2個(gè)選手，再兩兩比賽，如此重復(fù)，直到選出一個(gè)冠軍。滿二叉樹(shù)的葉結(jié)點(diǎn)，存放待排

38、序記錄的關(guān)鍵詞。如果 n 不是2的 k 次冪，則讓葉結(jié)點(diǎn)數(shù)補(bǔ)足到滿足 2k-1 n 2k 的2k個(gè)。非葉結(jié)點(diǎn)是關(guān)鍵詞兩兩比較的結(jié)果，根結(jié)點(diǎn)的關(guān)鍵詞最大。63Winner 49631663492521254925*160863tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14比賽樹(shù)的概念每次兩兩比較的結(jié)果是把關(guān)鍵詞大者作為優(yōu)勝者上升到雙親結(jié)點(diǎn)，稱這種樹(shù)為比賽樹(shù)。位于最底層的葉結(jié)點(diǎn)叫做比賽樹(shù)的外結(jié)點(diǎn)，非葉結(jié)點(diǎn)稱為比賽樹(shù)的內(nèi)結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)除了存放記錄的關(guān)鍵詞外，還存放了此對(duì)象在滿二叉樹(shù)中的序號(hào)。比賽樹(shù)最頂層是樹(shù)的根，表示最后選擇出來(lái)的具有最大關(guān)鍵

39、詞的記錄。形成初始比賽樹(shù)（最大關(guān)鍵詞上升到根）得到最大記錄R763Winner 49631663492521254925*160863tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14R7利用比賽樹(shù)的排序第1步將剩余6個(gè)記錄，調(diào)整為新的比賽樹(shù)得到第2大記錄R649Winner 491616-492521254925*1608-tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14R6利用比賽樹(shù)的排序第2步將剩余6個(gè)記錄，調(diào)整為新的比賽樹(shù)得到第2大記錄R625Winner 251616-25*

40、25212525*1608-tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14R5利用比賽樹(shù)的排序第3步-上述過(guò)程重復(fù)進(jìn)行結(jié)果全部輸出時(shí)，比賽樹(shù)的狀態(tài)08Winner 0808-08-tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14R1-2、堆的定義如果有一個(gè)關(guān)鍵碼的集合Kk1,k2,kn把它的所有元素按完全二叉樹(shù)的順序(數(shù)組)存儲(chǔ)方式存放在一個(gè)一維數(shù)組中。并且滿足 ki k2i且ki k2i+1 / 小根堆 或 ki k2i且ki k2i+1 / 大根堆 94937591854451

41、1848581034例 1 2 3 4 5 6 7 8 9 10 11 12 94 93 75 91 85 44 51 18 48 58 10 34堆的定義完全二叉樹(shù)的數(shù)組表示 Ki K2i & Ki K2i+1完全二叉樹(shù)的數(shù)組表示 Ki K2i & Ki K2i+1 3、堆排序算法設(shè)數(shù)組R存放堆，則R1是關(guān)鍵詞最大的記錄，將R1和Rn互換，使得最大記錄放在Rn的位置。調(diào)整R1，Rn-1，使之成為新堆，則R1是其中最大者，再交換R1與Rn-1，使Rn-1中放入次最大記錄。再對(duì)R1，R2，Rn-2調(diào)整，使之成為新堆，再進(jìn)行類似的交換，上述操作反復(fù)進(jìn)行，直到調(diào)整范圍只剩下一個(gè)記錄R1為止。此時(shí)，R

42、1是n個(gè)記錄中最小的，且數(shù)組Rn中的記錄已經(jīng)按從小到大排列了。堆排序算法的粗略描述： （l）建立包含Kl，K2，Kn的堆； （2）FOR in TO 2 STEP 1 DO （R1Ri 重建包含K1，K2，Ki1的堆 ）需解決的兩個(gè)問(wèn)題： 如何建堆 如何調(diào)整新堆問(wèn)題 初始建堆: 將以序號(hào)n/2，n/21 , 1的結(jié)點(diǎn)為根的子樹(shù)都調(diào)整為堆即可。 例 關(guān)鍵詞序列（42,13,91,23,24,16,05,88)。4213912324160588421391232416058842139188241605234213918824160523421391882416052342889113241605

43、234288911324160523428891232416051342889123241605139188422324160513初始建堆過(guò)程圖形說(shuō)明：9188422324160513問(wèn)題重建堆：R1與Ri交換后，只有R1與其左右兒子不滿足堆的性質(zhì)。13884223241605914288912324160513884223241605428891232416058813422324160542889123241605881342232416054288912324160588244223131605428891232416058824422313160591堆排序過(guò)程圖形說(shuō)明：428891

44、232416051391884223241605134288912324160513918842232416051342889123241605131388422324160591428891232416051313884223241605914288912324160513881342232416059142889123241605138813422324160591428891232416051388244223131605914288912324160513882442231316059142889123241605138824422313160591428891232416051305

45、2442231316889142889123241605134224162313058891堆排序過(guò)程：4288912324160513052416231342889142889123241605132423160513428891堆排序過(guò)程：42889123241605134224162313058891堆排序過(guò)程：428891232416051324231605134288914288912324160513132316052442889142889123241605132313160524428891堆排序過(guò)程：42889123241605132313160524428891428891

46、2324160513051316232442889142889123241605131613052324428891堆排序過(guò)程：428891232416051316130523244288914288912324160513051316232442889142889123241605131305162324428891堆排序過(guò)程：428891232416051313051623244288914288912324160513051316232442889142889123241605130513162324428891算法Restore（R，f，e）/ 建堆R1 初始化 jf R2 建堆 WH

47、ILE je/2 DO (IF(2j e)AND(K2j Kj THEN（RmRj . jm ） ELSE je ）42139123241605884213912324160588j=4HS1 初始建堆FOR in2 TO 1 STEP 1 DORestore（R，i，n） 42139188241605234213918824160523j=842139188241605234213918824160523j=342139188241605234213918824160523j=242889113241605234288911324160523j=44288911324160523428891

48、1324160523j=442889123241605134288912324160513j=842889123241605134288912324160513j=191884223241605139188422324160513j=3算法HeapSort ( R，n ) / 堆排序算法 HS1 初始建堆 FOR in2 TO 1 STEP 1 DO Restore（R，i，n） HS2 排序 FOR in TO 2 STEP 1 DO ( R1Ri . Restore ( R，1，i1 ) ) 4288912324160513918842232416051342889123241605139

49、188422324160513428891232416051313884223241605914288912324160513138842232416059142889123241605138813422324160591428891232416051388134223241605914288912324160513882442231316059142889123241605138824422313160591重建堆算法的時(shí)間復(fù)雜度為 O(log2n)138842232416059188244223131605914、堆排序算法總結(jié)時(shí)間復(fù)雜度: 最好、最壞和平均情況相同 重建堆算法為 O(lo

50、g2n) 堆排序算法為O(nlog2n) . 穩(wěn)定性：堆排序是不穩(wěn)定的排序方法。輔助存儲(chǔ)空間： O(1) . 492525*211608012345082525*16214902543149 25 21 25* 16 0808 25 21 25* 16 49交換 0 號(hào)與 5 號(hào)對(duì)象,5 號(hào)對(duì)象就位初始最大堆2525*082116490123451625*0825214902543125 25* 21 08 16 4916 25* 21 08 25 492525*082116490123451625*0825214902543125 25* 21 08 16 4916 25* 21 08 25

51、 49交換 0 號(hào)與 4 號(hào)對(duì)象,4 號(hào)對(duì)象就位從 0 號(hào)到 4 號(hào) 重新調(diào)整為最大堆25*1608212549012345081625*25214902543125* 16 21 08 25 4908 16 21 25* 25 49交換 0 號(hào)與 3 號(hào)對(duì)象,3 號(hào)對(duì)象就位從 0 號(hào)到 3 號(hào) 重新調(diào)整為最大堆211625*082549012345081625*25214902543121 16 08 25* 25 4908 16 21 25* 25 49交換 0 號(hào)與 2 號(hào)對(duì)象,2 號(hào)對(duì)象就位從 0 號(hào)到 2 號(hào) 重新調(diào)整為最大堆堆存在于順序線性表（數(shù)組）中160825*21254901

52、2345081625*25214902543116 08 21 25* 25 4908 16 21 25* 25 49交換 0 號(hào)與 1 號(hào)對(duì)象,1 號(hào)對(duì)象就位從 0 號(hào)到 1 號(hào) 重新調(diào)整為最大堆第七章 排序7.1 基本概念7.2 插入排序7.3 交換排序7.4 選擇排序7.5 合并排序7.6 基于關(guān)鍵詞比較的排序算法分析7.7 分布排序7.5 合并排序1、合并合并(歸并)：把兩個(gè)或多個(gè)有序文件合并成一個(gè)單一的有序文件。合并的基本思想：設(shè)兩個(gè)有序表A和B的記錄個(gè)數(shù)(表長(zhǎng))分別為 al 和 bl，變量 i 和 j 分別是表A和表B的當(dāng)前檢測(cè)指針。設(shè)表C是歸并后的新有序表，變量 k 是它的當(dāng)前存放指針。08 21 25 25* 49 62 72 93 16 37 54 l m m+1 ni j08 16 21 25 25* 37 49 54 62 72 93 l nkC當(dāng)