組織計(jì)算機(jī)軟件考試推動(dòng)軟件職業(yè)技術(shù)教育改革

1、2024/3/16,1,第8章 排序,排序的概念及種類 插入法排序的各種具體實(shí)現(xiàn)方法及算法分析 選擇法排序的各種具體方法的實(shí)現(xiàn)及時(shí)間性能分析 交換法排序的具體實(shí)現(xiàn)及性能分析 歸并排序和基數(shù)排序的各自實(shí)現(xiàn)算法,2024/3/16,2,本章導(dǎo)讀,排序是日常工作和軟件設(shè)計(jì)中常用的運(yùn)算之一。為了提高查詢速度需要將無(wú)序序列按照一定的順序組織成有序序列。由于需要排序的數(shù)據(jù)表的基本特性可能存在差異，使得排序方法也不同。如何合

2、理地組織數(shù)據(jù)的邏輯順序，按照何種方式排出的序列最有效？這是本章要討論的主題。本章主要介紹排序的概念及幾種最常見(jiàn)的排序方法，討論其性能和特點(diǎn)，并在此基礎(chǔ)上進(jìn)一步討論各種方法的適用場(chǎng)合，以便在實(shí)際應(yīng)用中能根據(jù)具體的問(wèn)題選擇合適的排序方法。通過(guò)本章學(xué)習(xí)，讀者應(yīng)該掌握以下幾項(xiàng)內(nèi)容： 排序的概念及種類 插入法排序的各種具體實(shí)現(xiàn)方法及算法分析 選擇法排序的各種具體方法的實(shí)現(xiàn)及時(shí)間性能分析 交換法排序的具體實(shí)現(xiàn)及性能分析

3、 歸并排序和基數(shù)排序的各自實(shí)現(xiàn)算法,2024/3/16,3,8.1 排序的基本概念,8.1.1 排序及其分類,1．排序概念,排序（sorting）又稱分類，是數(shù)據(jù)處理領(lǐng)域中一種很常用的運(yùn)算。排序就是把一組記錄或數(shù)據(jù)元素的無(wú)序序列按照某個(gè)關(guān)鍵字值（關(guān)鍵字）遞增或遞減的次序重新排列的過(guò)程。排序的主要目的就是實(shí)現(xiàn)快速查找。日常生活中通過(guò)排序以后進(jìn)行檢索的例子屢見(jiàn)不鮮。如電話簿、病歷、檔案室中的檔案、圖書館和各種詞典的目錄表等，幾乎都需要對(duì)

4、有序數(shù)據(jù)進(jìn)行操作。,2024/3/16,4,假設(shè)含有n個(gè)記錄的序列為：{R1，R2 ，…，Rn} (8-1)其相應(yīng)的關(guān)鍵字序列為： {K1，K2 ，…，Kn}需確定1，2， …，n的一種排序p1，p2， …，pn，使其相應(yīng)的關(guān)鍵字滿足如下關(guān)系：Kp1≤Kp2≤…≤Kpn (8-2)即使得式（8-1）的序列成為一個(gè)按關(guān)鍵字有序的序列{R p1，R p

5、2 ，…，Rpn} (8-3) 這個(gè)將原有表中任意順序的記錄變成一個(gè)按關(guān)鍵字有序排列的過(guò)程稱為排序。,2024/3/16,5,2．排序分類,增排序和減排序：如果排序的結(jié)果是按關(guān)鍵字從小到大的次序排列的，就是增排序，否則就是減排序。 穩(wěn)定排序和不穩(wěn)定排序：假設(shè)Ki=Kj（1≤i≤n，1≤j≤n，i≠j），且在排序前的序列中Ri領(lǐng)先于Rj（即i<j）。若在排序后的排序中Ri仍領(lǐng)先于Rj，即那些具

6、有相同關(guān)鍵字的記錄，經(jīng)過(guò)排序后它們的相對(duì)次序仍然保持不變，則稱這種排序方法是穩(wěn)定的；反之，若Rj領(lǐng)先于Ri，則稱所用的方法是不穩(wěn)定的。,2024/3/16,6,(3) 內(nèi)部排序與外部排序：在排序中，若數(shù)據(jù)表中的所有記錄的排列過(guò)程都是在內(nèi)存中進(jìn)行的，稱為內(nèi)部排序。由于待排序的記錄數(shù)量太多，在排序過(guò)程中不能同時(shí)把全部記錄放在內(nèi)存，需要不斷地通過(guò)在內(nèi)存和外存之間交換數(shù)據(jù)元素來(lái)完成整個(gè)排序的過(guò)程，稱為外部排序。在外部排序情況下，只有部分記錄進(jìn)入

7、內(nèi)存，在內(nèi)存中進(jìn)行內(nèi)部排序，待排序完成后再交換到外部存儲(chǔ)器中加以保存。然后再將其它待排序的記錄調(diào)入內(nèi)存繼續(xù)排序。這一過(guò)程需要反復(fù)進(jìn)行，直到全部記錄排出次序?yàn)橹埂ｏ@然，內(nèi)部排序是外部排序的基礎(chǔ)，本章先介紹內(nèi)部排序的各種方法，最后再討論外部排序。,2024/3/16,7,8.1.2 排序算法的效率分析,與許多算法一樣，對(duì)各種排序算法性能的評(píng)價(jià)主要從兩個(gè)方面來(lái)考慮，一是時(shí)間性能；二是空間性能。,1． 時(shí)間復(fù)雜度分析,排序算法的時(shí)間復(fù)雜度可用

