【數(shù)據(jù)結(jié)構(gòu)與算法】排序

1、第十章 內(nèi)部排序,10.1 概述 10.2 插入排序 10.2.1 直接插入排序 10.2.3 shell排序 10.3 交換排序（快速排序） 10.4 選擇排序 10.4.1 簡(jiǎn)單選擇排序 10.4.3 堆排序 10.5 歸并排序 10.6 基數(shù)排序 10.7 各種排序方法的比較討論,10.1 內(nèi)部排序概述,排序(Sorting): 將數(shù)據(jù)元素(或記錄)的一個(gè)任意序列,重新排列成一個(gè)按關(guān)鍵字有序的序列。 排序方法的穩(wěn)定性： 對(duì)關(guān)鍵字相同的數(shù)據(jù)元素，排序前后它們的領(lǐng)先關(guān)系保持不變，則稱該排序方法是穩(wěn)定的。反之，稱該排序方法是不穩(wěn)定的。 內(nèi)部排序 待排序記錄存放在計(jì)算機(jī)的內(nèi)存中進(jìn)行排序。 外部排

2、序 待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中尚需對(duì)外存進(jìn)行訪問的排序。,排序的分類,按排序過程依據(jù)的不同原則進(jìn)行分類： 插入排序、 交換排序、 選擇排序、 歸并排序和 基數(shù)排序 按工作量分類，可以分為三類： (1)簡(jiǎn)單的排序方法,其時(shí)間復(fù)雜度為O(n2); (2)先進(jìn)的排序方法,其時(shí)間復(fù)雜度為O(nlog2n); (3)基數(shù)排序，其時(shí)間復(fù)雜度為O(dn);,排序的基本操作和記錄的存儲(chǔ)方式,排序過程中需要的兩種基本操作： （1）比較關(guān)鍵字的大小； （2）將記錄從一個(gè)位置移至另一個(gè)位置。 待排序記錄序列可有下列三種存儲(chǔ)方式： （1）記錄存放在一組連續(xù)的存儲(chǔ)單元中；類似于線性

3、表的順序存儲(chǔ)結(jié)構(gòu)，記錄次序由存儲(chǔ)位置決定，實(shí)現(xiàn)排序需移動(dòng)記錄。 （2）記錄存放在靜態(tài)鏈表中；記錄次序由指針指示，實(shí)現(xiàn)排序不需移動(dòng)記錄，僅需修改指針。- 鏈排序 （3）記錄本身存放在一組連續(xù)的存儲(chǔ)單元中，同時(shí)另設(shè)指示各個(gè)記錄存儲(chǔ)位置的地址向量，排序過程中不移動(dòng)記錄本身，而移動(dòng)地址向量中相應(yīng)記錄的地址。排序結(jié)束后再根據(jù)地址調(diào)整記錄的存儲(chǔ)位置。- 地址排序,待排序記錄的數(shù)據(jù)類型,#define MAXSIZE 20 typedef int KeyType; typedef struct KeyType key; InfoType otherinfo; RcdType; typedef struct

4、RedType rMAXSIZE+1; int length; SqList;,10.2 插入排序10.2.1 直接插入排序,例：序列為49，38，65，97，76，13，27，49 (49)，38，65，97，76，13，27，49 (38) (38，49)，65，97，76，13，27，49 (65) (38，49，65)，97，76，13，27，49 (97) (38，49，65，97)，76，13，27，49 (76) (38，49，65，76，97)，13，27，49 (13) (13，38，49，65，76，97)，27，49 (27) (13，27，38，49，65，76，97)

5、，49 (49) (13，27，38，49，49，65，76，97),直接插入排序算法,void InsertSort(SqList / InsertSort,時(shí)間：最壞情形判斷與移動(dòng)各接近 n(n+1)/2; 最好情形判斷n次，無移動(dòng)；故時(shí)間復(fù)雜度：O(n2) 空間：一個(gè)輔助空間,10.2.2 Shell排序算法,基本思想： 先將整個(gè)待排序記錄序列分割成若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。 算法復(fù)雜度：O(n3/2),Shell排序舉例（非穩(wěn)定的）,10.3 交換排序 1. 冒泡排序（其時(shí)間復(fù)雜度O(n2)）,初 始 關(guān) 鍵 字,第 一

6、 趟 排 序 后,第 二 趟 排 序 后,第 三 趟 排 序 后,第 四 趟 排 序 后,第 五 趟 排 序 后,第 六 趟 排 序 后,2. 快速排序- 對(duì)冒泡排序的一種改進(jìn),基本思想： 通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，其中一部分的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)分別進(jìn)行排序，以達(dá)到整個(gè)序列有序。,快速排序舉例,初始關(guān)鍵字：49，38，65，97，76，13，27，49,一趟完成后：27，38，13，49，76，97，65，49,快速排序分析,快速排序的平均時(shí)間為T(n) = knlog(n) k為某個(gè)常數(shù)因子 經(jīng)驗(yàn)表明,在同數(shù)量級(jí)的排序方法中,快速排序的

