第10章內排序

一、排序的基本概念
- 1.1 排序演算法的記錄存盤結構定義
二、插入排序
- 2.1 直接插入排序
- 2.1.1 直接插入排序演算法（演算法）
- 2.2 二分法（折半）插入排序
- 2.3 表插入排序（大綱未規定）
- 2.4 希爾（Shell）插入排序
三、選擇排序
- 3.1 直接選擇排序
  - 3.1.1 直接選擇排序演算法（演算法）
- 3.2 樹型選擇排序（大綱未規定）
- 3.3 堆排序
四、交換排序
- 4.1 冒泡排序
- 4.2 快速排序
五、歸并排序
六、基數排序
- 6.1 多排序碼的排序
- 6.2 靜態鏈式基數排序
七、各種內部排序演算法的比較（書中未給出）
八、內部排序演算法的應用（書中未給出）
九、演算法設計題
十、錯題集

一、排序的基本概念

排序：假設一個檔案由 $n$ 個記錄 $R_1,R_2,\cdots,R_n$ 組成，以記錄中某個（或幾個）欄位值不減（或不增）的次序把這 $n$ 個記錄重新排列，稱該欄位為排序碼
關鍵碼：能唯一標識一個記錄的欄位，關鍵碼可以作為排序碼，但排序碼不一定要是關鍵碼
穩定排序演算法：任意兩個排序碼相同的記錄 $R_i$ 和 $R_j$，如果排序前 $R_i$ 在 $R_j$ 的前面，排序后 $R_i$ 還在在 $R_j$ 的前面，則該演算法是穩定的排序演算法，否則是不穩定的排序演算法
注：以下討論的排序，都是以記錄中某個欄位值不減的次序把這 $n$ 個記錄重新排列，且排序碼資料型別為整型

1.1 排序演算法的記錄存盤結構定義

#define MAXSIZE 100 // 檔案中記錄個數的最大值
typedef int keytype; // 定義排序碼型別為整數型別
typedef struct {
    keytype key;
    // int other; // 此處還可以定義記錄中除排序碼外的其它域
} recordtype; // 記錄型別的定義
typedef struct {
    recordtype r[MAXSIZE + 1];
    int length; // 待排序檔案中記錄的個數
} table; // 待排序檔案型別

二、插入排序

2.1 直接插入排序

演算法步驟：
1. 初始認為檔案中的第 $1$ 個記錄已排好序
2. 然后把第 $2$ 個到第 $n$ 個記錄依次插入到已排序的記錄組成的檔案中
3. 對第 $i$ 個記錄 $R_i$ 進行插入時，$R_1,R_2,\cdots,R_{i-1}$ 已排序
  1. 把記錄 $R_i$ 的排序碼 $key_i$ 和已經排好序的排序碼從右向左依次比較，找到 $R_i$ 應插入的位置
  2. 把該位置以后直到 $R_{i-1}$ 的記錄順序后移，空出位置讓 $R_i$ 插入
4. 注：當待插入排序小于所有已排序的排序碼時，可能會出現下標越界，因此可以在排序檔案的第一個排序碼前插入一個值作為哨兵
圖10-2-直接插入排序演算法的執行程序示意圖：

2.1.1 直接插入排序演算法（演算法）

void insertsort(table *tab) {
    int i, j;
    // 依次插入從第2個開始的所有元素
    for (i = 2; i <= tab->length; i++) {
        j = i - 1;
        tab->r[0].key = tab->r[i].key; // 設定哨兵，準備找插入位置

        // 找插入位置并后移
        while (tab->r[0].key < tab->r[j].key) {
            tab->r[j + 1].key = tab->r[j].key; // 后移
            j = j - 1; // 繼續向前（左）查找
        }
        tab->r[j + 1].key = tab->r[0].key; // 插入第i個元素的副本，即前面設定的哨兵
    }
}

時間復雜度：$O(n^2)$

2.2 二分法（折半）插入排序

演算法步驟：
1. 注：依據直接插入排序的思想，進行擴充
2. 在找第 $i$ 個記錄的插入位置時，由于前 $i-1$ 個記錄已排好序，因此在插入程序中使用二分法確定 $key[i]$ 的插入位置
演算法代碼：略

2.3 表插入排序（大綱未規定）

2.4 希爾（Shell）插入排序