8、排序過(guò)程中記錄之間關(guān)鍵字的比較次數(shù)與記錄的移動(dòng)次數(shù)來(lái)衡量。在本章各節(jié)中討論算法的時(shí)間復(fù)雜度時(shí)，一般都按平均時(shí)間復(fù)雜度進(jìn)行估算；對(duì)于那些受數(shù)據(jù)表中記錄的初始排列及記錄數(shù)目影響較大的算法，按最好情況和最壞情況分別進(jìn)行估算。,2024/3/16,8,2．空間復(fù)雜度分析,排序算法的空間復(fù)雜度是指算法在執(zhí)行時(shí)所需的附加存儲(chǔ)空間，也就是用來(lái)臨時(shí)存儲(chǔ)數(shù)據(jù)的內(nèi)存使用情況。 在以后的排序算法中，若無(wú)特別說(shuō)明，均假定待排序的記錄序列采用順序表結(jié)構(gòu)來(lái)

9、存儲(chǔ)，即數(shù)組存儲(chǔ)方式，并假定是按關(guān)鍵字遞增方式排序。為簡(jiǎn)單起見(jiàn)，假設(shè)關(guān)鍵字類型為整型。待排序的順序表類型的類型定義如下： typedef int KeyType //定義關(guān)鍵字類型 typedef struct dataType //記錄類型 { keytype key; //關(guān)鍵字項(xiàng) elemtype otherelement; //其他數(shù)據(jù)項(xiàng)

10、 }RecType;,2024/3/16,9,8.2 插入排序,插入排序的基本思想是：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子表中的適當(dāng)位置，直到全部記錄插入完成為止。也就是說(shuō)，將待序列表分成左右兩部分，左邊為有序表（有序序列），右邊為無(wú)序表（無(wú)序序列）。整個(gè)排序過(guò)程就是將右邊無(wú)序表中的記錄逐個(gè)插入到左邊的有序表中，構(gòu)成新的有序序列。根據(jù)不同的插入方法，插入排序算法主要包括：直接插入排序、折半插入排序、表插入排序和

11、希爾排序等。本章重點(diǎn)介紹直接插入排序、折半插入排序和希爾排序。,2024/3/16,10,8.2.1 直接插入排序,直接插入排序(Insertion Sort)是所有排序方法中最簡(jiǎn)單的一種排序方法。其基本原理是順次地從無(wú)序表中取出記錄Ri(1≤i≤n)，與有序表中記錄的關(guān)鍵字逐個(gè)進(jìn)行比較，找出其應(yīng)該插入的位置，再將此位置及其之后的所有記錄依次向后順移一個(gè)位置，將記錄Ri插入其中。 假設(shè)待排序的n個(gè)記錄為{R1，R2 ，……，

12、Rn}，初始有序表為[R1]，初始無(wú)序表為[R2 …Rn]。當(dāng)插入第i個(gè)記錄Ri(2≤i≤n)時(shí)，有序表為[R1…Ri-1]，無(wú)序表為[Ri …Rn]。將關(guān)鍵字K i依次與Ki-1，Ki-2 ，…，K1進(jìn)行比較，找出其應(yīng)該插入的位置，將該位置及其以后的記錄向后順移，插入記錄Ri，完成序列中第i個(gè)記錄的插入排序。當(dāng)完成序列中第n個(gè)記錄Rn的插入后，整個(gè)序列排序完畢。,2024/3/16,11,向有序表中插入記錄，主要完成如下操作：(1)

