1、第8章 排序技術(shù),本章的基本內(nèi)容是： 排序的基本概念 插入排序 交換排序(起泡、快速) 選擇排序(簡單選擇、堆) 歸并排序 分配排序 各種排序算法的比較,8.1 概 述,排序：給定一組記錄的集合r1, r2, , rn，其相應(yīng)的關(guān)鍵碼分別為k1, k2, , kn，排序是將這些記錄排列成順序?yàn)閞s1, rs2, , rsn的一個(gè)序列，使得相應(yīng)的關(guān)鍵碼滿足ks1ks2ksn（稱為升序）或ks1ks2ksn（稱為降序）。 正序：待排序序列中的記錄已按關(guān)鍵碼排好序。 逆序（反序）：待排序序列中記錄的排列順序與排好序的順序正好相反。,排序的基本概念,從操作角度看，排序是線性結(jié)構(gòu)的一種操作,排序算法的穩(wěn)

2、定性：假定在待排序的記錄集中，存在多個(gè)具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對次序仍然保持不變，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。,排序的基本概念,8.1 概 述,排序的基本概念,單鍵排序：根據(jù)一個(gè)關(guān)鍵碼進(jìn)行的排序； 多鍵排序：根據(jù)多個(gè)關(guān)鍵碼進(jìn)行的排序。,按學(xué)號排序單鍵排序 按成績（高數(shù)英語思想品德）排序多鍵排序,8.1 概 述,排序的基本概念,設(shè)關(guān)鍵碼分別為k1, k2, , km，多鍵排序有兩種方法： 依次對記錄進(jìn)行m次排序，第一次按k1排序，第二次按k2排序，依此類推。這種方法要求各趟排序所用

3、的算法是穩(wěn)定的； 將關(guān)鍵碼k1, k2, , km分別視為字符串依次首尾連接在一起，形成一個(gè)新的字符串，然后，對記錄序列按新形成的字符串排序。,8.1 概 述,排序的分類 1. 內(nèi)排序：在排序的整個(gè)過程中，待排序的所有記錄全部被放置在內(nèi)存中 2. 外排序：由于待排序的記錄個(gè)數(shù)太多，不能同時(shí)放置在內(nèi)存，而需要將一部分記錄放置在內(nèi)存，另一部分記錄放置在外存上，整個(gè)排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能得到排序的結(jié)果。,排序的基本概念,8.1 概 述,排序的分類 1. 基于比較：基本操作關(guān)鍵碼的比較和記錄的移動(dòng)，其最差時(shí)間下限已經(jīng)被證明為（nlog2n）。 （1）插入排序 （2）交換排序 （3）選

4、擇排序 （4）歸并排序 2. 不基于比較：根據(jù)關(guān)鍵碼的分布特征。,排序的基本概念,8.1 概 述,1. 基本操作。內(nèi)排序在排序過程中的基本操作： 比較：關(guān)鍵碼之間的比較； 移動(dòng)：記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。 2. 輔助存儲(chǔ)空間。 輔助存儲(chǔ)空間是指在數(shù)據(jù)規(guī)模一定的條件下，除了存放待排序記錄占用的存儲(chǔ)空間之外，執(zhí)行算法所需要的其他存儲(chǔ)空間。 3. 算法本身的復(fù)雜程度。,排序算法的性能,8.1 概 述,排序算法的存儲(chǔ)結(jié)構(gòu),從操作角度看，排序是線性結(jié)構(gòu)的一種操作，待排序記錄可以用順序存儲(chǔ)結(jié)構(gòu)或鏈接存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。,假定2：將待排序的記錄序列排序?yàn)樯蛐蛄小?int rn+1; /待排序記錄存儲(chǔ)在r1

5、rn，r0留做他用,假定1：采用順序存儲(chǔ)結(jié)構(gòu)，關(guān)鍵碼為整型，且記錄只有關(guān)鍵碼一個(gè)數(shù)據(jù)項(xiàng)。,8.1 概 述,8.2 插入排序,插入排序的主要操作是插入，其基本思想是：每次將一個(gè)待排序的記錄按其關(guān)鍵碼的大小插入到一個(gè)已經(jīng)排好序的有序序列中，直到全部記錄排好序?yàn)橹埂?基本思想：在插入第 i（i1）個(gè)記錄時(shí)，前面的 i-1個(gè)記錄已經(jīng)排好序。,直接插入排序,8.2 插入排序,基本思想：在插入第 i（i1）個(gè)記錄時(shí)，前面的 i-1個(gè)記錄已經(jīng)排好序。,（1）如何構(gòu)造初始的有序序列？ （2）如何查找待插入記錄的插入位置?,直接插入排序,需解決的關(guān)鍵問題?,8.2 插入排序,直接插入排序過程示例,r 0 1 2

