數(shù)據(jù)結(jié)構(gòu)(c語言版)課件_第八章_排序_(嚴蔚敏、吳偉民編_清華大學出版社).ppt

1、第八章 排序,排序定義將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序的序列叫 排序分類 按待排序記錄所在位置 內(nèi)部排序：待排序記錄存放在內(nèi)存 外部排序：排序過程中需對外存進行訪問的排序 按排序依據(jù)原則 插入排序：直接插入排序、折半插入排序、希爾排序 交換排序：冒泡排序、快速排序 選擇排序：簡單選擇排序、堆排序 歸并排序：2-路歸并排序 基數(shù)排序,按排序所需工作量 簡單的排序方法：T(n)=O(n) 先進的排序方法：T(n)=O(logn) 基數(shù)排序：T(n)=O(d.n) 排序基本操作 比較兩個關(guān)鍵字大小 將記錄從一個位置移動到另一個位置,8.1 插入排序 直接插入排序 排序過

2、程：整個排序過程為n-1趟插入，即先將序列中第1個記錄看成是一個有序子序列，然后從第2個記錄開始，逐個進行插入，直至整個序列有序,算法描述,例,49 38 65 97 76 13 27,i=2 38 (38 49) 65 97 76 13 27,i=3 65 (38 49 65) 97 76 13 27,i=4 97 (38 49 65 97) 76 13 27,i=5 76 (38 49 65 76 97) 13 27,i=6 13 (13 38 49 65 76 97) 27,i=1 ( ),i=7 (13 38 49 65 76 97) 27,27,97,76,65,49,38,27,算

3、法評價 時間復(fù)雜度 若待排序記錄按關(guān)鍵字從小到大排列(正序) 關(guān)鍵字比較次數(shù)：,記錄移動次數(shù)：,若待排序記錄按關(guān)鍵字從大到小排列(逆序) 關(guān)鍵字比較次數(shù)：,記錄移動次數(shù)：,若待排序記錄是隨機的，取平均值 關(guān)鍵字比較次數(shù)：,記錄移動次數(shù)：,T(n)=O(n),空間復(fù)雜度：S(n)=O(1),Ch8_1.c,折半插入排序 排序過程：用折半查找方法確定插入位置的排序叫,例,i=1 (30) 13 70 85 39 42 6 20,i=2 13 (13 30) 70 85 39 42 6 20,i=7 6 (6 13 30 39 42 70 85 ) 20,.,i=8 20 (6 13 20 30 3

4、9 42 70 85 ),算法描述,算法評價 時間復(fù)雜度：T(n)=O(n) 空間復(fù)雜度：S(n)=O(1),Ch8_2.c,希爾排序(縮小增量法) 排序過程：先取一個正整數(shù)d1n，把所有相隔d1的記錄放一組，組內(nèi)進行直接插入排序；然后取d2d1，重復(fù)上述分組和排序操作；直至di=1，即所有記錄放進一個組中排序為止,算法描述,Ch8_3.c,#define T 3 int d=5,3,1;,49,13,38,27,27,4,55,38,65,48,97,55,76,4,希爾排序特點 子序列的構(gòu)成不是簡單的“逐段分割”，而是將相隔某個增量的記錄組成一個子序列 希爾排序可提高排序速度，因為 分組后

5、n值減小，n更小，而T(n)=O(n),所以T(n)從總體上看是減小了 關(guān)鍵字較小的記錄跳躍式前移，在進行最后一趟增量為1的插入排序時，序列已基本有序 增量序列取法 無除1以外的公因子 最后一個增量值必須為1,8.2 交換排序 冒泡排序 排序過程 將第一個記錄的關(guān)鍵字與第二個記錄的關(guān)鍵字進行比較，若為逆序r1.keyr2.key，則交換；然后比較第二個記錄與第三個記錄；依次類推，直至第n-1個記錄和第n個記錄比較為止第一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被安置在最后一個記錄上 對前n-1個記錄進行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第n-1個記錄位置 重復(fù)上述過程，直到“在一趟排序過程