演算法步驟：
1. 對 $n$ 個記錄進行排序，首先取一個整數 $d<n$，把這個 $n$ 個記錄分成 $d$ 組
2. 所有位置相差為 $d$ 的倍數的記錄分在同一組
3. 在每組中使用直接插入排序進行組內排序
4. 縮小 $d$ 的值
5. 重復進行分組和組內排序
6. 知道 $d=1$ 結束排序
演算法代碼：略
圖10-5-Shell插入排序示意圖：

三、選擇排序

選擇排序基本思想：每次從待排序檔案中選擇出排序碼最小的記錄，把該記錄放入已排序檔案的最后一個位置

3.1 直接選擇排序

演算法步驟：
1. 首先從 $n$ 個記錄中選擇排序碼最小的記錄，讓該記錄和第 $1$ 個記錄交換
2. 再從剩下的 $n-1$ 個記錄選出排序碼最小的記錄，讓該記錄和第 $2$ 個記錄交換
3. 重復這樣的操作直到剩下最后兩個記錄
4. 從最后兩個記錄中選出最小的記錄和第 $n-1$ 個記錄交換
5. 結束
圖10-6-直接選擇排序演算法執行程序：

3.1.1 直接選擇排序演算法（演算法）

void simpleselectsort(table *tab) {
    int i, j, k;
    for (i = 1; i <= tab->length - 1; i++) {
        k = i; // 記下當前最小元素的位置

        // 向右查找更小的元素
        for (j = i + 1; j <= tab->length; j++)
            if (tab->r[j].key < tab->r[k].key) k = j; // 修改當前最小元素的位置
            
        // 如果第i次選到的最小元素位置k不等于i，則將第k、i個元素交換
        if (k != i) {
            tab->r[0].key = tab->r[k].key;  // 以第0個元素作為中間單元進行交換
            tab->r[k].key = tab->r[i].key;
            tab->r[i].key = tab->r[0].key;
        }
    }
}

時間復雜度：$O(n^2)$

3.2 樹型選擇排序（大綱未規定）

3.3 堆排序

堆排序解決的問題：保存中間比較結果，減少后面的比較次數，又不占用大量的附加存盤空間
堆：一個序列 $\{k_1,k_2,\cdots,k_n\}$，其中 $k_i\leq{k_{2i}}$ 且 $k_i\leq{k_{2i+1}}$，當 $i=1,2,\cdots,n/2$ 且 $2i+1\leq{n}$
1. 注：當采用順序存盤這個序列，就可以把這個序列的每一個元素 $k_i$ 看成是一顆有 $n$ 個結點的完全二叉樹的第 $i$ 個結點，其中 $k_1$ 是該二叉樹的根結點
堆的特征：把堆對應的一維陣列看作一顆完全二叉樹的順序存盤，則該完全二叉樹中任意分支結點的值都小于或等于它的左右兒子結點的值，且根結點的值是所有元素中值最小的
最小堆和最大堆：當父節點的值總是大于等于任何一個子節點的值時為最大堆；當父節點的值總是小于等于任何一個子節點的值時為最小堆
堆排序使用條件：當對記錄 $n$ 較大的檔案，堆排序很好，當 $n$ 較小時，并不提倡使用，因為初始建堆和調整建新堆時需要進行反復的篩選
圖10-8-一個序列 Arr = {5, 1, 13, 3, 16, 7, 10, 14, 6, 9}和相應的完全二叉樹：
構造最大堆步驟（通過已有完全二叉樹構建堆）：
1. 主要思想：判斷有子女結點的子樹是否滿足最大（小）堆的要求
2. 首先我們需要找到最后一個結點的父結點如圖 $(a)$，我們找到的結點是 $16$，然后找出該結點的最大子節點與自己比較，若該子節點比自身大，則將兩個結點交換，圖 $(a)$ 中，$16$ 是最大的結點，不需要交換
3. 我們移動到第下一個父結點 $3$，如圖 $(b)$ 所示，同理做第一步的操作，交換了 $3$ 和 $14$，結果如圖 $(c)$ 所示
4. 移動結點到下一個父結點 $13$，如圖 $(d)$ 所示，發現不需要做任何操作
5. 移動到下個父結點 $1$，如圖 $(e)$ 所示,然后交換 $1$ 和 $16$，如圖 $(f)$ 所示，此時我們發現交換后，$1$ 的子節點并不是最大的，我們接著在交換，如圖 $(g)$所示
6. 移動到父結點到 $5$，一次重復上述步驟，交換 $5$ 和 $16$，在交換 $14$ 和 $5$，在交換 $5$ 和 $6$ 所有節點交換完畢，最大堆構建完成
圖10-9-建堆程序示意圖：
堆排序步驟：
1. 構建一個篩選演算法，該演算法可以把一個任意的排序碼序列建成一個堆，堆的第一個元素就是排序碼中最小的
2. 把選出的最小排序碼從堆中洗掉，對剩余的部分重新建堆，繼續選出其中的最小者
3. 直到剩余 $1$ 個元素時，排序結束