13、 搜索插入位置。(2) 移動(dòng)插入點(diǎn)及其以后的記錄空出插入位置。(3) 插入記錄。,假設(shè)將n個(gè)待排序的記錄順序存放在長(zhǎng)度為n+1的數(shù)組R[1]～R[n] 中。R[0]作為輔助空間，用來(lái)暫時(shí)存儲(chǔ)需要插入的記錄，起監(jiān)視哨的作用。直接插入排序算法如下:,2024/3/16,12,void Insert_Sort(int R[],int n) {int i,j; for(i=2;i<=n; i++) //表示待插入元素的下標(biāo)

14、 {R[0]=R[i]; //設(shè)置監(jiān)視哨保存待插入元素，騰出R[i]空間 j=i-1; //j指示當(dāng)前空位置的前一個(gè)元素 while(R[0].key<R[j].key)//搜索插入位置并后移騰出空 {R[j+1]=R[j]; j--; } R[j+1]=R[0]; //插入元素 }},2024/3/16,13,顯然，開(kāi)始時(shí)有序表中只有1個(gè)記

15、錄[R[1]]，然后需要將R[2]～R[n]的記錄依次插入到有序表中，總共要進(jìn)行n-1次插入操作。首先從無(wú)序表中取出待插入的第i個(gè)記錄R[i]，暫存在R[0]中；然后將R[0].key依次與R[i-1].key，R[i-2].key，…進(jìn)行比較，如果R[0].key<R[i-j].key（1≤j≤i-1），則將R[i-j]后移一個(gè)單元；如果R[0].key≥R[i-j].key，則找到R[0]插入的位置i-j+1，此位置已經(jīng)空出，

16、將R[0] (即R[i])記錄直接插入即可。然后采用同樣的方法完成下一個(gè)記錄R[i+1]的插入排序。如此不斷進(jìn)行，直到完成記錄R[n]的插入排序，整個(gè)序列變成按關(guān)鍵字非遞減的有序序列為止。在搜索插入位置的過(guò)程中，R[0].key與R[i-j].key進(jìn)行比較時(shí)，如果j=i，則循環(huán)條件 R[0].key<R[i-j].key不成立，從而退出while 循環(huán)。由此可見(jiàn)R[0]起到了監(jiān)視哨的作用，避免了數(shù)組下標(biāo)的出界。,2024/3/1

17、6,14,【例8-1】假設(shè)有7個(gè)待排序的記錄，它們的關(guān)鍵字分別為23，4，15，8，19，24，15，用直接插入法進(jìn)行排序。,【解】直接插入排序過(guò)程如圖8-1所示。方括號(hào)[ ]中為已排好序的記錄的關(guān)鍵字，有兩個(gè)記錄的關(guān)鍵字都為15，為表示區(qū)別，將后一個(gè)15加下劃線。,圖8-1 直接插入排序,2024/3/16,15,空間性能：該算法僅需要一個(gè)記錄的輔助存儲(chǔ)空間，空間復(fù)雜度為O(1)。時(shí)間性能：整個(gè)算法執(zhí)行for循環(huán)n-1次，每次循環(huán)

18、中的基本操作是比較和移動(dòng)，其總次數(shù)取決于數(shù)據(jù)表的初始特性，可能有以下幾種情況：（1）當(dāng)初始記錄序列的關(guān)鍵字已是遞增排列時(shí)，這是最好的情況。算法中while語(yǔ)句的循環(huán)體執(zhí)行次數(shù)為0，因此，在一趟排序中關(guān)鍵字的比較次數(shù)為1，即R[0]的關(guān)鍵字與R[j]的關(guān)鍵字比較。而移動(dòng)次數(shù)為2，即R[i]移動(dòng)到R[0]中，R[0]移動(dòng)到R[j+1]中。所以，整個(gè)排序過(guò)程中的比較次數(shù)和移動(dòng)次數(shù)分別為(n-1)和2×(n-1)， 因而其時(shí)間復(fù)雜度

19、為O(n)。,穩(wěn)定性：由于該算法在搜索插入位置時(shí)遇到關(guān)鍵字值相等的記錄時(shí)就停止操作，不會(huì)把關(guān)鍵字值相等的兩個(gè)數(shù)據(jù)交換位置，所以該算法是穩(wěn)定的。,2024/3/16,16,（2）當(dāng)初始數(shù)據(jù)序列的關(guān)鍵字序列是遞減排列時(shí)，這是最壞的情況。在第i次排序時(shí)， while語(yǔ)句內(nèi)的循環(huán)體執(zhí)行次數(shù)為i。因此，關(guān)鍵字的比較次數(shù)為i，而移動(dòng)次數(shù)為i+1。所以，整個(gè)排序過(guò)程中的比較次數(shù)和移動(dòng)次數(shù)分別為：,（3）一般情況下，可認(rèn)為出現(xiàn)各種排列的概率相同，因此取

20、上述兩種情況的平均值，作為直接插入排序關(guān)鍵字的比較次數(shù)和記錄移動(dòng)次數(shù)，約為n2/4。所以其時(shí)間復(fù)雜度為O(n2)。根據(jù)上述分析得知：當(dāng)原始序列越接近有序時(shí)，該算法的執(zhí)行效率就越高。,2024/3/16,17,8.2.2 折半插入排序,直接插入排序的基本操作是在有序表中進(jìn)行查找和插入，而在有序表中查找插入位置，可以通過(guò)折半查找的方法實(shí)現(xiàn)，由此進(jìn)行的插入排序稱之為折半插入排序。 所謂折半查找，就是在插入Ri時(shí)（此時(shí)R1，R2，…

21、，Ri-1已排序），取R?i/2?的關(guān)鍵字K?i/2? 與Ki進(jìn)行比較（?i/2? 表示取不大于i/2的最大整數(shù)），如果Ki<K?i/2?，Ri的插入位置只能在R1和R?i/2? 之間，則在R1和R?i/2?-1之間繼續(xù)進(jìn)行折半查找，否則在R?i/2?+1和Ri-1 之間進(jìn)行折半查找。如此反復(fù)直到最后確定插入位置為止。折半查找的過(guò)程是以處于有序表中間位置記錄的關(guān)鍵字和Ki比較，經(jīng)過(guò)一次比較，便可排除一半記錄，把可插入的區(qū)間縮小一半

22、，故稱為折半。,2024/3/16,18,設(shè)置始指針low，指向有序表的第一個(gè)記錄，尾指針high，指向有序表的最后一個(gè)記錄，中間指針mid指向有序表中間位置的記錄。每次將待插入記錄的關(guān)鍵字與mid位置記錄的關(guān)鍵字進(jìn)行比較，從而確定待插入記錄的插入位置。折半插入排序算法如下：,typedef int keytype;void Insert_halfSort(RecType R[],int n){/*對(duì)順序表R作折半插入排序

23、*/ int i,j,low,high,mid;for(i=2; i<=n; i++){ R[0]=R[i]; //保存待插入元素 low=1; high=i-1; //設(shè)置初始區(qū)間,2024/3/16,19,while(lowR[mid].key)low=mid+1; 插入位置在后半部分中 else high=mid-1; //插入位置

24、在前半部分中} for(j=i-1;j>=high+1; --j) //high+1為插入位置 R[j+1]=R[j]; //后移元素，空出插入位置 R[high+1]=R[0]; //將元素插入 }},2024/3/16,20,【例8-2】待排序記錄的關(guān)鍵字為：28，13，72，85，39，4

25、1，6，20，在前7個(gè)記錄都已排好序的基礎(chǔ)上，采用折半插入第8個(gè)記錄的比較過(guò)程如圖8-2所示。,圖8-2 折半插入排序,2024/3/16,21,折半插入排序的比較次數(shù)與待排序記錄的初始排列次序無(wú)關(guān)，僅依賴于記錄的個(gè)數(shù)。插入第i個(gè)元素時(shí)，如果i=2j（1≤j≤?log2n?），則無(wú)論關(guān)鍵字值的大小，都恰好經(jīng)過(guò)j= log2i次比較才能確定其應(yīng)插入的位置；如果2j<i≤2j+1，則比較次數(shù)為j+1。因此將n個(gè)記錄（設(shè)n=2k）排序

26、的總比較次數(shù)為：,2024/3/16,22,折半插入排序僅減少了關(guān)鍵字間的比較次數(shù)，但記錄的移動(dòng)次數(shù)不變。因此折半插入排序的時(shí)間復(fù)雜度仍為O(n2)。折半插入排序的空間復(fù)雜度與直接插入排序相同。折半插入排序也是一個(gè)穩(wěn)定的排序方法。,2024/3/16,23,8.2.3 希爾排序,希爾排序（shell’s sort）又稱縮小增量排序(Diminishing Increment Sort)。它是希爾（D.L.Shell）于1959年提出

27、的插入排序的改進(jìn)算法。如前所述，直接插入排序算法的時(shí)間性能取決于數(shù)據(jù)的初始特性，一般情況下，它的時(shí)間復(fù)雜度為O(n2)。但是當(dāng)待排序列為正序或基本有序時(shí)，時(shí)間復(fù)雜度則為O(n)。因此，若能在一次排序前將排序序列調(diào)整為基本有序，則排序的效率就會(huì)大大提高。正是基于這樣的考慮，希爾提出了改進(jìn)的插入排序方法。 希爾排序的基本思想是：先將整個(gè)待排記錄序列分割成若干小組（子序列），分別在組內(nèi)進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)

28、，再對(duì)全體記錄進(jìn)行一次直接插入排序。希爾排序的具體步驟如下：,2024/3/16,24,（1）首先取一個(gè)整數(shù)d1<n，稱之為增量，將待排序的記錄分成d1個(gè)組，凡是距離為d1倍數(shù)的記錄都放在同一個(gè)組，在各組內(nèi)進(jìn)行直接插入排序，這樣的一次分組和排序過(guò)程稱為一趟希爾排序。（2）再設(shè)置另一個(gè)新的增量d2<d1，采用與上述相同的方法繼續(xù)進(jìn)行分組和排序過(guò)程。（3）繼續(xù)取di+1<di，重復(fù)步驟(2)，直到增量d=1，即所有記錄

29、都放在同一個(gè)組中。,【例8-3】設(shè)有一個(gè)待排序的序列有10個(gè)記錄，它們的關(guān)鍵字分別為58，46，72，95，84，25 ，37，58，63，12 ，用希爾排序法進(jìn)行排序?！窘狻繄D8-3給出了希爾排序的整個(gè)過(guò)程，用同一連線上的關(guān)鍵字表示其所屬的記錄在同一組。為區(qū)別具有相同關(guān)鍵字58的不同記錄，用下劃線標(biāo)記后一個(gè)記錄的關(guān)鍵字。,2024/3/16,25,圖8-3 希爾排序過(guò)程,2024/3/16,26,第一趟排序時(shí)，取d1=5，整個(gè)序列

30、被劃分成5組，分別為{58，25}，{46，37}，{72，58}，{95，63}，{84，12}。對(duì)各組內(nèi)的記錄進(jìn)行直接插入排序，得到第一趟排序結(jié)果如圖8-3(a)所示。第二趟排序時(shí)，取d2=3，將第一趟排序的結(jié)果分成3組，分別為{25，63，46，84},{37，12，72},{58，58，95}。再對(duì)各組內(nèi)記錄進(jìn)行直接插入排序，得到第二趟排序結(jié)果如圖8-3(b)所示。25 12 58 46 37

31、 58 63 72 95 84第三趟排序時(shí)，取d3=1，所有的數(shù)據(jù)記錄分成1組{25 ，12，58 ，46，37，58 ，63， 72， 95，84}，此時(shí)序列基本“有序”，對(duì)其進(jìn)行直接插入排序，最后得到希爾排序的結(jié)果如圖8-3(c )所示。12 25 37 46 58 58 63 72 86 95。,2024/3/16,27,希爾排序的算法如下：void She

32、ll_Sort(RecType R[],int n){ int i, j, d; RecType temp; d=n／2; //初始增量 while(d>0){　 //通過(guò)增量控制排序的執(zhí)行過(guò)程 for(i=d; i=0) if(R[j].key>R[j+d].key){ t

33、emp=R[j]; //R[j]與R[j+d]交換 R[j]=R[j+d];R[j+d]=temp;j=j-d; //j前移 } else j=-1; } d=d／2; //遞減增量d }},2024/3/16,28,從希爾排序過(guò)程可以看到： （1）

34、算法中約定初始增量d1為已知； （2）算法中采用簡(jiǎn)單的取增量值的方法，從第二次起取增量值為其前次增量值的一半。在實(shí)際應(yīng)用中，可能有多種取增量的方法，并且不同的取值方法對(duì)算法的時(shí)間性能有一定的影響，因而一種好的取增量的方法是改進(jìn)希爾排序算法時(shí)間性能的關(guān)鍵。 （3）希爾排序開(kāi)始時(shí)增量較大，分組較多，每組的記錄數(shù)較少，故各組內(nèi)直接插入過(guò)程較快。隨著每一趟中增量di逐漸縮小，分組數(shù)逐漸減少，雖各組的記錄數(shù)目逐漸增多，但由于已經(jīng)按di-1作為

35、增量排過(guò)序，使序列表較接近有序狀態(tài)，所以新的一趟排序過(guò)程也較快。因此，希爾排序在效率上較直接插入排序有較大的改進(jìn)。希爾排序的時(shí)間復(fù)雜度約為O(n1..3)，它實(shí)際所需的時(shí)間取決于各次排序時(shí)增量的取值。大量研究證明，若增量序列取值較合理，希爾排序時(shí)關(guān)鍵字比較次數(shù)和記錄移動(dòng)次數(shù)約為O(nlog2n)2。由于其時(shí)間復(fù)雜度分析較復(fù)雜，在此不做討論。 希爾排序會(huì)使關(guān)鍵字相同的記錄交換相對(duì)位置，所以希爾排序是不穩(wěn)定的。,2024/3/16,

36、29,8.3交換排序,利用交換記錄的位置進(jìn)行排序的方法稱為交換排序。其基本思想是：兩兩比較待排序記錄的關(guān)鍵字，如果逆序就進(jìn)行交換，直到所有記錄都排好序?yàn)橹埂３Ｓ玫慕粨Q排序方法主要有冒泡排序和快速排序。快速排序是一種分區(qū)交換排序法，是對(duì)冒泡排序方法的改進(jìn)。,2024/3/16,30,冒泡排序（Bubble sort）的算法思想是：設(shè)待排序有n個(gè)記錄，首先將第一個(gè)記錄的關(guān)鍵字R1.key和第二個(gè)記錄的關(guān)鍵字R2.key進(jìn)行比較，若R1.ke

37、y>R2.key，就交換記錄R1和R2在序列中的位置；然后繼續(xù)對(duì)R2.key和R3.key進(jìn)行比較，并作相同的處理；重復(fù)此過(guò)程，直到關(guān)鍵字Rn-1.key和Rn.key比較完成。其結(jié)果是n個(gè)記錄中關(guān)鍵字最大的記錄被交換到序列的最后一個(gè)記錄的位置上，即具有最大關(guān)鍵字的記錄被“沉”到了最后，這個(gè)過(guò)程被稱為一趟冒泡排序。然后進(jìn)行第二趟冒泡排序，對(duì)序列表中前n-1個(gè)記錄進(jìn)行同樣的操作，使序列表中關(guān)鍵字次大的記錄被交換到序列的n-1位置上；

38、第i趟冒泡排序是從R1到Rn-i+1依次比較相鄰兩個(gè)記錄的關(guān)鍵字，并在“逆序”時(shí)交換相鄰記錄，其結(jié)果是這n-i+1個(gè)記錄中關(guān),8.3.1 冒泡排序,2024/3/16,31,鍵字最大的記錄被交換到n-i+1位置上。每一趟排序都有一個(gè)相對(duì)大的數(shù)據(jù)被交換到后面，就像一塊塊“大”石頭不斷往下沉，最大的總是最早沉下；而具有較小關(guān)鍵字的記錄則不斷向上（前）移動(dòng)位置，就像水中的氣泡逐漸向上飄浮一樣，冒到最上面的是關(guān)鍵字值最小的記錄。所以把這種排序

39、方法稱為冒泡排序。對(duì)有n個(gè)記錄的序列最多做n-1趟冒泡就會(huì)把所有記錄依關(guān)鍵字大小排好序。如果在某一趟排序中都沒(méi)有發(fā)生相鄰記錄的交換，表示在該趟之前已達(dá)到排序的目的，整個(gè)排序過(guò)程可以結(jié)束。在操作實(shí)現(xiàn)時(shí)，常用一個(gè)標(biāo)志位flag標(biāo)示在第i趟是否發(fā)生了交換，若在第i趟發(fā)生過(guò)交換，則置flag=false（或0）；若第i趟沒(méi)有發(fā)生交換，則置flag=true（或1），表示在第i-1趟已經(jīng)達(dá)到排序目的，可結(jié)束整個(gè)排序過(guò)程。,2024/3/16,32

40、,算法描述如下：#define False 0#define True 1typedef int keytype;void Bubble_Sort(RecType R[],int n) //用冒泡排序?qū)[1]~R[n]記錄排序{ int i,j,flag=0;for(i=1; i<n; i++){ flag=1 ; //每趟比較前設(shè)置flag=1，假定該序

41、列已有序 for(j=1;j<=n-i;j++) if(R[j+1].key<R[j].key) { flag=0; //如果有逆序的則置flag=0 R[0]=R[j]; R[j]=R[j+1]; R[j+1]=R[0]; } if(flag==1) return; //flag

42、為True則表示序列已有序，可結(jié)束排序過(guò)程 }},2024/3/16,33,在該算法中，外層循環(huán)控制排序的執(zhí)行趟數(shù)，內(nèi)層循環(huán)用于控制在一趟冒泡排序中相鄰記錄間的比較和交換。,【例8-4】假設(shè)有8個(gè)記錄，關(guān)鍵字分別為53，38，47，24，69，05，17，38，用冒泡排序方法排序。,【解】冒泡排序過(guò)程如圖8-4所示。,2024/3/16,34,圖8-4 冒泡排序過(guò)程,2024/3/16,35,執(zhí)行了5趟冒泡排序后，完成了整個(gè)排序

43、過(guò)程。 排序中當(dāng)關(guān)鍵字間的比較呈逆序時(shí)，需要交換兩個(gè)記錄的位置，使用一個(gè)輔助空間來(lái)完成交換。在算法中用數(shù)組中的R[0]作為輔助空間，所以其空間復(fù)雜度為O(1)。,對(duì)于有n個(gè)記錄的待排序列進(jìn)行冒泡排序，算法的時(shí)間復(fù)雜度依賴于待排序序列的初始特性，有以下幾種情況： （1）如果初始記錄序列為“正序”序列，則只需進(jìn)行一趟排序，記錄移動(dòng)次數(shù)為0，關(guān)鍵字間比較次數(shù)為n-1；,2024/3/16,36,（2）如果初始記錄序列為“逆序”序

44、列，則進(jìn)行n-1趟排序，每一趟中的比較和交換次數(shù)將達(dá)到最大，即冒泡排序的最大比較次數(shù)為 =n(n-1)/2，最大移動(dòng)次數(shù)為3× =3n(n-1)/2。（3）一般情況下，比較次數(shù)≤n(n-1)/2，移動(dòng)次數(shù)≤3n (n-1)/2，因此時(shí)間復(fù)雜度為O(n2)。由相鄰兩個(gè)記錄的交換條件可知冒泡排序是穩(wěn)定排序。,2024/3/16,37,8.3.3 快速排序,快速排序（Quick Sorting）又稱分區(qū)交

45、換排序，是對(duì)冒泡排序算法的改進(jìn)，是一種基于分組進(jìn)行互換的排序方法。1．快速排序的基本思想 快速排序的基本思想是：從待排記錄序列中任取一個(gè)記錄Ri作為基準(zhǔn)（通常取序列中的第一個(gè)記錄），將所有記錄分成兩個(gè)序列分組，使排在Ri之前的序列分組的記錄關(guān)鍵字都小于等于基準(zhǔn)記錄的關(guān)鍵字值Ri.key，排在Ri之后的序列分組的記錄關(guān)鍵字都大于Ri.key，形成以Ri為分界的兩個(gè)分組，此時(shí)基準(zhǔn)記錄Ri的位置就是它的最終排序位置。此趟排序稱為第一

46、趟快速排序。然后分別對(duì)兩個(gè)序列分組重復(fù)上述過(guò)程，直到所有記錄排在相應(yīng)的位置上。,2024/3/16,38,2．選取基準(zhǔn)在快速排序中，選取基準(zhǔn)常用的方法有：（1）選取序列中第一個(gè)記錄的關(guān)鍵字值作為基準(zhǔn)關(guān)鍵字。這種選擇方法簡(jiǎn)單。但是當(dāng)序列中的記錄已基本有序時(shí)，這種選擇往往使兩個(gè)序列分組的長(zhǎng)度不均勻，不能改進(jìn)排序的時(shí)間性能。（2）選取序列中間位置記錄的關(guān)鍵字值作為基準(zhǔn)關(guān)鍵字。（3）比較序列中始端、終端及中間位置上記錄的關(guān)鍵字值，并取這

47、三個(gè)值中居中的一個(gè)作為基準(zhǔn)關(guān)鍵字。為了敘述方便，在下面的快速排序中，選取第一個(gè)記錄的關(guān)鍵字作為基準(zhǔn)關(guān)鍵字。,2024/3/16,39,3．快速排序的實(shí)現(xiàn) 算法中記錄的比較和交換是從待排記錄序列的兩端向中間進(jìn)行的。設(shè)置兩個(gè)變量i和j，其初值分別是n個(gè)待排序記錄中第一個(gè)記錄的位置號(hào)和最后一個(gè)記錄的位置號(hào)。在掃描過(guò)程中，變量i，j的值始終表示當(dāng)前所掃描分組序列的第一個(gè)和最后一個(gè)記錄的位置號(hào)。將第一個(gè)記錄R0作為基準(zhǔn)記錄放到一個(gè)臨時(shí)變

48、量temp中，將R0的位置空出。每趟快速排序，如下進(jìn)行： （1）從序列最后位置的記錄Rj開(kāi)始依次往前掃描，若存在temp≤Rj.key ，則令j前移一個(gè)位置，即j= j-1，如此直到temp＞Rj.key或i=j為止。若i＜j，則將記錄Rj放入Ri 空出的位置（由變量i指示的位置）。此時(shí)Rj位置空出（由變量j指示的位置）。,2024/3/16,40,（2）從序列最前位置的記錄Ri開(kāi)始依次往后掃描，若存在temp≥R[i].key，

49、則令i后移一個(gè)位置，即i= i+1，如此比較直到temp＜Ri.key或i=j為止。若i＜j，則將記錄Ri放入Rj 空出的位置（由變量j指示的位置）。此時(shí)Ri位置空出（用變量i指示的位置）。使j= j-1，繼續(xù)進(jìn)行步驟（1）的操作，即再?gòu)淖兞縥所指示的當(dāng)前位置依次向前比較交換。 在一趟快速排序中，整個(gè)過(guò)程交替地從后往前掃描關(guān)鍵字值小的記錄和從前往后掃描關(guān)鍵字值大的記錄并放置到對(duì)應(yīng)端空出的位置中，又空出新的位置。當(dāng)從兩個(gè)方向的掃描重合