6、中沒有進行過交換記錄的操作”為止,例,38,49,76,97,13,97,27,97,30,97,13,76,76,76,27,30,13,65,27,65,30,65,13,13,49,49,30,49,27,38,27,38,30,38,算法描述,算法評價 時間復(fù)雜度 最好情況（正序） 比較次數(shù)：n-1 移動次數(shù)：0 最壞情況（逆序） 比較次數(shù)：,移動次數(shù)：,空間復(fù)雜度：S(n)=O(1),T(n)=O(n),Ch8_4.c,快速排序 基本思想：通過一趟排序，將待排序記錄分割成獨立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄進行排序，以達到整個序列有序

7、 排序過程：對rst中記錄進行一趟快速排序，附設(shè)兩個指針i和j，設(shè)樞軸記錄rp=rs，x=rp.key 初始時令i=s,j=t 首先從j所指位置向前搜索第一個關(guān)鍵字小于x的記錄，并和rp交換 再從i所指位置起向后搜索，找到第一個關(guān)鍵字大于x的記錄，和rp交換 重復(fù)上述兩步，直至i=j為止 再分別對兩個子序列進行快速排序，直到每個子序列只含有一個記錄為止,完成一趟排序： ( 27 38 13) 49 (76 97 65 50),分別進行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97),快速排序結(jié)束： 13 27 38 49 50 65 76 97,49,27,49,6

8、5,13,49,49,97,算法描述,算法評價 時間復(fù)雜度 最好情況（每次總是選到中間值作樞軸）T(n)=O(nlog2n) 最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(n),空間復(fù)雜度：需?？臻g以實現(xiàn)遞歸 最壞情況：S(n)=O(n) 一般情況：S(n)=O(log2n),T(n)=O(n),Ch8_5.c,8.3 選擇排序 簡單選擇排序 排序過程 首先通過n-1次關(guān)鍵字比較，從n個記錄中找出關(guān)鍵字最小的記錄，將它與第一個記錄交換 再通過n-2次比較，從剩余的n-1個記錄中找出關(guān)鍵字次小的記錄，將它與第二個記錄交換 重復(fù)上述操作，共進行n-1趟排序后，排序結(jié)束,例,初始： 49

9、 38 65 97 76 13 27 ,i=1,13,49,一趟： 13 38 65 97 76 49 27 ,i=2,27,38,六趟： 13 27 38 49 65 76 97 ,排序結(jié)束： 13 27 38 49 65 76 97,算法描述,算法評價 時間復(fù)雜度 記錄移動次數(shù) 最好情況：0 最壞情況：3(n-1) 比較次數(shù)：,空間復(fù)雜度：S(n)=O(1),T(n)=O(n),Ch8_6.c,堆排序 堆的定義：n個元素的序列(k1,k2,kn)，當且僅當滿足下列關(guān)系時，稱之為堆,例 （96，83，27，38，11，9）,例 （13，38，27，50，76，65，49，97）,可將堆序列看

10、成完全二叉樹，則堆頂 元素（完全二叉樹的根）必為序列中 n個元素的最小值或最大值,堆排序：將無序序列建成一個堆，得到關(guān)鍵字最?。ɑ蜃畲螅┑挠涗?；輸出堆頂?shù)淖钚。ù螅┲岛?，使剩余的n-1個元素重又建成一個堆，則可得到n個元素的次小值；重復(fù)執(zhí)行，得到一個有序序列，這個過程叫 堆排序需解決的兩個問題： 如何由一個無序序列建成一個堆？ 如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個新的堆？ 第二個問題解決方法篩選 方法：輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結(jié)點值與左、右子樹的根結(jié)點值進行比較，并與其中小者進行交換；重復(fù)上述操作，直至葉子結(jié)點，將得到新的堆，稱這個從堆頂至葉子的調(diào)整過