6、 3 4 5 6,21,18,25,22,10,25*,21,22,10,25,18,18,r0的作用?,暫存單元,監(jiān)視哨,8.2 插入排序,解決方法： 將第1個(gè)記錄看成是初始有序表，然后從第2個(gè)記錄起依次插入到這個(gè)有序表中，直到將第n個(gè)記錄插入。,關(guān)鍵問題(1)如何構(gòu)造初始的有序序列？,算法描述： for (i=2; i=n; i+) 插入第i個(gè)記錄，即第i趟直接插入排序； ,8.2 插入排序,關(guān)鍵問題(2)如何查找待插入記錄的插入位置?,解決方法： 在i-1個(gè)記錄的有序區(qū)r1 ri-1中插入記錄ri，首先順序查找ri的正確插入位置，然后將ri插入到相應(yīng)位置。,r0有兩個(gè)作用： 1. 進(jìn)入循

7、環(huán)之前暫存了ri的值，使得不致于因記錄的后移而丟失ri的內(nèi)容； 2. 在查找插入位置的循環(huán)中充當(dāng)哨兵。,算法描述： r0=ri; j=i-1; while (r0rj) rj+1=rj; j-; ,8.2 插入排序,void insertSort (int r , int n) for (i=2; i=n; i+) r0=ri; j=i-1; while (r0rj) rj+1=rj; j=j-1; rj+1=r0; ,直接插入排序算法,8.2 插入排序,直接插入排序算法性能分析,最好情況下（正序）：,時(shí)間復(fù)雜度為O(n)。,8.2 插入排序,直接插入排序算法性能分析,最好情況下（正序）：,最

8、壞情況下（逆序或反序）：,時(shí)間復(fù)雜度為O(n2)。,時(shí)間復(fù)雜度為O(n)。,8.2 插入排序,平均情況下（隨機(jī)排列）：,直接插入排序算法性能分析,時(shí)間復(fù)雜度為O(n2)。,8.2 插入排序,空間性能：需要一個(gè)記錄的輔助空間。 直接插入排序算法是一種穩(wěn)定的排序算法。,直接插入排序算法性能分析,直接插入排序算法簡單、容易實(shí)現(xiàn)，適用于待排序記錄基本有序或待排序記錄較小時(shí)。 當(dāng)待排序的記錄個(gè)數(shù)較多時(shí)，大量的比較和移動(dòng)操作使直接插入排序算法的效率降低。,8.2 插入排序,如何改進(jìn)直接插入排序?,注意到，在插入第 i（i1）個(gè)記錄時(shí)，前面的 i-1 個(gè)記錄已經(jīng)排好序，則在尋找插入位置時(shí)，可以用折半查找來代

9、替順序查找，從而減少比較次數(shù)。,請同學(xué)們寫出這個(gè)改進(jìn)的直接插入排序算法，并分析時(shí)間性能。,8.2 插入排序,希爾排序,改進(jìn)的著眼點(diǎn)： （1）若待排序記錄按關(guān)鍵碼基本有序時(shí)，直接插入排序的效率可以大大提高； （2）由于直接插入排序算法簡單，則在待排序記錄數(shù)量n較小時(shí)效率也很高。,8.2 插入排序,（1）應(yīng)如何分割待排序記錄，才能保證整個(gè)序列逐步向基本有序發(fā)展？ （2）子序列內(nèi)如何進(jìn)行直接插入排序？,需解決的關(guān)鍵問題?,基本思想：將整個(gè)待排序記錄分割成若干個(gè)子序列，在子序列內(nèi)分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本有序時(shí)，對全體記錄進(jìn)行直接插入排序。,希爾排序,8.2 插入排序,基本有序：接近

10、正序，例如1, 2, 8, 4, 5, 6, 7, 3, 9； 局部有序：部分有序，例如6, 7, 8, 9, 1, 2, 3, 4, 5。 局部有序不能提高直接插入排序算法的時(shí)間性能。,希爾排序,分割待排序記錄的目的?,1. 減少待排序記錄個(gè)數(shù)； 2. 使整個(gè)序列向基本有序發(fā)展。,子序列的構(gòu)成不能是簡單地“逐段分割”，而是將相距某個(gè)“增量”的記錄組成一個(gè)子序列。,啟示?,8.2 插入排序,希爾插入排序過程示例,1 2 3 4 5 6 7 8 9,40,21,25,49,25*,16,初始序列,30,08,13,8.2 插入排序,解決方法： 將相隔某個(gè)“增量”的記錄組成一個(gè)子序列。 增量應(yīng)如何

11、?。?希爾最早提出的方法是d1=n/2，di+1=di/2。,關(guān)鍵問題(1)應(yīng)如何分割待排序記錄？,算法描述： for (d=n/2; d=1; d=d/2) 以d為增量，進(jìn)行組內(nèi)直接插入排序； ,8.2 插入排序,解決方法： 在插入記錄ri時(shí)，自ri-d起往前跳躍式（跳躍幅度為d）搜索待插入位置，并且r0只是暫存單元，不是哨兵。當(dāng)搜索位置0，表示插入位置已找到。 在搜索過程中，記錄后移也是跳躍d個(gè)位置。 在整個(gè)序列中，前d個(gè)記錄分別是d個(gè)子序列中的第一個(gè)記錄，所以從第d+1個(gè)記錄開始進(jìn)行插入。,關(guān)鍵問題(2)子序列內(nèi)如何進(jìn)行直接插入排序？,8.2 插入排序,希爾插入排序過程示例,1 2 3