50、時(shí)，即i=j，就找到了基準(zhǔn)記錄的存放位置。 按照快速排序的基本思想，在一趟快速排序之后，需要重復(fù)(1)，(2)，直到找到所有記錄的相應(yīng)位置。顯然，快速排序是一個(gè)遞歸的過(guò)程。,2024/3/16,41,,算法描述如下：void Quick_Sort(RecType R[],int left,int right){ //用遞歸方法把R[left]至R[righ]的記錄進(jìn)行快速排序 int i=left, j=right,

51、k;RecType temp;if(lefti && R[j].key>=temp.key) j--; //從右向左掃描，找第1個(gè)關(guān)鍵字小于temp.key的R[j] if (i<j) { //若找到這樣的R[j]，將R[j]存放到R[i]處 R[i]＝R[j]; i++; } while(i<j&&R[i

52、].key<=temp.key) i++; //從左向右掃描，找第1個(gè)關(guān)鍵字大于temp.key的R[i] if (i<j){ //找到則將R[i] 存放到 R[j] 處 R[j]=R[i]; j--; } } R[i]=temp; //將基準(zhǔn)放入其最終位置 Quick_Sort(R,left,i

53、-1); //對(duì)基準(zhǔn)前面的記錄序列進(jìn)行遞歸排序 Quick_Sort(R,i+l,right); //對(duì)基準(zhǔn)后面的記錄序列進(jìn)行遞歸排序｝,2024/3/16,42,【例8-5】假設(shè)有8個(gè)記錄，關(guān)鍵字的初始序列為｛45,34,67,95,78,12,26,45｝，用快速排序法進(jìn)行排序?！窘狻浚?）一趟快速排序過(guò)程如圖8-5所示：,圖8-5 一趟快速排序過(guò)程,2024/3/16,43,選取第一個(gè)記錄作為基準(zhǔn)記錄，存入臨