11、程為“篩選”,例,算法描述,第一個問題解決方法 方法：從無序序列的第n/2個元素（即此無序序列對應(yīng)的完全二叉樹的最后一個非終端結(jié)點）起，至第一個元素止，進行反復(fù)篩選,例 含8個元素的無序序列（49，38，65，97，76，13，27，50）,算法描述,算法評價 時間復(fù)雜度：最壞情況下T(n)=O(nlogn) 空間復(fù)雜度：S(n)=O(1),Ch8_7.c,8.4 歸并排序 歸并將兩個或兩個以上的有序表組合成一個新的有序表，叫 2-路歸并排序 排序過程 設(shè)初始序列含有n個記錄，則可看成n個有序的子序列，每個子序列長度為1 兩兩合并，得到n/2個長度為2或1的有序子序列 再兩兩合并，如此重復(fù)，直

12、至得到一個長度為n的有序序列為止,例,初始關(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,算法描述,算法評價 時間復(fù)雜度：T(n)=O(nlog2n) 空間復(fù)雜度：S(n)=O(n),Ch8_9.c,8.5 基數(shù)排序 多關(guān)鍵字排序 定義：,例 對52張撲克牌按以下次序排序： 23A23A 23A23A 兩個關(guān)鍵字：花色（ ） 面值（23A） 并且“花色”地位高于“面值”,多關(guān)鍵字排序方法 最高位優(yōu)先法（MSD)：先對最高位關(guān)

13、鍵字k1（如花色）排序，將序列分成若干子序列，每個子序列有相同的k1值；然后讓每個子序列對次關(guān)鍵字k2（如面值）排序，又分成若干更小的子序列；依次重復(fù)，直至就每個子序列對最低位關(guān)鍵字kd排序；最后將所有子序列依次連接在一起成為一個有序序列,最低位優(yōu)先法(LSD)：從最低位關(guān)鍵字kd起進行排序，然后再對高一位的關(guān)鍵字排序，依次重復(fù)，直至對最高位關(guān)鍵字k1排序后，便成為一個有序序列 MSD與LSD不同特點 按MSD排序，必須將序列逐層分割成若干子序列，然后對各子序列分別排序 按LSD排序，不必分成子序列，對每個關(guān)鍵字都是整個序列參加排序；并且可不通過關(guān)鍵字比較，而通過若干次分配與收集實現(xiàn)排序 鏈式

14、基數(shù)排序 基數(shù)排序：借助“分配”和“收集”對單邏輯關(guān)鍵字進行排序的一種方法 鏈式基數(shù)排序：用鏈表作存儲結(jié)構(gòu)的基數(shù)排序,鏈式基數(shù)排序步驟 設(shè)置10個隊列，fi和ei分別為第i個隊列的頭指針和尾指針 第一趟分配對最低位關(guān)鍵字（個位）進行，改變記錄的指針值，將鏈表中記錄分配至10個鏈隊列中，每個隊列記錄的關(guān)鍵字的個位相同 第一趟收集是改變所有非空隊列的隊尾記錄的指針域，令其指向下一個非空隊列的隊頭記錄，重新將10個隊列鏈成一個鏈表 重復(fù)上述兩步，進行第二趟、第三趟分配和收集，分別對十位、百位進行，最后得到一個有序序列,例,算法描述,算法評價 時間復(fù)雜度： 分配：T(n)=O(n) 收集：T(n)=O(rd) T(n)=O(d(n+rd) 其中：n記錄數(shù) d關(guān)鍵字數(shù) rd關(guān)鍵字取值范圍 空間復(fù)雜度：S(n)=2rd個隊列指針+n個指針域空間,Ch8_10.c,f0=0 e0=0 f1=0 e1=0 f2=0 e2=0 f3=0 e3=0 f4=0 e4=0 f5=0 e5=0 f6=0 e6=0 f7=0 e7=0 f8=0 e8=0 f9=0 e9=0,1,1,2,2,3,3,4,4,5,6,6,7,7,8,9,10,f0=0 e0=0 f1=0 e1=0 f2=0 e2=0