12、4 5 6 7 8 9,40,21,25,49,25*,16,初始序列,30,08,13,16,40,16,8.2 插入排序,希爾插入排序過程示例,1 2 3 4 5 6 7 8 9,40,21,25,49,25*,16,初始序列,30,08,13,25,21,16,40,21,8.2 插入排序,希爾插入排序過程示例,1 2 3 4 5 6 7 8 9,40,21,25,49,25*,16,初始序列,30,08,13,25,21,16,40,49,08,08,8.2 插入排序,希爾插入排序過程示例,1 2 3 4 5 6 7 8 9,40,21,25,49,25*,16,初始序列,30,08,

13、13,25,21,16,40,49,08,25*,30,30,8.2 插入排序,希爾插入排序過程示例,1 2 3 4 5 6 7 8 9,40,21,25,49,25*,16,初始序列,30,08,13,25,21,16,40,49,08,25*,30,40,13,16,13,8.2 插入排序,算法描述：,for (i=d+1; i0 ,關(guān)鍵問題(2)子序列內(nèi)如何進(jìn)行直接插入排序？,8.2 插入排序,希爾排序算法的時(shí)間性能,希爾排序算法的時(shí)間性能是所取增量的函數(shù)，而到目前為止尚未有人求得一種最好的增量序列。 研究表明，希爾排序的時(shí)間性能在O(n2)和O(nlog2n)之間。當(dāng)n在某個(gè)特定范圍內(nèi)

14、，希爾排序所需的比較次數(shù)和記錄的移動(dòng)次數(shù)約為O(n1.3 ) 。,希爾排序開始時(shí)增量較大，每個(gè)子序列中的記錄個(gè)數(shù)較少，從而排序速度較快；當(dāng)增量較小時(shí)，雖然每個(gè)子序列中記錄個(gè)數(shù)較多，但整個(gè)序列已基本有序，排序速度也較快縮小增量。,8.2 插入排序,交換排序的主要操作是交換，其主要思想是：在待排序列中選兩個(gè)記錄，將它們的關(guān)鍵碼相比較，如果反序（即排列順序與排序后的次序正好相反），則交換它們的存儲(chǔ)位置。,8.3 交換排序,反序則 交換,起泡排序,基本思想：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。,8.3 交換排序,05,98,12,69,38,53,81,起泡排序過程示例,

15、8.3 交換排序, 在一趟起泡排序中，若有多個(gè)記錄位于最終位置，應(yīng)如何記載？ 如何確定起泡排序的范圍，使得已經(jīng)位于最終位置的記錄不參與下一趟排序？ 如何判別起泡排序的結(jié)束？,需解決的關(guān)鍵問題?,起泡排序,8.3 交換排序,解決方法： 設(shè)變量exchange記載記錄交換的位置，則一趟排序后，exchange記載的一定是這一趟排序中記錄的最后一次交換的位置，且從此位置以后的所有記錄均已經(jīng)有序。,關(guān)鍵問題：如何記載一趟排序過程中交換的多個(gè)記錄？,8.3 交換排序,關(guān)鍵問題：如何記載一趟排序過程中交換的多個(gè)記錄？,算法描述： if （rjrj+1） rjrj+1； exchange=j； ,解決方法：

16、 設(shè)變量exchange記載記錄交換的位置，則一趟排序后，exchange記載的一定是這一趟排序中記錄的最后一次交換的位置，且從此位置以后的所有記錄均已經(jīng)有序。,8.3 交換排序,解決方法： 設(shè)bound位置的記錄是無序區(qū)的最后一個(gè)記錄，則每趟起泡排序的范圍是r1 rbound。 在一趟排序后，從exchange位置之后的記錄一定是有序的，所以bound=exchange。,關(guān)鍵問題：如何確定起泡排序的范圍？,8.3 交換排序,解決方法： 設(shè)bound位置的記錄是無序區(qū)的最后一個(gè)記錄，則每趟起泡排序的范圍是r1 rbound。 在一趟排序后，從exchange位置之后的記錄一定是有序的，所以b

17、ound=exchange。,關(guān)鍵問題：如何確定起泡排序的范圍？,算法描述： bound=exchange; for (j=1; jrj+1） rjrj+1； exchange=j； ,8.3 交換排序,解決方法： 在每一趟起泡排序之前，令exchange的初值為0，在以后的排序過程中，只要有記錄交換，exchange的值就會(huì)大于0。這樣，在一趟比較完畢，就可以通過exchange的值是否為0來判別是否有記錄交換，從而判別整個(gè)起泡排序的結(jié)束。,關(guān)鍵問題：如何判別起泡排序的結(jié)束？,8.3 交換排序,解決方法： 在每一趟起泡排序之前，令exchange的初值為0，在以后的排序過程中，只要有記錄交換

18、，exchange的值就會(huì)大于0。這樣，在一趟比較完畢，就可以通過exchange的值是否為0來判別是否有記錄交換，從而判別整個(gè)起泡排序的結(jié)束。,關(guān)鍵問題：如何判別起泡排序的結(jié)束？,算法描述： while (exchange) 執(zhí)行一趟起泡排序； ,8.3 交換排序,void BubbleSort(int r , int n) exchange=n; while (exchange) bound=exchange; exchange=0； for (j=1; jrj+1) rjrj+1； exchange=j； ,起泡排序算法,8.3 交換排序,起泡排序的時(shí)間性能分析,最好情況（正序）：,時(shí)間

19、復(fù)雜度為O(n)。,8.3 交換排序,最壞情況（反序）：,起泡排序的時(shí)間性能分析,最好情況（正序）：,時(shí)間復(fù)雜度為O(n)；,時(shí)間復(fù)雜度為O(n2)。,平均情況：時(shí)間復(fù)雜度為O(n2)。,8.3 交換排序,快速排序,改進(jìn)的著眼點(diǎn)：在起泡排序中，記錄的比較和移動(dòng)是在相鄰單元中進(jìn)行的，記錄每次交換只能上移或下移一個(gè)單元，因而總的比較次數(shù)和移動(dòng)次數(shù)較多。,減少總的比較次數(shù)和移動(dòng)次數(shù),增大記錄的比較和移動(dòng)距離,較大記錄從前面直接移動(dòng)到后面 較小記錄從后面直接移動(dòng)到前面,8.3 交換排序,快速排序的基本思想,首先選一個(gè)軸值（即比較的基準(zhǔn)），通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，前一部分記錄的關(guān)鍵碼

20、均小于或等于軸值，后一部分記錄的關(guān)鍵碼均大于或等于軸值，然后分別對這兩部分重復(fù)上述方法，直到整個(gè)序列有序。,如何選擇軸值？ 如何實(shí)現(xiàn)分割（稱一次劃分）？ 如何處理分割得到的兩個(gè)待排序子序列？ 如何判別快速排序的結(jié)束？,需解決的關(guān)鍵問題?,8.3 交換排序,選擇軸值的方法： 1.使用第一個(gè)記錄的關(guān)鍵碼； 2.選取序列中間記錄的關(guān)鍵碼； 3.比較序列中第一個(gè)記錄、最后一個(gè)記錄和中間記錄的關(guān)鍵碼，取關(guān)鍵碼居中的作為軸值并調(diào)換到第一個(gè)記錄的位置； 4.隨機(jī)選取軸值。,關(guān)鍵問題：如何選擇軸值？,選取不同軸值的后果： 決定兩個(gè)子序列的長度，子序列的長度最好相等。,8.3 交換排序,13,65,27,50,

21、38,49,55,關(guān)鍵問題：如何實(shí)現(xiàn)一次劃分？,8.3 交換排序,解決方法： 設(shè)待劃分的序列是rs rt，設(shè)參數(shù)i，j分別指向子序列左、右兩端的下標(biāo)s和t，令rs為軸值， （1）j從后向前掃描，直到rjri，將rj移動(dòng)到ri的位置，使關(guān)鍵碼?。ㄍS值相比）的記錄移動(dòng)到前面去； （2）i從前向后掃描，直到rirj，將ri移動(dòng)到rj的位置，使關(guān)鍵碼大（同軸值比較）的記錄移動(dòng)到后面去； （3）重復(fù)上述過程，直到i=j。,關(guān)鍵問題：如何實(shí)現(xiàn)一次劃分？,8.3 交換排序,關(guān)鍵問題：如何實(shí)現(xiàn)一次劃分？,算法描述：,int Partition(int r , int first, int end) i=fi

22、rst; j=end; /初始化 while (ij) while (ij /i為軸值記錄的最終位置 ,8.3 交換排序,解決方法： 對分割得到的兩個(gè)子序列遞歸地執(zhí)行快速排序。,關(guān)鍵問題：如何處理分割得到的兩個(gè)待排序子序列？,38,8.3 交換排序,算法描述：,關(guān)鍵問題：如何處理分割得到的兩個(gè)待排序子序列？,void QuickSort (int r , int first, int end ) pivotpos = Partition (r, first, end ); /一次劃分 QuickSort (r, first, pivotpos-1); /對前一個(gè)子序列進(jìn)行快速排序 QuickS

23、ort (r, pivotpos+1, end ); /對后一個(gè)子序列進(jìn)行快速排序 ,8.3 交換排序,解決方法： 若待排序列中只有一個(gè)記錄，顯然已有序，否則進(jìn)行一次劃分后，再分別對分割所得的兩個(gè)子序列進(jìn)行快速排序（即遞歸處理）。,關(guān)鍵問題：如何判別快速排序的結(jié)束？,8.3 交換排序,void QuickSort (int r , int first, int end ) /在序列 firstend中遞歸地進(jìn)行快速排序 if (first end) pivotpos = Partition (r, first, end ); QuickSort (r, first, pivotpos-1);

24、QuickSort (r, pivotpos+1, end ); ,算法描述：,關(guān)鍵問題：如何判別快速排序的結(jié)束？,8.3 交換排序,例：38, 27, 55, 50, 13, 49, 65的快速排序遞歸樹如下：,快速排序的遞歸執(zhí)行過程可以用遞歸樹描述。,快速排序的時(shí)間性能分析,8.3 交換排序,快速排序的時(shí)間性能分析,快速排序的時(shí)間性能,快速排序遞歸的深度,每次劃分軸值的選取,8.3 交換排序,最好情況： 每一次劃分對一個(gè)記錄定位后，該記錄的左側(cè)子表與右側(cè)子表的長度相同，為O(nlog2n)。,快速排序的時(shí)間性能分析,T(n)2T(n/2)n 2(2T(n/4)n/2)n4T(n/4)2n

25、4(2T(n/8)n/4)2n8T(n/8)3n nT(1)nlog2nO(nlog2n),8.3 交換排序,最壞情況： 每次劃分只得到一個(gè)比上一次劃分少一個(gè)記錄的子序列（另一個(gè)子序列為空），為 O(n2)。,最好情況： 每一次劃分對一個(gè)記錄定位后，該記錄的左側(cè)子表與右側(cè)子表的長度相同，為O(nlog2n)。,快速排序的時(shí)間性能分析,平均情況：為O(nlog2n)。,8.3 交換排序,選擇排序的主要操作是選擇，其主要思想是：每趟排序在當(dāng)前待排序序列中選出關(guān)鍵碼最小的記錄，添加到有序序列中。,8.4 選擇排序,簡單選擇排序,基本思想：第i 趟在n-i+1（i=1,2,n-1）個(gè)記錄中選取關(guān)鍵碼最

26、小的記錄作為有序序列中的第i個(gè)記錄。,需解決的關(guān)鍵問題?,如何在待排序序列中選出關(guān)鍵碼最小的記錄？ 如何確定待排序序列中關(guān)鍵碼最小的記錄在有序序列中的位置？,8.4 選擇排序,簡單選擇排序示例,i = 2,最小者 08 交換21,08,最小者 16 交換25,16,最小者 21 交換49,21,21,28,i = 1,25,16,49,08,08,i = 3,21,16,8.4 選擇排序,i = 4,最小者 25 交換25,28,i = 5,最小者 28 不交換,簡單選擇排序示例,25,28,無序區(qū)只有 一個(gè)記錄,8.4 選擇排序,解決方法： 設(shè)置一個(gè)整型變量index，用于記錄在一趟比較的過

27、程中關(guān)鍵碼最小的記錄位置。,關(guān)鍵問題：如何在無序區(qū)中選出關(guān)鍵碼最小的記錄？,21,28,25,16,49,08,index,index,08,8.4 選擇排序,算法描述： index=i; for (j=i+1; j=n; j+) if (rjrindex) index=j;,解決方法： 設(shè)置一個(gè)整型變量index，用于記錄在一趟比較的過程中關(guān)鍵碼最小的記錄位置。,關(guān)鍵問題：如何在無序區(qū)中選出關(guān)鍵碼最小的記錄？,8.4 選擇排序,解決方法： 第i趟簡單選擇排序的待排序區(qū)間是ri rn，則ri是無序區(qū)第一個(gè)記錄，所以，將index所記載的關(guān)鍵碼最小的記錄與ri交換。,關(guān)鍵問題：如何確定最小記錄的

28、最終位置？,算法描述： if (index!=i) ririndex;,8.4 選擇排序,void selectSort ( int r , int n) for ( i=1; in; i+) index=i; for (j=i+1; j=n; j+) if (rjrindex) index=j; if (index!=i) ri rindex; ,簡單選擇排序算法,8.4 選擇排序,簡單選擇排序算法的性能分析,移動(dòng)次數(shù)： 最好情況（正序）：0次,1,2,3,4,8.4 選擇排序,最壞情況：3(n-1)次,簡單選擇排序算法的性能分析,移動(dòng)次數(shù)： 最好情況（正序）：0次,空間性能：需一個(gè)輔助空間

29、。 穩(wěn)定性：是一種穩(wěn)定的排序算法。,1,2,3,4,比較次數(shù)：,簡單選擇排序的時(shí)間復(fù)雜度為O(n2)。,8.4 選擇排序,堆排序,改進(jìn)的著眼點(diǎn)：如何減少關(guān)鍵碼間的比較次數(shù)。若能利用每趟比較后的結(jié)果，也就是在找出鍵值最小記錄的同時(shí)，也找出鍵值較小的記錄，則可減少后面的選擇中所用的比較次數(shù)，從而提高整個(gè)排序過程的效率。,減少關(guān)鍵碼間的比較次數(shù),查找最小值的同時(shí)，找出較小值,8.4 選擇排序,堆的定義,堆是具有下列性質(zhì)的完全二叉樹：每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（稱為小根堆），或每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（稱為大根堆）。,1. 小根堆的根結(jié)點(diǎn)是所有結(jié)點(diǎn)的最小者。 2. 較

30、小結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕對。,8.4 選擇排序,堆的定義,堆是具有下列性質(zhì)的完全二叉樹：每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（稱為小根堆），或每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（稱為大根堆）。,1. 大根堆的根結(jié)點(diǎn)是所有結(jié)點(diǎn)的最大者。 2. 較大結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕對。,8.4 選擇排序,堆和序列的關(guān)系,將堆用順序存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)，則堆對應(yīng)一組序列。,8.4 選擇排序,基本思想：首先將待排序的記錄序列構(gòu)造成一個(gè)堆，此時(shí)，選出了堆中所有記錄的最大者，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次小的記錄，以此類推，直到堆中只有一個(gè)記錄。,堆排序,需解決的關(guān)鍵問題?,如

31、何由一個(gè)無序序列建成一個(gè)堆（即初始建堆）？ 如何處理堆頂記錄？ 如何調(diào)整剩余記錄，成為一個(gè)新堆（即重建堆）？,8.4 選擇排序,堆調(diào)整,堆調(diào)整：在一棵完全二叉樹中，根結(jié)點(diǎn)的左右子樹均是堆，如何調(diào)整根結(jié)點(diǎn)，使整個(gè)完全二叉樹成為一個(gè)堆？,8.4 選擇排序,void sift ( int r , int k, int m ) /要篩選結(jié)點(diǎn)的編號為k，堆中最后一個(gè)結(jié)點(diǎn)的編號為m i=k; j=2*i; while (jrj) break; else ri rj; i=j; j=2*i; ,堆調(diào)整算法描述：,8.4 選擇排序,關(guān)鍵問題：如何由一個(gè)無序序列建成一個(gè)堆？,8.4 選擇排序,算法描述： for

32、 (i=n/2; i=1; i-) sift(r, i, n) ;,關(guān)鍵問題：如何由一個(gè)無序序列建成一個(gè)堆？,最后一個(gè)結(jié)點(diǎn)（葉子）的序號是n，則最后一個(gè)分支結(jié)點(diǎn)即為結(jié)點(diǎn)n的雙親，其序號是n/2。,8.4 選擇排序,關(guān)鍵問題：如何處理堆頂記錄？,對 應(yīng),對 應(yīng),8.4 選擇排序,算法描述： r1rn-i+1;,關(guān)鍵問題：如何處理堆頂記錄？,解決方法： 第 i 次處理堆頂是將堆頂記錄r1與序列中第n-i+1個(gè)記錄rn-i+1交換。,8.4 選擇排序,關(guān)鍵問題：如何調(diào)整剩余記錄，成為一個(gè)新堆？,8.4 選擇排序,解決方法： 第 i 次調(diào)整剩余記錄，此時(shí)，剩余記錄有n-i個(gè)，調(diào)整根結(jié)點(diǎn)至第n-i個(gè)記錄

33、。,關(guān)鍵問題：如何調(diào)整剩余記錄，成為一個(gè)新堆？,算法描述： sift(r, 1, n-i);,8.4 選擇排序,堆排序算法,void HeapSort ( int r, int n) for (i=n/2; i=1; i-) /初建堆 sift(r, i, n) ; for (i=1; in; i+ ) r1rn-i+1; /移走堆頂 sift(r, 1, n-i); /重建堆 ,8.4 選擇排序,堆排序算法的性能分析,第1個(gè)for循環(huán)是初始建堆，需要O(n)時(shí)間； 第2個(gè)for循環(huán)是輸出堆頂重建堆，共需要取n-1次堆頂記錄，第 i 次取堆頂記錄重建堆需要O(log2i)時(shí)間，需要O(nlog

34、2n)時(shí)間； 因此整個(gè)時(shí)間復(fù)雜度為O(nlog2n)，這是堆排序的最好、最壞和平均的時(shí)間代價(jià)。,8.4 選擇排序,歸并排序,歸并排序的主要操作是歸并，其主要思想是：將若干有序序列逐步歸并，最終得到一個(gè)有序序列。,8.5 歸并排序,歸并：將兩個(gè)或兩個(gè)以上的有序序列合并成一個(gè)有序序列的過程。,基本思想：將一個(gè)具有n個(gè)待排序記錄的序列看成是n個(gè)長度為1的有序序列，然后進(jìn)行兩兩歸并，得到n/2個(gè)長度為2的有序序列，再進(jìn)行兩兩歸并，得到n/4個(gè)長度為4的有序序列，直至得到一個(gè)長度為n的有序序列為止。,二路歸并排序,需解決的關(guān)鍵問題?,如何將兩個(gè)有序序列合成一個(gè)有序序列？ 怎樣完成一趟歸并？ 如何控制二路

35、歸并的結(jié)束？,8.5 歸并排序,關(guān)鍵問題：如何將兩個(gè)有序序列合成一個(gè)有序序列？,60 20 31 5 44 55 65,5,20,31,60,8.5 歸并排序,關(guān)鍵問題：如何將兩個(gè)有序序列合成一個(gè)有序序列？,60 20 31 5 44 55 65,5,20,31,60,歸并可以就地進(jìn)行嗎?,8.5 歸并排序,在歸并過程中，可能會(huì)破壞原來的有序序列，所以，將歸并的結(jié)果存入另外一個(gè)數(shù)組中。,關(guān)鍵問題：如何將兩個(gè)有序序列合成一個(gè)有序序列？,60 20 31 5 44 55 65,5,20,31,60,8.5 歸并排序,關(guān)鍵問題：如何將兩個(gè)有序序列合成一個(gè)有序序列？,60 20 31 5 44 55

36、65,5,20,31,60,子序列的長度一定相等嗎?,8.5 歸并排序,關(guān)鍵問題：如何將兩個(gè)有序序列合成一個(gè)有序序列？,60 20 31 5 44 55 65,5,20,31,60,8.5 歸并排序,關(guān)鍵問題：如何將兩個(gè)有序序列合成一個(gè)有序序列？,設(shè)相鄰的有序序列為rs rm和rm+1 rt，歸并成一個(gè)有序序列r1s r1t,8.5 歸并排序,void Merge (int r , int r1 , int s, int m, int t ) i=s; j=m+1; k=s; while (i=m /后一個(gè)子序列 ,關(guān)鍵問題：如何將兩個(gè)有序序列合成一個(gè)有序序列？,算法描述：,8.5 歸并排序,

37、關(guān)鍵問題：怎樣完成一趟歸并？,60 20 31 5 44 55 65,在一趟歸并中，除最后一個(gè)有序序列外，其它有序序列中記錄的個(gè)數(shù)相同，用長度h表示。,8.5 歸并排序,關(guān)鍵問題：怎樣完成一趟歸并？,設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄，歸并的步長是2h， 在歸并過程中，有以下三種情況：,若in-2h+1，則相鄰兩個(gè)有序表的長度均為h，執(zhí)行一次歸并，完成后i加2h，準(zhǔn)備進(jìn)行下一次歸并；,i=1 n-2h+1=4,8.5 歸并排序,關(guān)鍵問題：怎樣完成一趟歸并？,設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄，歸并的步長是2h，在歸并過程中，有以下三種情況：,若in-2h+1，則相鄰兩個(gè)有序表的長度均為h，執(zhí)行

38、一次歸并，完成后i加2h，準(zhǔn)備進(jìn)行下一次歸并；,算法描述： while (in-2h+1) Merge (r, r1, i, i+h-1, i+2*h-1); i+=2*h; ,8.5 歸并排序,關(guān)鍵問題：怎樣完成一趟歸并？,設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄，歸并的步長是2h，在歸并過程中，有以下三種情況：,若in-h+1，則表示仍有兩個(gè)相鄰有序表，一個(gè)長度為h，另一個(gè)長度小于h，則執(zhí)行兩個(gè)有序表的歸并，完成后退出一趟歸并。,i=4 n-2h+1=4 n-h+1=6,8.5 歸并排序,關(guān)鍵問題：怎樣完成一趟歸并？,設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄，歸并的步長是2h，在歸并過程中，有以下三種

39、情況：,若in-h+1，則表示仍有兩個(gè)相鄰有序表，一個(gè)長度為h，另一個(gè)長度小于h，則執(zhí)行兩個(gè)有序表的歸并，完成后退出一趟歸并。,算法描述： if (in-h+1) Merge (r, r1, i, i+h-1, n);,8.5 歸并排序,關(guān)鍵問題：怎樣完成一趟歸并？,設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄，歸并的步長是2h，在歸并過程中，有以下三種情況：,若in-h+1，則表明只剩下一個(gè)有序表，直接將該有序表送到r1的相應(yīng)位置，完成后退出一趟歸并。,i=9 n-h+1=8,8.5 歸并排序,關(guān)鍵問題：怎樣完成一趟歸并？,設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄，歸并的步長是2h，在歸并過程中，有以下三種

40、情況：,若in-h+1，則表明只剩下一個(gè)有序表，直接將該有序表送到r1的相應(yīng)位置，完成后退出一趟歸并。,算法描述： if (i=n-h+1) for (k=i; k=n; k+) r1k=rk;,8.5 歸并排序,void MergePass (int r , int r1 , int n, int h) i=1; while (in-2h+1) /情況1 Merge (r, r1, i, i+h-1, i+2*h-1); i+=2*h; if (in-h+1) Merge (r, r1, i, i+h-1, n); /情況2 else for (k=i; k=n; k+) /情況3 r1k=

41、rk; ,一趟歸并排序算法,8.5 歸并排序,解決方法： 開始時(shí)，有序序列的長度h=1，結(jié)束時(shí)，有序序列的長度h=n，用有序序列的長度來控制排序的結(jié)束。,關(guān)鍵問題：如何控制二路歸并的結(jié)束？,8.5 歸并排序,算法描述： void MergeSort (int r , int r1 , int n ) h=1; while (hn) MergePass (r, r1, n, h); h=2*h; MergePass (r1, r, n, h); h=2*h; ,關(guān)鍵問題：如何控制二路歸并的結(jié)束？,8.5 歸并排序,二路歸并的遞歸實(shí)現(xiàn),8.5 歸并排序,void MergeSort2(int r

42、, int r1 , int s, int t) if (s=t) r1s=rs; /遞歸出口 else m=(s+t)/2; Mergesort2(r, r1, s, m); /歸并排序前半個(gè)子序列 Mergesort2(r, r1, m+1, t); /歸并排序后半個(gè)子序列 Merge(r1, r, s, m, t); 將兩個(gè)已排序的子序列歸并 ,二路歸并的遞歸實(shí)現(xiàn),8.5 歸并排序,二路歸并排序算法的性能分析,8.5 歸并排序,分配排序的基本思想,8.6 分配排序,分配排序是基于分配和收集的排序方法，其基本思想是：先將待排序記錄序列分配到不同的桶里，然后再把各桶中的記錄依次收集到一起。,

43、桶式排序,8.6 分配排序,桶式排序的基本思想是：假設(shè)待排序記錄的值都在0m-1之間，設(shè)置m個(gè)桶，首先將值為i的記錄分配到第i個(gè)桶中，然后再將各個(gè)桶中的記錄依次收集起來。,桶式排序,8.6 分配排序,需解決的關(guān)鍵問題?,（1）如何表示桶？即如何存儲(chǔ)具有相同鍵值的記錄？ （2）如何進(jìn)行分配操作？ （3）如何進(jìn)行收集操作？,問題1如何表示桶？,8.6 分配排序,由于具有相同鍵值的記錄可能會(huì)有多個(gè)，所以，應(yīng)采用鏈接存儲(chǔ)，為保證排序的穩(wěn)定性，可以設(shè)m個(gè)鏈隊(duì)列作為桶的存儲(chǔ)結(jié)構(gòu)。為避免在分配和收集的過程中移動(dòng)元素，采用靜態(tài)鏈表作為鏈隊(duì)列和待排序記錄序列的存儲(chǔ)結(jié)構(gòu)，定義如下：,struct Node /定義

44、靜態(tài)鏈表存儲(chǔ)待排序記錄序列 int key; /記錄的鍵值 int next; /游標(biāo)，下一個(gè)鍵值在數(shù)組中的下標(biāo) ; struct QueueNode /定義靜態(tài)鏈隊(duì)列存儲(chǔ)桶 int front; /隊(duì)頭指針，指向隊(duì)頭元素在數(shù)組中的下標(biāo) int rear; /隊(duì)尾指針，指向隊(duì)尾元素在數(shù)組中的下標(biāo) ;,問題1如何表示桶？,8.6 分配排序,由于具有相同鍵值的記錄可能會(huì)有多個(gè)，所以，應(yīng)采用鏈接存儲(chǔ)，為保證排序的穩(wěn)定性，可以設(shè)m個(gè)鏈隊(duì)列作為桶的存儲(chǔ)結(jié)構(gòu)。為避免在分配和收集的過程中移動(dòng)元素，采用靜態(tài)鏈表作為鏈隊(duì)列和待排序記錄序列的存儲(chǔ)結(jié)構(gòu)。,問題2如何進(jìn)行分配操作？,8.6 分配排序,分配操作即是將記

45、錄插入到相應(yīng)的隊(duì)列中，入隊(duì)在靜態(tài)鏈表上實(shí)現(xiàn)，并修改相應(yīng)隊(duì)列的隊(duì)頭指針和隊(duì)尾指針。,問題2如何進(jìn)行分配操作？,8.6 分配排序,分配操作即是將記錄插入到相應(yīng)的隊(duì)列中，入隊(duì)在靜態(tài)鏈表上實(shí)現(xiàn)，并修改相應(yīng)隊(duì)列的隊(duì)頭指針和隊(duì)尾指針。,void Distribute(Node r , int n, QueueNode q , int m, int first) /first為靜態(tài)鏈表的頭指針，從下標(biāo)0開始存放待排序序列 i = first; while (ri.next != -1) /依次分配每一個(gè)待排序記錄 k = ri.key; if (qk.front = -1) qk.front = i; /處理隊(duì)列為空的情況 else rqk.rear.next = i; /在靜態(tài)鏈表中實(shí)現(xiàn)插在隊(duì)列尾部 qk.rear = i; /修改隊(duì)尾指針 i = ri.next; /i后移，處理下一個(gè)記錄 ,問題3如何進(jìn)行收集操作？,8.6 分配排序,收集操作即是將所有隊(duì)列收尾相接。,問題3如何進(jìn)行收集操作？,8.6 分配排序,收集操作即是將所有隊(duì)列收尾相接。,void Collect(Node r , int n, QueueNode q , int m, int first) /first為靜態(tài)鏈表的頭指針從下標(biāo)0開始存放待排序序列 k = 0; while (qk.front