54、時(shí)單元temp中，騰出第一個(gè)位置（由i指示）。首先將temp中的45與Rj.key (45) 相比較，因temp≤Rj.key，j前移，即j= j-1；temp繼續(xù)與Rj.key (26) 比較，45>26，進(jìn)行第一次調(diào)整，將Rj.key (26) 放到Ri (i=1)處，Rj (j=7)位置空出；令i=i+1，然后進(jìn)行從前往后的比較；當(dāng)i=3時(shí)，temp＜Ri.key (67)，進(jìn)行第二次調(diào)整，將Ri.key (67) 放到Rj

55、 (j=7) 處，于是，Ri (i=3)位置空出；經(jīng)過(guò)i和j交替地從兩端向中間掃描以及記錄位置的調(diào)整，當(dāng)執(zhí)行到i=j=4 時(shí)，一趟排序成功，將temp保存的記錄放入該位置，這也是該記錄的最終排序位置。,2024/3/16,44,（2）各趟排序之后的結(jié)果,圖8-6 快速排序過(guò)程,2024/3/16,45,快速排序算法的執(zhí)行時(shí)間取決于基準(zhǔn)記錄的選擇。一趟快速排序算法的時(shí)間復(fù)雜度為O(n)。下面分幾種情況討論整個(gè)快速排序算法需要排序的趟數(shù)