7、常數(shù)因子k最小. 就平均時(shí)間而言,快速排序是最好的. 若初始序列按關(guān)鍵字基本有序,快速排序蛻化為起泡排序,其時(shí)間復(fù)雜度為O(n2)。 改進(jìn)的方法，用“三者取中”的法則選取樞軸記錄（pivotkey).,快速排序舉例,初始關(guān)鍵字：49，38，65，97，76，13，27，49,一趟完成后：27，38，13，49，76，97，65，49,快速排序算法（一）,int Partition(SqList ,快速排序算法（二）,void Qsort(SqList / QuickSort,10.4 選擇排序 10.4.1. 簡(jiǎn)單選擇排序（其時(shí)間復(fù)雜度O(n2)）,基本思想： 每一趟在序列的后n-i+1(i=

8、1,2,.,n-1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為第i個(gè)記錄。,void SelectSort(SqList / 與第i個(gè)記錄交換 / SelectSort,初始關(guān)鍵字：49，38，65，97，76，13，27，49 第一次交換：13，38，65，97，76，49，27，49,10.4.3 堆排序,堆的定義： n個(gè)元素的序列k1,k2,.,kn當(dāng)且僅當(dāng)滿足下列條件時(shí)，稱之為堆。,堆舉例： 96,83,27,38,11,09) 12,36,24,85,47,30,53,91,完全二叉樹,且所有非葉 結(jié)點(diǎn)的值均不大于(不小 于)其左、右孩子結(jié)點(diǎn)的值,實(shí)現(xiàn)堆要解決的問題,（1）如何從一個(gè)無序序列建

9、成一個(gè)堆？ （2）如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個(gè)新的堆？,無序序列建成一個(gè)堆（從第n/2到1個(gè)元素） 49，38，65，97，76，13，27，49,10.5 歸并排序(Merging Sort),將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表 2-路歸并舉例:,初始關(guān)鍵字: 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,2-路歸并算法,void Merge(RcdType SR, RcdType /復(fù)制剩余的SRj.n

10、 / Merge,歸并算法的特點(diǎn),需要輔助空間: O(n) 整個(gè)歸并需要 log2n 趟 時(shí)間復(fù)雜度: O(n log2n) 它是穩(wěn)定的排序方法 思想可以推廣到 “多-路歸并“,10.6 基數(shù)排序(Radix Sorting),不需要進(jìn)行關(guān)鍵字之間的比較 借助多關(guān)鍵字排序的思想對(duì)單關(guān)鍵字排序 10.6.1 多關(guān)鍵字排序 2345678910JQKA 2345678910JQKA 2345678910JQKA 2345678910JQKA 花色 ()優(yōu)先于面值(23.A) 最高位優(yōu)先(MSD): 分成子序列分別排序 最高位優(yōu)先(LSD): 通過若干次“分配”和“收集“,10.6.2 基數(shù)排序,借

11、助“分配”和“收集“兩種操作對(duì)單關(guān)鍵字進(jìn)行排序。例如: 278-109-063-930-589-184-505-269-008-083,278,109,063,930,184,505,589,269,008,083,930-063-083-184-505-278-008-109-589-269,930-063-083-184-505-278-008-109-589-269,278,109,063,930,184,505,589,269,008,184,505-008-109-930-063-269-278-083-184-589,505,008,109,930,063,269,278,083,

12、083,589,008-063-083-109-184-269-278-505-589-930,基數(shù)排序分析(d個(gè)關(guān)鍵字的取值范圍rd）,“收集”重復(fù)的次數(shù)為d; 一輪“分配”的次數(shù)為n+rd; 時(shí)間復(fù)雜度為O(d(n+rd); 鏈?zhǔn)交鶖?shù)排序所需輔助存儲(chǔ)量為O(n)。,10.7 各種排序方法的比較討論,排序方法 簡(jiǎn)單排序 Shell排序 快速排序 堆排序 歸并排序 基數(shù)排序,平均時(shí)間 O(n2) O(n3/2) O(nlogn) O(nlogn) O(nlogn) O(d(n+rd),最壞情況 O(n2) O(n2) O(n2) O(nlogn) O(nlogn) O(d(n+rd),輔助存儲(chǔ) O(1) O(1) O(logn) O(1) O(n) O(rd),插入, 交換, 選擇, 歸并, 基數(shù)排序,幾個(gè)結(jié)論,(1)平均時(shí)間性能快速排序最佳,但最壞情況下的時(shí)間性能不如堆排序和歸并排序. (2)簡(jiǎn)單排序以“直接插入排序”最簡(jiǎn)單,當(dāng)序列“基本有序”或n較