四、交換排序

交換排序：對待排序記錄兩兩進行排序碼比較，若不滿足排序順序，則交換這對排序碼

4.1 冒泡排序

冒泡排序演算法步驟：
1. 對所有記錄從左到右每相鄰兩個記錄的排序碼進行比較，如果這兩個記錄的排序碼不符合排序要求，則進行交換，這樣一趟做完，將排序碼最大者放在最后一個位置
2. 對剩下的 $n-1$ 個待排序記錄重復上述程序，又將一個排序碼放于最終位置，反復進行 $n-1$ 次，可將 $n-1$ 個排序碼對應的記錄放至最終位置，剩下的即為排序碼最小的記錄，它在第 $1$ 的位置處
3. 注：如果在某一趟中，沒有發生交換，則說明此時所有記錄已經按排序要求排列完畢，排序結束
圖10-10-冒泡排序演算法示意圖：

4.2 快速排序

快速排序演算法步驟（主要通過首尾指標的移動來劃分大于 $x$ 和小于 $x$ 的值）：
1. 從 $n$ 個待排序的記錄中任取一個記錄(不妨取第 $1$ 個記錄)
2. 設法將該記錄放置于排序后它最終應該放的位置，使它前面的記錄排序碼都不大于它的排序碼，而后面的記錄排序碼都大于它的排序碼
3. 然后對前、后兩部分待排序記錄重復上述程序，可以將所有記錄放于排序成功后的相應位置，排序即告完成
圖10-11-一次劃分的程序：

五、歸并排序

歸并排序演算法基本思路：一個待排序記錄構成的檔案，可以看作是有多個有序子檔案組成的，對有序子檔案通過若干次使用歸并的方法，得到一個有序檔案
歸并：把兩個（或多個）有序子表合并成一個有序表的程序
一次歸并：把一個陣列中兩個相鄰的有序陣列歸并為一個有序陣列段，其結果存盤于另一個陣列
一趟歸并：$n$ 個元素的陣列中，從第 $1$ 個元素開始，每連續 $len$ 個元素組成的陣列段是有序的，從第一個陣列段開始，每相鄰的兩個長度相等的有序陣列段進行一次歸并，一直到剩余元素個數小于 $2*len$時結束，如果剩余元素個數大于 $len$，可以對一個長度為 $len$，另一個長度小于 $len$ 的兩個有序陣列實行一次歸并；如果其個數小于 $len$，則把這些元素直接拷貝到目標陣列中
圖10-13-一趟歸并的圖示：
二路歸并排序演算法步驟：
1. 對任意一個待排序的檔案，初始時它的有序段的長度為 $1$
2. 通過不斷呼叫一趟歸并演算法，使有序段的長度不斷增加
3. 直到有序段的長度不小于待排序檔案的長度，排序結束
圖10-14-二路歸并排序程序示意圖：

六、基數排序

基數排序（又稱分配排序）：不對排序碼比較，而是借助于多排序碼排序的思想進行單排序嗎排序的方法

6.1 多排序碼的排序

注：每一張牌有兩個 “排序碼”：花色（梅花<方塊<紅心<黑桃）和面值（$2<3<\ldots<A$），且花色的地位高于面值，即面值相等的兩張牌，以花色大的為大，即在比較兩張牌的牌面大小時，先比較花色，若花色相同，則再比較面值
分配：把 $52$ 張撲克牌按面值分成 $13$ 堆，再按照不同的花色分成 $4$ 堆，分成若干堆的程序稱為分配
收集：第一次分配時，把面值不同的 $13$ 堆牌自小至大疊在一起，把不同花色的 $4$ 堆牌自小至大的次序合在一起，從若干堆自小到大疊在一起的程序稱為收集

6.2 靜態鏈式基數排序