56、： （1）在理想情況下，每次排序時(shí)所選取的記錄關(guān)鍵字值都是當(dāng)前待排序列中的“中值”記錄，那么該記錄的排序終止位置應(yīng)在該序列的中間，這樣就把原來(lái)的子序列分解成了兩個(gè)長(zhǎng)度大致相等的更小的子序列，在這種情況下，排序的速度最快。設(shè)完成n個(gè)記錄待排序列所需的比較次數(shù)為C(n),則有：C(n)≤n+2C(n/2)≤2n+4C(n/4)≤kn+nC(1)(k是序列的分解次數(shù)) 若n為2的冪次值且每次分解都是等長(zhǎng)的，則分解過(guò)程可用一棵滿二叉樹描

57、述，分解次數(shù)等于樹的深度k=log2n，因此有：C(n)≤nlog2n+nC(1)=O(nlog2n)整個(gè)算法的時(shí)間復(fù)雜度為O(nlog2n)。,2024/3/16,46,(2)在極端情況下，即每次選取的“基準(zhǔn)”都是當(dāng)前分組序列中關(guān)鍵字最小(或最大)的值，劃分的結(jié)果是基準(zhǔn)的前邊(或右邊)為空，即把原來(lái)的分組序列分解成一個(gè)空序列和一個(gè)長(zhǎng)度為原來(lái)序列長(zhǎng)度減1的子序列?？偟谋容^次數(shù)達(dá)到最大值：,如果初始記錄序列已為升序或降序排列，并且選取

58、的基準(zhǔn)記錄又是該序列中的最大或最小值，這時(shí)的快速排序就變成了“慢速排序”。整個(gè)算法的時(shí)間復(fù)雜度為O(n2)。為了避免這種情況的發(fā)生，可修改上面的排序算法，在每趟排序之前比較當(dāng)前序列的第一、最后和中間記錄的關(guān)鍵字，取關(guān)鍵字居中的一個(gè)記錄作為基準(zhǔn)值調(diào)換到第一個(gè)記錄的位置。,2024/3/16,47,(3)一般情況下，序列中各記錄關(guān)鍵字的分布是隨機(jī)的，因而可以認(rèn)為快速排序算法的平均時(shí)間復(fù)雜度為O(nlog2n)。實(shí)驗(yàn)證明，當(dāng)n較大時(shí)，快速排序

59、是目前被認(rèn)為最好的一種內(nèi)部排序方法。 在算法實(shí)現(xiàn)中需設(shè)置一個(gè)棧的存貯空間來(lái)實(shí)現(xiàn)遞歸，棧的大小取決于遞歸深度，最多不會(huì)超過(guò)n。若每次都選較長(zhǎng)的分組序列進(jìn)棧，而處理較短的分組序列，則遞歸深度最多不會(huì)超過(guò)log2n，因此快速排序需要的輔助存貯空間為O(log2n)。 快速排序算法是不穩(wěn)定排序，對(duì)于有相同關(guān)鍵字的記錄，排序后有可能顛倒位置。,2024/3/16,48,8.4選擇排序,選擇排序（Selection Sort）的基本