靜態鏈式基數排序步驟：
1. 先用靜態鏈表存盤待排序檔案中的 $n$ 個記錄，表中每一個結點對應一個記錄
2. 第一趟對低位排序碼（個位數）進行分配，將 $n$ 個結點分配到序號分別為 $0-9$ 的 $10$ 個鏈式佇列中，用 $f[i]$ 和 $e[i]$ 分別作為第 $i$ 個佇列的隊首和隊尾指標
3. 第一趟收集程序中把這個 $10$ 個佇列中非空的佇列依次合并在一起產生一個新的靜態單鏈表
4. 對這個新的靜態單鏈表按十位數進行分配和采集，然后再依次對百位數、千位數直到最高位數反復進行這樣的分配和收集操作，排序結束
圖10-15-靜態鏈式技術排序示意圖：

七、各種內部排序演算法的比較（書中未給出）

排序方法	比較次數（最好）	比較次數（最差）	移動次數（最好）	移動次數（最差）	穩定性
直接插入排序	$n$	$n^2$	$0$	$$n^2$$	$√$
折半插入排序	$nlog_2n$	$nlog_2n$	$0$	$n^2$	$√$
冒泡排序	$n$	$n^2$	$0$	$n^2$	$√$
快速排序	$nlog_2n$	$n^2$	$nlog_2n$	$n^2$	$×$
簡單選擇排序	$n^2$	$n^2$	$0$	$n$	$×$
堆排序	$nlog_2n$	$nlog_2n$	$$nlog_2n$$	$nlog_2n$	$×$
歸并排序	$nlog_2n$	$nlog_2n$	$nlog_2n$	$nlog_2n$	$√$
基數排序	$O(b(n+rd))$	$O(b(n+rd))$			$√$

上表基數排序中：$rd$ 是收集程序和各位排序碼的取值范圍中值的個數（十進制為 $10$）；靜態鏈式基數排序要進行 $b$ 唐收集和分配

八、內部排序演算法的應用（書中未給出）

九、演算法設計題

十、錯題集

下列說法錯誤的是：基數排序適合實型資料的排序
插入排序演算法在最后一趟開始之前，所有的元素可能都不在其最終的位置上（比如最后一個需要插入的元素是最小的元素）
一個序列中有 $10000$ 個元素，若只想得到其中前 $10$ 個最小元素，最好采用堆排序演算法
排序的趟數和待排序元素的原始狀態有關的排序演算法是冒泡排序
快速排序演算法和冒泡排序演算法都會出現起泡的現象

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/155599.html

標籤：其他

上一篇：請問dragonboard 410c的android原始碼有沒有好的下載方法

下一篇：冷月手撕408之作業系統(12)-記憶體的分配與回收連續存盤管理

排序方法	比較次數（最好）	比較次數（最差）	移動次數（最好）	移動次數（最差）	穩定性
直接插入排序	\(n\)	\(n^2\)	\(0\)	$$n^2$$	\(√\)
折半插入排序	\(nlog_2n\)	\(nlog_2n\)	\(0\)	\(n^2\)	\(√\)
冒泡排序	\(n\)	\(n^2\)	\(0\)	\(n^2\)	\(√\)
快速排序	\(nlog_2n\)	\(n^2\)	\(nlog_2n\)	\(n^2\)	\(×\)
簡單選擇排序	\(n^2\)	\(n^2\)	\(0\)	\(n\)	\(×\)
堆排序	\(nlog_2n\)	\(nlog_2n\)	$$nlog_2n$$	\(nlog_2n\)	\(×\)
歸并排序	\(nlog_2n\)	\(nlog_2n\)	\(nlog_2n\)	\(nlog_2n\)	\(√\)
基數排序	\(O(b(n+rd))\)	\(O(b(n+rd))\)			\(√\)

第10章 內排序

第10章 內排序

一、排序的基本概念

1.1 排序演算法的記錄存盤結構定義

二、插入排序

2.1 直接插入排序

2.1.1 直接插入排序演算法（演算法）

2.2 二分法（折半）插入排序

2.3 表插入排序（大綱未規定）

2.4 希爾（Shell）插入排序

三、選擇排序

3.1 直接選擇排序

3.1.1 直接選擇排序演算法（演算法）

3.2 樹型選擇排序（大綱未規定）

3.3 堆排序

四、交換排序

4.1 冒泡排序

4.2 快速排序

五、歸并排序

六、基數排序

6.1 多排序碼的排序

6.2 靜態鏈式基數排序

七、各種內部排序演算法的比較（書中未給出）

八、內部排序演算法的應用（書中未給出）

九、演算法設計題

十、錯題集

第10章內排序

第10章內排序