60、思想是：不斷從待排記錄序列中選出關(guān)鍵字最小的記錄插入已排序記錄序列的后面，直到n個(gè)記錄全部插入已排序記錄序列中。本節(jié)主要介紹兩種選擇排序方法：簡(jiǎn)單選擇排序和堆排序。,8.4.1 簡(jiǎn)單選擇排序,簡(jiǎn)單選擇排序(Simple Selection Sort)也稱直接選擇排序，是選擇排序中最簡(jiǎn)單直觀的一種方法。其基本操作思想：,(1)每次從待排記錄序列中選出關(guān)鍵字最小的記錄； (2)將它與待排記錄序列第一位置的記錄交換后，再將其“插入”已排序記

61、錄序列(初始為空)；,2024/3/16,49,(3)不斷重復(fù)過(guò)程(1)和(2)，就不斷地從待排記錄序列中剩下的(n-1，n-2，…2)個(gè)記錄中選出關(guān)鍵字最小的記錄與該區(qū)第1位置的記錄交換(該區(qū)第1個(gè)位置不斷后移，該區(qū)記錄逐漸減少)，然后把第1位置的記錄不斷 “插入” 已排序記錄序列之后。經(jīng)過(guò)n-1次的選擇和多次交換后，R1 ~ Rn就排成了有序序列，整個(gè)排序過(guò)程結(jié)束。具有n個(gè)記錄的待排記錄序列要做n-1次的選擇和交換才能成為有序表。,

62、簡(jiǎn)單選擇排序算法描述如下：,2024/3/16,50,void Select_Sort(RecType R[],int n){ int i,j,k; RecType temp; for(i=1;i<n;i++) //進(jìn)行n-1趟排序，每趟選出1個(gè)最小記錄 { k=i; //假定起始位置為最小記錄的位置 for(j=i+1;j<=n;j++) //

63、查找最小記錄 if(R[j].key<R[k].key) k=j; if(i!=k) //如果k不是假定位置，則交換 { temp=R[k]; //交換記錄 R[k]=R[i]; R[i]=temp; } }},本算法中有兩重循環(huán)：外循環(huán)用于控制排序的次數(shù)，

64、內(nèi)循環(huán)用于查找當(dāng)前待排記錄序列中關(guān)鍵字最小的記錄。,2024/3/16,51,【例8-6】采用簡(jiǎn)單選擇排序?qū)σ韵?個(gè)記錄進(jìn)行排序【解】圖8-7是簡(jiǎn)單選擇排序的過(guò)程示意圖。圖中 [ ] 中的數(shù)據(jù)表示待排記錄序列的關(guān)鍵字。,圖8-7 簡(jiǎn)單選擇排序示例,2024/3/16,52,簡(jiǎn)單選擇排序算法的關(guān)鍵字比較次數(shù)與記錄的初始排列無(wú)關(guān)。假定整個(gè)序列表有n個(gè)記錄，總共需要n-1趟的選擇；第i (i=1，2，…，n-1) 趟選擇具有最小關(guān)鍵字

65、記錄所需要的比較次數(shù)是n-i-1次，總的關(guān)鍵字比較次數(shù)為： 比較次數(shù)=(n-1)+(n-2)+…+1=n(n-1)/2 而記錄的移動(dòng)次數(shù)與其初始排列有關(guān)。當(dāng)這組記錄的初始狀態(tài)是按關(guān)鍵字從小到大有序時(shí)，每一趟選擇后都不需要進(jìn)行交換，記錄的總移動(dòng)次數(shù)為0，這是最好的情況；而最壞的情況是每一趟選擇后都要進(jìn)行交換，一趟交換需要移動(dòng)記錄3次?？偟挠涗浺苿?dòng)次數(shù)為3(n-1)。所以，簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度為O(n2)。 簡(jiǎn)單

66、選擇排序算法只需要一個(gè)臨時(shí)單元用作交換，因此空間復(fù)雜度為O(1)。 由于在直接選擇排序過(guò)程中存在不相鄰記錄之間的互換，可能會(huì)改變具有相同關(guān)鍵字記錄的相對(duì)位置，所以該算法是不穩(wěn)定排序。,2024/3/16,53,8.4.2 堆排序,堆排序(Heap Sort)借助于完全二叉樹結(jié)構(gòu)進(jìn)行排序，是一種樹型選擇排序。 在直接選擇排序時(shí)，為從n個(gè)關(guān)鍵字中選出最小值，需要進(jìn)行n-1次比較，，然后又在剩下的n-1個(gè)關(guān)鍵字中選出次最小值，需要

67、n-2次比較。在n-2次的比較中可能有許多比較在前面的n-1次比較中已經(jīng)做過(guò)，因此存在多次重復(fù)比較，降低了算法的效率。堆排序方法是由J. Williams和Floyd提出的一種改進(jìn)方法，它在選擇當(dāng)前最小關(guān)鍵字記錄的同時(shí)，還保存了本次排序過(guò)程所產(chǎn)生的比較信息。,2024/3/16,54,n個(gè)元素序列{k1，k2，…，kn }，當(dāng)且僅當(dāng)滿足如下性質(zhì)稱為堆。(1)這些元素是一棵完全二叉樹中的結(jié)點(diǎn)，且對(duì)于i=1， 2，…, n， ki是該完全

68、二叉樹中編號(hào)為i的結(jié)點(diǎn)； (2) ki≤k2i （或ki≥k2i ） (1≤i≤?n /2? ) (3) ki≤k2i+1(或 ki≥k2i+l ) (1≤i≤?n /2? )從堆的定義可以看出，堆是一棵完全二叉樹，其中每一個(gè)非終端結(jié)點(diǎn)的元素均大于等于（或小于等于）其左、右孩子結(jié)點(diǎn)的元素值。圖8-8(a) 和 圖8-8 (b)為堆的兩個(gè)示例，所對(duì)應(yīng)的元素序列分別為｛92,84,25,