內(nèi)部排序

10.1 概述

排序 ：將一組雜亂無(wú)章的數(shù)據(jù)按一定規(guī)律順次排列起來(lái)。即，將無(wú)序序列排成一個(gè)有序序列 (由小到大或由大到小) 的運(yùn)算。

如果參加排序的數(shù)據(jù)結(jié)點(diǎn)包含多個(gè)數(shù)據(jù)域，那么排序往往是針對(duì)其中某個(gè)域而言。

排序方法分類 ：

• 按數(shù)據(jù)存儲(chǔ)介質(zhì): 內(nèi)部排序和外部排序

  • 內(nèi)部排序：數(shù)據(jù)量不大、數(shù)據(jù)在內(nèi)存，無(wú)需內(nèi)外存交換數(shù)據(jù)
  • 外部排序：數(shù)據(jù)量較大、數(shù)據(jù)在外存(文件排序) —— 外部排序時(shí)，要將數(shù)據(jù)分批調(diào)入內(nèi)存來(lái)排序，中間結(jié)果還要及時(shí)放入外存

• 按比較器個(gè)數(shù): 串行排序和并行排序

  • 串行排序：單處理機(jī)(同一時(shí)刻比較一對(duì)元素)
  • 并行排序：多處理機(jī)(同一時(shí)刻比較多對(duì)元素)

• 按主要操作: 比較排序和基數(shù)排序

  • 比較排序：用比較的方法 —— 插入排序、交換排序、選擇排序、歸并排序
  • 基數(shù)排序：不比較元素的大小，僅僅根據(jù)元素本身的取值確定其有序位置。

• 按輔助空間: 原地排序和非原地排序

  • 原地排序：輔助空間用量為O(1)的排序方法(所占的輔助存儲(chǔ)空間與參加排序的數(shù)據(jù)量大小無(wú)關(guān))·
  • 非原地排序：輔助空間用量超過(guò)O(1的排序方法(所占的輔助存儲(chǔ)空間與參加排序的數(shù)據(jù)量大小有關(guān))·

• 按穩(wěn)定性: 穩(wěn)定排序和非穩(wěn)定排序

  • 穩(wěn)定排序：能夠使任何數(shù)值相等的元素，排序以后相對(duì)次序不變。例如：直接插入排序

  • 非穩(wěn)定性排序：數(shù)值相等的元素，排序以后相對(duì)次序改變。例如：簡(jiǎn)單選擇排序

    排序方法是否穩(wěn)定，并不能衡量一個(gè)排序算法的優(yōu)劣。

• 按自然性: 自然排序和非自然排序

  • 自然排序：輸入數(shù)據(jù)越有序排序的速度越快的排序方法。
  • 非自然排序：輸入數(shù)據(jù)越有序排序的速度慢的排序方法。

存儲(chǔ)結(jié)構(gòu) ：

• 順序表存儲(chǔ)：待排序的一組記錄存放在地址連續(xù)的一組存儲(chǔ)單元上。記錄之間的次序關(guān)系由其存儲(chǔ)位置決定，則實(shí)現(xiàn)排 序必須借助移動(dòng)記錄

  # define MAXSIZE 20     // 設(shè)記錄不超過(guò)20個(gè)
  typedef int KeyType;    // 設(shè)關(guān)鍵字為int型typedef struct {         //定義每個(gè)記錄(數(shù)據(jù)元素)的結(jié)構(gòu)KeyType key;         //關(guān)鍵字//InfoType otherinfo;  //其它數(shù)據(jù)項(xiàng)
  }RedType;typedef struct {   // 定義順序表結(jié)構(gòu)RedType r[MAXSIZE + 1]; //r[0]作為緩沖區(qū)或哨兵int length; //順序表的長(zhǎng)度
  }SqList;
  

• 鏈表存儲(chǔ)：待排序記錄存放在靜態(tài)鏈表中，記錄之間的次序關(guān)系由 指針指示，則實(shí)現(xiàn)排序不需要移動(dòng)記錄，僅需修改指針即可；

• 地址存儲(chǔ)：待排序記錄本身存儲(chǔ)在一組地址連續(xù)的存儲(chǔ)單元內(nèi)，同時(shí)另設(shè)一個(gè)指示各個(gè)記錄存儲(chǔ)位置的地址向量，在排序過(guò) 程中不移動(dòng)記錄本身，而移動(dòng)地址向量中這些記錄的“地址",在排序結(jié)束之后再按照地址向量中的值調(diào)整記錄的存儲(chǔ)位置。

10.2 插入排序

插入排序：

在有序序列中插入一個(gè)元素，保持序列有序，有序長(zhǎng)度不斷增加。

有序插入方法：

• 在插入a[i]前，數(shù)組a的前半段(a[0]~a[i-1])是有序段, 后半段(a[i]~a[n-1])是停留于輸入次序的“無(wú)序段“
• 插入a[i]使a[0]~a[i-1]有序，也就是要為a[i]找到有序位置j (0≤j≤i) ,將a[i]插入在a[j]的位置上。

根據(jù)找插入位置方法不同分為：

• 順序法定位插入位置：直接插入排序
• 二分法定位插入位置：二分插入排序
• 縮小增量多遍插入排序：希爾排序

10.2.1 直接插入排序

實(shí)現(xiàn)排序的基本操作有兩個(gè):

? (1) “比較”序列中兩個(gè)關(guān)鍵字的大小;

? (2) “移動(dòng)”記錄。

#include<stdio.h># define MAXSIZE 20     // 設(shè)記錄不超過(guò)20個(gè)
typedef int KeyType;    // 設(shè)關(guān)鍵字為int型typedef struct {         //定義每個(gè)記錄(數(shù)據(jù)元素)的結(jié)構(gòu)KeyType key;         //關(guān)鍵字
}RedType;typedef struct {   // 定義順序表結(jié)構(gòu)RedType r[MAXSIZE + 1]; //r[0]作為緩沖區(qū)或哨兵int length; //順序表的長(zhǎng)度
}SqList;void InsertSort(SqList* L)
{int i, j;for (i = 2; i <= L->length; i++){if (L->r[i].key < L->r[i - 1].key) //后面比前面數(shù)小，則需要進(jìn)行排序{L->r[0] = L->r[i]; // 復(fù)制插入元素到哨兵//記錄后移，尋找插入位置L->r[i] = L->r[i - 1];for (j = i - 2; L->r[0].key < L->r[j].key; j--){L->r[j + 1] = L->r[j];}//插人到正確位置L->r[j + 1] = L->r[0];}//后面數(shù)大于等于前面數(shù)，只需繼續(xù)循環(huán)，比較下一個(gè)數(shù)}
}int main()
{int i;int r[7] = {32,12,24,5,16,43,20};SqList L;L.length = 7;for (i = 0; i < 7; i++){L.r[i + 1].key = r[i];}InsertSort(&L);for (i = 0; i < 7; i++){printf("%d ", L.r[i + 1].key);}return 0;
}

n個(gè)元素

最好情況：順序有序

• 比較次數(shù)：$$\sum _{i=2}^{n}1=n?1$$
• 移動(dòng)次數(shù)：0
• 時(shí)間復(fù)雜度 O(n)

最壞情況：逆序有序

• 比較次數(shù)（平均值）：$$\sum _{i=2}^{n}i=\frac{(n+2)(n?1)}{2}$$

• 移動(dòng)次數(shù)（平均值）：$$\sum _{i=2}^n(i+1)=\frac{(n+4)(n?1)}{2}$$

• 時(shí)間復(fù)雜度 O(n²)

平均情況：

• 比較次數(shù)（平均值）：$$\sum _{i=2}^n\frac{i+1}{2}=\frac{(n+2)(n?1)}{4}$$
• 移動(dòng)次數(shù)（平均值）：$$\sum _{i=2}^n(\frac{i+1}{2}+1)=\frac{(n+6)(n?1)}{4}$$
• 時(shí)間復(fù)雜度 O(n²) - 最壞的情況的一半

空間復(fù)雜度：O(1)

穩(wěn)定性：穩(wěn)定

原始數(shù)據(jù)越接近有序，排序速度越快

10.2.2 其他插入排序

10.2.2.1 折半插入排序(Binary Insertion Sort)

插入排序的基本操作是在一個(gè)有序表中進(jìn)行查找和插入，這個(gè)==“查找“操作可利用“折半查找”==來(lái)實(shí)現(xiàn)，再進(jìn)行插入，則稱之為折半插入排序(Binary Insertion Sort)

#include<stdio.h># define MAXSIZE 20     // 設(shè)記錄不超過(guò)20個(gè)
typedef int KeyType;    // 設(shè)關(guān)鍵字為int型typedef struct {         //定義每個(gè)記錄(數(shù)據(jù)元素)的結(jié)構(gòu)KeyType key;         //關(guān)鍵字
}RedType;typedef struct {   // 定義順序表結(jié)構(gòu)RedType r[MAXSIZE + 1]; //r[0]作為緩沖區(qū)或哨兵int length; //順序表的長(zhǎng)度
}SqList;void BInsertSort(SqList* L)
{int i, j;for (i = 2; i <= L->length; i++){L->r[0] = L->r[i]; // 復(fù)制插入元素到哨兵int low = 1;int high = i - 1;while (low <= high) { //在 r[low.. high]中折半查找有序插入的位置int m = (low + high) / 2; // 折半if (L->r[0].key < L->r[m].key) //插入點(diǎn)在低半?yún)^(qū){high = m - 1;}else { //插入點(diǎn)在高半?yún)^(qū)low = m + 1;}}//循環(huán)結(jié)束，high+1 則為插入位置for (j = i - 1; j>=high+1; j--){L->r[j + 1] = L->r[j]; //記錄后移}L->r[high + 1] = L->r[0]; // 插入}
}int main()
{int i;int r[7] = {32,12,24,5,16,43,20};SqList L;L.length = 7;for (i = 0; i < 7; i++){L.r[i + 1].key = r[i];}BInsertSort(&L);for (i = 0; i < 7; i++){printf("%d ", L.r[i + 1].key);}return 0;
}

折半插入排序特點(diǎn)：

• 折半查找比順序查找快，
• 關(guān)鍵碼比較次數(shù)與待排座對(duì)象序列的初始排列無(wú)關(guān)，僅依賴于對(duì)象個(gè)數(shù)。
• 當(dāng)n較大時(shí)，總關(guān)鍵碼比較次數(shù)比直接插入排序的最壞情況要好得多，但比其最好情況要差;
• 在對(duì)象的初始排列已經(jīng)按關(guān)鍵碼排好序或接近有序時(shí)，直接插入排序比折半插入排序執(zhí)行的關(guān)鍵碼比較次數(shù)要少;
• 平均性能優(yōu)于直接插入排序

n個(gè)元素

折半插入排序僅減少了關(guān)鍵字間的比較次數(shù)，而記錄的移動(dòng)次數(shù)不變

時(shí)間復(fù)雜度：仍為O(n²)，

空間復(fù)雜度：O(1)

穩(wěn)定性：穩(wěn)定

10.2.2.2 2-路插入排序（Two-Way Insertion Sort）

2- 路插入排序是在折半插入排序的基礎(chǔ)上再改進(jìn)之，其目的是減少排序過(guò)程中移動(dòng) 記錄的次數(shù)，但為此需要n個(gè)記錄的輔助空間。

• 初始化一個(gè)與原數(shù)組一樣大小的輔助數(shù)組d，并將原數(shù)組的第一個(gè)元素放入輔助數(shù)組的第一個(gè)位置。
• 將d看成是一個(gè)循環(huán)向量,并設(shè)兩個(gè)指針 first 和 final分別指示排序過(guò)程中得到的有序序列中的第一個(gè)和最后一個(gè)記錄在d中的位置。
• 從第二個(gè)元素開(kāi)始遍歷原數(shù)組，對(duì)于每個(gè)待排序元素：
  • 如果待排序元素小于輔助數(shù)組的最小值，則通過(guò)移動(dòng)first將其插入到最小值之前。
  • 如果待排序元素大于輔助數(shù)組的最大值，則過(guò)移動(dòng)final將其插入到最大值之后。
  • 否則，通過(guò)移動(dòng)final將大于的數(shù)值向后移動(dòng)并將待排序元素插入到適當(dāng)?shù)奈恢谩?/li>
• 處理完所有元素后，將輔助數(shù)組中的元素復(fù)制回原數(shù)組，完成排序。

#include<stdio.h>
#include<stdlib.h>#define MAXSIZE 20     // 設(shè)記錄不超過(guò)20個(gè)
typedef int KeyType;    // 設(shè)關(guān)鍵字為int型typedef struct {         //定義每個(gè)記錄(數(shù)據(jù)元素)的結(jié)構(gòu)KeyType key;         //關(guān)鍵字
}RedType;typedef struct {   // 定義順序表結(jié)構(gòu)RedType r[MAXSIZE + 1]; //r[0]作為緩沖區(qū)或哨兵int length; //順序表的長(zhǎng)度
}SqList;void TwoWayInsertSort(SqList* L) {/* 初始化一個(gè)與原數(shù)組一樣大小的輔助數(shù)組 */RedType* d;d = (RedType*)malloc((L->length) * sizeof(RedType));if (d == NULL) {return;}/* 設(shè)L的第1個(gè)記錄為d中排好序的記錄(在位置[0]) */d[0] = L->r[1];/* first、final分別指示d中排好序的記錄的第1個(gè)和最后1個(gè)記錄的位置 */int first, final;first = final = 0;int i, j;/* 依次將L的第2個(gè)～最后1個(gè)記錄插入d中 */for (i = 2; i <= L->length; i++) {if (L->r[i].key < d[first].key) {/* 待插記錄小于d中最小值，插到d[first]之前(不需移動(dòng)d數(shù)組的元素) */first = (first - 1 + L->length) % L->length;d[first] = L->r[i];}else if (L->r[i].key > d[final].key) {/* 待插記錄大于d中最大值，插到d[final]之后(不需移動(dòng)d數(shù)組的元素) */final++;d[final] = L->r[i];}else {/* 待插記錄大于d中最小值，小于d中最大值，插到d的中間(需要移動(dòng)d數(shù)組的元素) */j = final++;while (L->r[i].key < d[j].key){d[(j + 1) % L->length] = d[j];j = (j - 1 + L->length) % L->length;}d[j + 1] = L->r[i];}}for (i = 1; i <= L->length; i++) { // 修改循環(huán)條件L->r[i] = d[i - 1]; // 將排序后的元素放回L中}for (i = 1; i <= L->length; i++) { // 輸出排序后的Lprintf("%d ", L->r[i].key);}printf("\n");printf("在L中first: %d \n", first + 1);printf("在L中final: %d ", final + 1);free(d); // 釋放內(nèi)存
}int main() {int i;int r[8] = { 49,38,65,97,76,13,27,49 };SqList L;L.length = 8;for (i = 1; i <= L.length; i++) {L.r[i].key = r[i - 1];}TwoWayInsertSort(&L);return 0;
}

n個(gè)元素

?時(shí)間復(fù)雜度?：2-路插入排序的時(shí)間復(fù)雜度為O(n²)，移動(dòng)次數(shù)大約為n²/8次，盡管減少了移動(dòng)次數(shù)，但并不能完全避免移動(dòng)操作。

?空間復(fù)雜度?：需要額外的輔助數(shù)組，空間復(fù)雜度為O(n)。

10.2.2.3 表插入排序（Table Insertion Sort）

在排序過(guò)程中不移動(dòng)記 錄，只有改變存儲(chǔ)結(jié)構(gòu)

算法思路：

• 初始化表頭結(jié)點(diǎn)：設(shè)數(shù)組中下標(biāo)為"0"的分量為表頭結(jié)點(diǎn)，并令表頭結(jié)點(diǎn)記錄的關(guān)鍵字取最大整數(shù) MAXINT
• 表插入排序的過(guò)程：
  • 首先將靜態(tài)鏈表中數(shù)組下標(biāo)為"1"的分量（結(jié)點(diǎn)）和表頭結(jié)點(diǎn)構(gòu)成一個(gè)循環(huán)鏈表
  • 然后依次將下標(biāo)為"2"至"n"的分量（結(jié)點(diǎn)）按記錄關(guān)鍵字非遞減有序插人到循環(huán)鏈表中

#include<stdio.h>
#include<limits.h>#define MAXSIZE 20     // 設(shè)記錄不超過(guò)20個(gè)
#define MAXVALUE INT_MAX  // 定義最大值typedef struct SLNode {int data;  // 存儲(chǔ)數(shù)據(jù)int link;  // 存儲(chǔ)指向下一個(gè)元素的索引
}SLNode, Table[MAXSIZE];void TableInsertSort(Table* tb, int n)
{//與第一個(gè)數(shù)據(jù)元素構(gòu)成循環(huán)列表(*tb)[0].link = 1;  // 初始化順序表的頭結(jié)點(diǎn)，將其link指向第一個(gè)數(shù)據(jù)元素int p, q; // 用于在排序過(guò)程中存儲(chǔ)當(dāng)前元素和前驅(qū)元素的索引for (int i = 2; i < n; i++) // 從第二個(gè)元素開(kāi)始遍歷{p = (*tb)[0].link; q = 0;while (p != 0 && (*tb)[p].data <= (*tb)[i].data){q = p; //q是p的前驅(qū)p = (*tb)[p].link; // p更新為下一個(gè)元素的索引}(*tb)[i].link = (*tb)[q].link; // 將i插入到q的后面(*tb)[q].link = i; // 更新q的link，使其指向i}
}int main() {int i;int r[9] = { 0,49,38,65,97,76,13,27,49 };Table tb;// 初始化表頭結(jié)點(diǎn)：tb[0].data = MAXVALUE;tb[0].link = 0;for (i = 1; i < 9; i++){tb[i].data = r[i];tb[i].link = 0;}TableInsertSort(&tb, 9);for (i = 0; i < 9; i++){if (tb[i].data == MAXVALUE){printf("%c ", 'M');continue;}printf("%d ", tb[i].data);}printf("\n");for (i = 0; i < 9; i++){printf("%d ", tb[i].link);}return 0;
}

10.2.3 希爾排序(Shell’s Sort)

又稱“縮小增量排序"(Diminishing Increment Sort)

基本思想： 先將整個(gè)待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排 序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。

• 選擇一個(gè)增量序列 D_k：D_M > D_M-1 > … > D₁ = 1 必須遞減
• 對(duì)每個(gè)D_k進(jìn)行“D_k-間隔”插入排序（K= M，M-1，…1）

#include<stdio.h>
#include<stdlib.h>#define MAXSIZE 20     // 設(shè)記錄不超過(guò)20個(gè)
typedef int KeyType;    // 設(shè)關(guān)鍵字為int型typedef struct {         //定義每個(gè)記錄(數(shù)據(jù)元素)的結(jié)構(gòu)KeyType key;         //關(guān)鍵字
}RedType;typedef struct {   // 定義順序表結(jié)構(gòu)RedType r[MAXSIZE + 1]; //r[0]作為緩沖區(qū)或哨兵int length; //順序表的長(zhǎng)度
}SqList;void ShellInsert(SqList* L, int dk)
{int i, j;for (i = dk + 1; i <= L->length; i++)// 從第dk+1個(gè)元素開(kāi)始向后遍歷順序表{ if (L->r[i].key < L->r[i - dk].key)// 如果當(dāng)前元素的key小于它dk位置前的元素的key{            L->r[0] = L->r[i];// L->r[0]是暫存單元，暫存當(dāng)前元素for (j = i - dk; j > 0 && (L->r[0].key < L->r[j].key); j = j - dk){// 從當(dāng)前元素向前遍歷，步長(zhǎng)為dkL->r[j + dk] = L->r[j]; // 將比暫存元素大的元素向后移動(dòng)dk個(gè)位置}L->r[j + dk] = L->r[0]; // 將暫存的元素插入到正確的位置}}
}void ShellSort(SqList *L, int dlta[], int t) 
{int i, k;for (k = 0; k < t; k++){ShellInsert(L, dlta[k]);printf("\n第 D%d 增量序列排序結(jié)果：\n", dlta[k]);for (i = 1; i <= 13; i++){printf("%d ", L->r[i].key);}}
}int main() {int i;int r[13] = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };SqList L;L.length = 13;for (i = 1; i <= L.length; i++) {L.r[i].key = r[i - 1];}// 增量序列int dlta[3] = { 5,3,1 };ShellSort(&L, dlta, 3);printf("\n-----------------\n");printf("排序結(jié)果：\n");for (i = 1; i <= 13; i++){printf("%d ", L.r[i].key);}return 0;
}

希爾排序算法效率與增量序列的取值有關(guān)：

Hibbard增量序列

• D_k = 2 ^k-1 —— 相鄰元素互質(zhì)
• 最壞: T_worst = O(n^3/2)
• 猜想: T_avg = O(n^5/4)

Sedgewick增量序列

• {1,5,19,41,109,……} —— 9 * 4ⁱ - 9 * 2ⁱ + 1 或 4ⁱ - 3 * 2ⁱ + 1
• 最壞: T_worst = O(n^4/3)
• 猜想: T_avg = O(n^7/6)

穩(wěn)定性：不穩(wěn)定

時(shí)間復(fù)雜度：O(n^1.25) ~ O(1.6n^1.25) – 經(jīng)驗(yàn)公式

? 最好：O(n)

? 最壞：O(n²)

? 最好：~O(n^1.3)

空間復(fù)雜度：O(1)

不宜在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)

10.3 交換排序

交換排序：兩兩比較，如果發(fā)生逆序則交換，直到所有記錄都排好序?yàn)橹埂?/p>

10.3.1 冒泡排序(Bubble Sort)

基本思想: 每趟不斷將記錄兩兩比較，并按“前小后大”規(guī)則交換

#include<stdio.h>
#include<stdlib.h>#define MAXSIZE 20     // 設(shè)記錄不超過(guò)20個(gè)
typedef int KeyType;    // 設(shè)關(guān)鍵字為int型typedef struct {         //定義每個(gè)記錄(數(shù)據(jù)元素)的結(jié)構(gòu)KeyType key;         //關(guān)鍵字
}RedType;typedef struct {   // 定義順序表結(jié)構(gòu)RedType r[MAXSIZE + 1]; //r[0]作為緩沖區(qū)或哨兵int length; //順序表的長(zhǎng)度
}SqList;void bubble_sort(SqList *L) 
{int i, j;RedType x; // 交換時(shí)臨時(shí)存儲(chǔ)for (i = 1; i <= L->length - 1; i++) // 需要比較i趟，n個(gè)記錄 總共n-1趟{for (j = 1; j <= L->length - i; j++) // 每一趟需要比較的次數(shù)，n個(gè)記錄，比較n-i次{if (L->r[j].key > L->r[j + 1].key) // 比較 {//發(fā)生逆序 - 交換x = L->r[j]; L->r[j] = L->r[j + 1];L->r[j + 1] = x;}}printf("\n第 %d 趟排序結(jié)果：\n", i);for (j = 1; j <= L->length; j++){printf("%d ", L->r[j].key);}}
}int main() {int i;int r[13] = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };SqList L;L.length = 13;for (i = 1; i <= L.length; i++) {L.r[i].key = r[i - 1];}bubble_sort(&L);printf("\n-----------------\n");printf("排序結(jié)果：\n");for (i = 1; i <= 13; i++){printf("%d ", L.r[i].key);}return 0;
}

改進(jìn)：冒泡處理過(guò)程中，沒(méi)有進(jìn)行任何交換，說(shuō)明序列已有序，則停止交換

#include<stdio.h>
#include<stdlib.h>#define MAXSIZE 20     // 設(shè)記錄不超過(guò)20個(gè)
typedef int KeyType;    // 設(shè)關(guān)鍵字為int型typedef struct {         //定義每個(gè)記錄(數(shù)據(jù)元素)的結(jié)構(gòu)KeyType key;         //關(guān)鍵字
}RedType;typedef struct {   // 定義順序表結(jié)構(gòu)RedType r[MAXSIZE + 1]; //r[0]作為緩沖區(qū)或哨兵int length; //順序表的長(zhǎng)度
}SqList;void bubble_sort(SqList *L) 
{int i, j;int flag = 1;RedType x; // 交換時(shí)臨時(shí)存儲(chǔ)for (i = 1; (i <= L->length - 1) && (flag == 1); i++) // 需要比較i趟，n個(gè)記錄 總共n-1趟{flag = 0;for (j = 1; j <= L->length - i; j++) // 每一趟需要比較的次數(shù)，n個(gè)記錄，比較n-i次{if (L->r[j].key > L->r[j + 1].key) // 比較 {flag = 1;//發(fā)生逆序 - 交換x = L->r[j]; L->r[j] = L->r[j + 1];L->r[j + 1] = x;}}printf("\n第 %d 趟排序結(jié)果：\n", i);printf("flag = %d \n", flag);for (j = 1; j <= L->length; j++){printf("%d ", L->r[j].key);}}
}int main() {int i;int r[13] = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };SqList L;L.length = 13;for (i = 1; i <= L.length; i++) {L.r[i].key = r[i - 1];}bubble_sort(&L);printf("\n-----------------\n");printf("排序結(jié)果：\n");for (i = 1; i <= 13; i++){printf("%d ", L.r[i].key);}return 0;
}

最好情況：正序

• 比較次數(shù)：n-1
• 移動(dòng)次數(shù)：0
• 時(shí)間復(fù)雜度 O(n)

最壞情況：逆序

• 比較次數(shù)（平均值）：$$\sum _{i=1}^{n?1}(n?i)=\frac{(n^2?n)}{2}$$

• 移動(dòng)次數(shù)（平均值）：$$3\sum _{i=1}^{n?1}(n?i)=\frac{3(n^2?n)}{2}$$

• 時(shí)間復(fù)雜度 O(n²)

平均情況：

• 時(shí)間復(fù)雜度 O(n²)

空間復(fù)雜度：O(1)

穩(wěn)定性：穩(wěn)定

10.3.2 快速排序(Quick Sort)

基本思想:

• 任取一個(gè)元素 (如:第一個(gè)) 為中心pivot - 可以是第一個(gè)數(shù)、最后一個(gè)數(shù)、最中間一個(gè)數(shù)、任選一個(gè)數(shù)等

• 所有比它小的元素一律前放，比它大的元素一律后放形成左右兩個(gè)子表;

• 對(duì)各子表重新選擇中心元素并依此規(guī)則調(diào)整 【遞歸思想】

• 直到每個(gè)子表的元素只剩一個(gè)

#include<stdio.h>
#include<stdlib.h>#define MAXSIZE 20     // 設(shè)記錄不超過(guò)20個(gè)
typedef int KeyType;    // 設(shè)關(guān)鍵字為int型typedef struct {         //定義每個(gè)記錄(數(shù)據(jù)元素)的結(jié)構(gòu)KeyType key;         //關(guān)鍵字
}RedType;typedef struct {   // 定義順序表結(jié)構(gòu)RedType r[MAXSIZE + 1]; //r[0]作為緩沖區(qū)或哨兵int length; //順序表的長(zhǎng)度
}SqList;int Partition(SqList* L, int low, int high)
{int pivotkey = L->r[low].key; //任取一個(gè)元素 (第一個(gè)) 為中心pivotL->r[0] = L->r[low];  // 將中心pivot放到0處while (low < high){while (low < high && L->r[high].key >= pivotkey) // high >= 中心  ，移動(dòng)high向前{--high;}L->r[low] = L->r[high]; //high < 中心, 把該值移動(dòng)到low那一側(cè)while (low < high && L->r[low].key <= pivotkey)// low <= 中心  ，移動(dòng)low向后{++low;}L->r[high] = L->r[low];//low > 中心, 把該值移動(dòng)到high那一側(cè)}L->r[low] = L->r[0]; // 中心放到對(duì)應(yīng)位置return low;
}void QSort(SqList *L, int low, int high) 
{if (low < high)//長(zhǎng)度大于1{int pivotloc = Partition(L, low, high); //將L.r[low .. high]一分為二printf("low = %d, high = %d, pivotloc = %d\n", low, high, pivotloc);for (int i = 1; i <= 13; i++){printf("%d ", L->r[i].key);}printf("\n-----------------\n");QSort(L, low, pivotloc - 1); //對(duì)低子表遞歸排序QSort(L, pivotloc + 1, high);  //對(duì)高子表遞歸排序，}
}int main() {int i;int r[13] = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };SqList L;L.length = 13;for (i = 1; i <= L.length; i++) {L.r[i].key = r[i - 1];}QSort(&L,1, L.length);printf("排序結(jié)果：\n");for (i = 1; i <= 13; i++){printf("%d ", L.r[i].key);}return 0;
}

劃分元素的選取是影響時(shí)間性能的關(guān)鍵

最好情況：

• 時(shí)間復(fù)雜度 O(nlogn)

最壞情況：

• 時(shí)間復(fù)雜度 O(n²)

平均情況：

• 時(shí)間復(fù)雜度：O(nlogn)

? QSort()：O(logn)

? Partition()：O(n)

空間復(fù)雜度：

? 平均情況：O(logn)

? 最壞情況：O(n)

穩(wěn)定性：不穩(wěn)定

快速排序不適于對(duì)原本有序或基本有序（包括正序和逆序）的記錄序列進(jìn)行排序，退化成冒泡排序

10.4 選擇排序

10.4.1 簡(jiǎn)單選擇排序(Simple Selection Sort)

基本思想： 在待排序的數(shù)據(jù)中選出最大(小)的元素放在其最終的位置。

基本操作:

• 首先通過(guò)n-1次關(guān)鍵字比較，從n個(gè)記錄中找出關(guān)鍵字最小的記錄，將它與第一個(gè)記錄交換
• 再通過(guò)n-2次比較，從剩余的n-1個(gè)記錄中找出關(guān)鍵字次小的記錄，將它與第二個(gè)記錄交換
• 重復(fù)上述操作，共進(jìn)行n-1趟排序后，排序結(jié)束

#include<stdio.h>
#include<stdlib.h>#define MAXSIZE 20     // 設(shè)記錄不超過(guò)20個(gè)
typedef int KeyType;    // 設(shè)關(guān)鍵字為int型typedef struct {         //定義每個(gè)記錄(數(shù)據(jù)元素)的結(jié)構(gòu)KeyType key;         //關(guān)鍵字
}RedType;typedef struct {   // 定義順序表結(jié)構(gòu)RedType r[MAXSIZE + 1]; //r[0]作為緩沖區(qū)或哨兵int length; //順序表的長(zhǎng)度
}SqList;void SelectSort(SqList* L)
{int i, j, k;for (i = 1; i < L->length; i++){k = i; for (j = i + 1; j <= L->length; j++){if (L->r[j].key < L->r[k].key){k = j;}}if (k != i){L->r[0] = L->r[k];L->r[k] = L->r[i];L->r[i] = L->r[0];}printf("\n第 %d 次排序結(jié)果：\n", i);for (j = 1; j <= L->length; j++){printf("%d ", L->r[j].key);}}
}int main() {int i;int r[13] = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };SqList L;L.length = 13;for (i = 1; i <= L.length; i++) {L.r[i].key = r[i - 1];}SelectSort(&L);printf("\n-----------------\n");printf("排序結(jié)果：\n");for (i = 1; i <= 13; i++){printf("%d ", L.r[i].key);}return 0;
}

時(shí)間復(fù)雜度 - O(n²)：

• 移動(dòng)次數(shù)

  • 最好情況：0
  • 最壞情況：3(n-1)

• 比較次數(shù)：

  • 最好情況：O(n²)
  • 最壞情況：O(n²)
  • 平均情況：O(n²)

  $$\sum _{i=1}^{n?1}(n?i)=\frac{n(n?1)}{2}$$

空間復(fù)雜度：O(1)

穩(wěn)定性：不穩(wěn)定

10.4.2 樹(shù)形選擇排序(Tree Selection Sort)

又稱錦標(biāo)賽排序(Tournament Sort)

基本思想： 首先對(duì)n個(gè)記錄的關(guān)鍵字進(jìn)行兩兩比較，然后在 其中? n / 2?個(gè)較小者之間再進(jìn)行兩兩比較，如此重復(fù)，直至選出最小關(guān)鍵字的記錄為止。

10.4.3 堆排序(Heap Sort)

若n個(gè)元素的序列{a₁，a₂,…, a_n}滿足 a_i ≤ a_2i && a_i ≤ a_2i+1 則稱該序列為小根堆

若n個(gè)元素的序列{a₁，a₂,…, a_n}滿足 a_i ≥ a_2i && a_i ≥ a_2i+1 則稱該序列為大根堆

從堆的定義可以看出，堆實(shí)質(zhì)是滿足如下性質(zhì)的完全二叉樹(shù):二又樹(shù)中任一非葉子結(jié)點(diǎn)均小于(大于)它的孩子結(jié)點(diǎn)

堆排序: 若在輸出堆頂?shù)淖钚≈?最大值)后，使得剩余n-1個(gè)元素的序列重又建成一個(gè)堆，則得到n個(gè)元素的次小值(次大值)…如此反復(fù)，便能得到一個(gè)有序序列?！径秧斁褪亲钚≈?最大值)，每次都取堆頂，就可得到一個(gè)有序序列】

堆序列需解決兩個(gè)問(wèn)題：

• 如何由無(wú)序序列建成一個(gè)堆?

  1. 單結(jié)點(diǎn)的二又樹(shù)是堆

  2. 在完全二叉樹(shù)中所有以葉子結(jié)點(diǎn)(序號(hào)i>n/2【最后一個(gè)結(jié)點(diǎn)是n，那么他的雙親是n/2，所以葉子結(jié)點(diǎn)是 > n/2】)為根的子樹(shù)是堆。

  3. 只需依次將以序號(hào)為n/2，n/2 - 1，… 1的結(jié)點(diǎn)為根的子樹(shù)均調(diào)整為堆即可。

  

• 如何在輸出堆頂元素后，調(diào)整剩余元素為一個(gè)新的堆?

  ? 小根堆:

  1. 輸出堆頂元素之后，以堆中最后一個(gè)元素【編號(hào)最大的元素】替代之;

  2. 然后將根結(jié)點(diǎn)值與左、右子樹(shù)的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者進(jìn)行交換，

  3. 重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過(guò)程為“篩選

  

#include<stdio.h>
#include<stdlib.h>#define MAXSIZE 20     // 設(shè)記錄不超過(guò)20個(gè)
typedef int KeyType;    // 設(shè)關(guān)鍵字為 int 型typedef struct {         //定義每個(gè)記錄(數(shù)據(jù)元素)的結(jié)構(gòu)KeyType key;         //關(guān)鍵字
}RedType;typedef struct {   // 定義順序表結(jié)構(gòu)RedType r[MAXSIZE + 1]; //r[0]作為緩沖區(qū)或哨兵int length; //順序表的長(zhǎng)度
}SqList;
typedef SqList HeapType; // 堆采用順序表存儲(chǔ)表示/*大根堆*/
void HeapAdjust_big(HeapType* H, int s, int m)
{//調(diào)整R[s]關(guān)鍵字，使R[s...m]成為一個(gè)大根堆RedType rc = H->r[s];int j;for (j = 2 * s; j <= m; j *= 2){// H->r[j]和 H->r[j + 1]分別代表H->r[s]的左子結(jié)點(diǎn)和右子結(jié)點(diǎn)，比較出兩者之間最大值if (j < m && H->r[j].key < H->r[j + 1].key){++j;}//再和比較H->r[s]比較最大值if (rc.key >= H->r[j].key){//H->r[s]最大，即無(wú)需改動(dòng)位置break;}H->r[s] = H->r[j];s = j;}H->r[s] = rc;//插入
}/*小根堆*/
void HeapAdjust_small(HeapType* H, int s, int m)
{//調(diào)整R[s]關(guān)鍵字，使R[s...m]成為一個(gè)小根堆RedType rc = H->r[s];int j;for (j = 2 * s; j <= m; j *= 2){if (j < m && H->r[j].key > H->r[j + 1].key){++j;}if (rc.key <= H->r[j].key){break;}H->r[s] = H->r[j];s = j;}H->r[s] = rc;
}void HeapSort(HeapType* H)
{//對(duì)順序表H進(jìn)行堆排序int i;for (i = H->length / 2; i > 0; i--)  //建初始堆 從 i = H->length / 2 往前到1{HeapAdjust_small(H, i, H->length);}for (i = H->length; i > 1; i--)  //進(jìn)行n-1趟排序{printf("%d ", H->r[1].key);//根與最后一個(gè)元素交換H->r[0] = H->r[i];H->r[i] = H->r[1];H->r[1] = H->r[0];//對(duì)R[1]到R[i-1]重新建堆HeapAdjust_small(H, 1, i-1);}
}int main() {int i;int r[13] = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };HeapType H;H.length = 13;for (i = 1; i <= H.length; i++) {H.r[i].key = r[i - 1];}printf("排序結(jié)果：\n");HeapSort(&H);return 0;
}

時(shí)間復(fù)雜度：

• 初始堆化所需時(shí)間不超過(guò)O(n)
• 排序階段(不含初始堆化)
  • 一次重新堆化所需時(shí)間不超過(guò)O(logn)
  • n-1次循環(huán)所需時(shí)間不超過(guò)O(nlogn)
• Tw(n)=0(n)+ O(nlogn)= O(nlogn) —— 最好情況、最壞情況、平均情況

空間復(fù)雜度：O(1)

穩(wěn)定性：不穩(wěn)定

不適用于待排序記錄個(gè)數(shù)n較少的情況，但對(duì)于n較大的文件還是很有效的。

10.5 歸并排序(Merging Sort)

基本思想：將兩個(gè)或兩個(gè)以上的有序子序列“歸并”為一個(gè)有序序列，該算法采用經(jīng)典的分治（divide-and-conquer）策略（分治法將問(wèn)題 分(divide) 成一些小的問(wèn)題然后遞歸求解，而 治(conquer) 的階段則將分的階段得到的各答案"修補(bǔ)"在一起，即分而治之)。

通常采用2-路歸并排序：將兩個(gè)位置相鄰的有序子序列R[l…]m]和R[m+1…]n] 歸并為一個(gè)有序序列R[l…n]

整個(gè)歸并排序僅需 ?log₂n? 趟

#include<stdio.h>
#include<stdlib.h>void Merge(int* arr, int left, int mid, int right) {int* temp = (int*)malloc((right - left + 1) * sizeof(int));/* i => [left, mid]j => [mid + 1, right]*/int i = left, j = mid + 1, k = 0;while (i <= mid && j <= right) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++];}else {temp[k++] = arr[j++];}}while (i <= mid) {temp[k++] = arr[i++];}while (j <= right) {temp[k++] = arr[j++];}for (i = left, k = 0; i <= right; i++, k++) {arr[i] = temp[k];}free(temp);
}void MergeSort(int* arr, int left, int right) {if (left >= right) {return;}int mid = (left + right) / 2;MergeSort(arr, left, mid);MergeSort(arr, mid + 1, right);Merge(arr, left, mid, right);
}void printArray(int* arr, int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = { 81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15 };int n = sizeof(arr) / sizeof(arr[0]);MergeSort(arr, 0, n - 1);printArray(arr, n);return 0;
}

時(shí)間復(fù)雜度：O(nlogn) —— 最好情況、最壞情況、平均情況

空間復(fù)雜度：O(n)

穩(wěn)定性：穩(wěn)定

10.6 基數(shù)排序(Radix Sorting)

10.6.1 多關(guān)鍵字的排序

基本步驟：

1. 確定每個(gè)關(guān)鍵字的優(yōu)先級(jí)
2. 對(duì)每個(gè)關(guān)鍵字進(jìn)行排序
3. 根據(jù)優(yōu)先級(jí)合并排序結(jié)果

關(guān)鍵字的次序：K⁰, K¹, … , K^d-1

最主位關(guān)鍵字：K⁰

最次位關(guān)鍵字：K^d-1

最高位優(yōu)先 (Most Significant Digit first)法，簡(jiǎn)稱 MSD 法

• 先對(duì)最主位關(guān)鍵字 K⁰ 進(jìn)行排序，將序列分成若干子序列，每個(gè)子序 列中的記錄都具有相同的K⁰值，

• 然后分別就每個(gè)子序列對(duì)關(guān)鍵字 K¹ 進(jìn)行排序，按K¹值 不同再分成若干更小的子序列，

• 依次重復(fù)，

• 直至對(duì) K^d-2 進(jìn)行排序之后得到的每一子序列 中的記錄都具有相同的關(guān)鍵字(K⁰, K¹, … , K^d-2),

• 而后分別每個(gè)子序列對(duì) K^d-1 進(jìn)行排 序，最后將所有子序列依次聯(lián)接在一起成為一個(gè)有序序列

?

最低位優(yōu)先 (Least Significant Digit first) 法，簡(jiǎn)稱 LSD 法

• 從最次位關(guān)鍵字 K^d-1 起進(jìn)行排序。
• 然后再對(duì)高一位的關(guān)鍵字 K^d-2 進(jìn)行排序，
• 依次重復(fù)，
• 直至對(duì) K⁰ 進(jìn)行排序后便成 為一個(gè)有序序列

?

/*--------------使用LSD基數(shù)排序算法---------------*/
/* K 由 3個(gè)關(guān)鍵字(K0,0K1 ,K2)組成，其中 K0 是百位數(shù)，K1 是十位數(shù)，K2 是個(gè)位數(shù)；*/#include<stdio.h>
#include<stdlib.h>// 定義最大數(shù)字的位數(shù)
#define MAX_DIGITS 3  // 3位數(shù)字，百位、十位、個(gè)位// 定義桶的大小
#define BUCKET_SIZE 10   // 10個(gè)桶，分別對(duì)應(yīng)0-9/*** 函數(shù)：分配數(shù)據(jù)到桶中* @param data 要排序的數(shù)據(jù)數(shù)組* @param bucket 桶數(shù)組，用于統(tǒng)計(jì)每個(gè)數(shù)字出現(xiàn)的次數(shù)* @param n 數(shù)據(jù)數(shù)組的長(zhǎng)度* @param digit 當(dāng)前正在處理的位數(shù)（1、10、100）*/
void distribute(int* data, int* bucket, int n, int digit) {int i;// 遍歷數(shù)據(jù)數(shù)組，統(tǒng)計(jì)每個(gè)數(shù)字在當(dāng)前位數(shù)上的值for (i = 0; i < n; i++) {// 計(jì)算當(dāng)前數(shù)字在當(dāng)前位數(shù)上的值int index = (data[i] / digit) % 10;// 將該值對(duì)應(yīng)的桶計(jì)數(shù)加1bucket[index]++;}
}/*** 函數(shù)：收集數(shù)據(jù)從桶中* @param data 要排序的數(shù)據(jù)數(shù)組* @param bucket 桶數(shù)組，用于統(tǒng)計(jì)每個(gè)數(shù)字出現(xiàn)的次數(shù)* @param temp 臨時(shí)數(shù)組，用于存儲(chǔ)收集的數(shù)據(jù)* @param n 數(shù)據(jù)數(shù)組的長(zhǎng)度* @param digit 當(dāng)前正在處理的位數(shù)（1、10、100）*/
void collect(int* data, int* bucket, int* temp, int n, int digit) {int i, j = 0;// 遍歷桶數(shù)組，收集數(shù)據(jù)for (i = 0; i < BUCKET_SIZE; i++) {// 循環(huán)直到該桶的計(jì)數(shù)為0while (bucket[i] > 0) {// 遍歷數(shù)據(jù)數(shù)組，找到對(duì)應(yīng)的數(shù)字for (int k = 0; k < n; k++) {// 如果當(dāng)前數(shù)字在當(dāng)前位數(shù)上的值與桶的索引相等if ((data[k] / digit) % 10 == i) {// 將該數(shù)字收集到臨時(shí)數(shù)組中temp[j] = data[k];j++;// 將桶的計(jì)數(shù)減1bucket[i]--;}}}}// 將收集的數(shù)據(jù)復(fù)制回原始數(shù)據(jù)數(shù)組for (i = 0; i < n; i++) {data[i] = temp[i];}
}// 函數(shù)：基數(shù)排序
void radixSort(int* data, int n) {int digit = 1;int* temp = (int*)malloc(n * sizeof(int));int bucket[BUCKET_SIZE] = { 0 };// 進(jìn)行MAX_DIGITS次分配和收集for (int i = 0; i < MAX_DIGITS; i++) {// 分配數(shù)據(jù)到桶中distribute(data, bucket, n, digit);// 收集數(shù)據(jù)從桶中collect(data, bucket, temp, n, digit);// 將位數(shù)乘以10（下一位）digit *= 10;// 重置桶數(shù)組for (int j = 0; j < BUCKET_SIZE; j++) {bucket[j] = 0;}// 打印當(dāng)前的數(shù)據(jù)狀態(tài)printf("第 %d 趟分配 + 收集后的數(shù)據(jù)：\n", i);for (int i = 0; i < n; i++) {printf("%d ", data[i]);}printf("\n");}
}// 主函數(shù)
int main() {int data[] = { 278, 109, 63, 930, 589, 184, 505, 269, 8, 83};int n = sizeof(data) / sizeof(data[0]);radixSort(data, n);    return 0;
}

10.6.2 鏈?zhǔn)交鶖?shù)排序

基數(shù)排序是借助 “分配“和“收集“ 兩種操作對(duì)單邏輯關(guān)鍵字進(jìn)行排序，并用鏈表作存儲(chǔ)結(jié)構(gòu) 的一種內(nèi)部排序 方法。

基本步驟：

1. 將數(shù)據(jù)分成多個(gè)桶，每個(gè)桶對(duì)應(yīng)一個(gè)基數(shù)位
2. 對(duì)每個(gè)桶進(jìn)行排序，使用鏈表存儲(chǔ)排序結(jié)果
3. 迭代基數(shù)位，重復(fù)步驟1和2，直到所有基數(shù)位完成

#include <stdio.h>
#include <stdlib.h>// 定義節(jié)點(diǎn)結(jié)構(gòu)，包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的指針
typedef struct Node {int data;struct Node* next;
} Node;// 定義鏈表結(jié)構(gòu)，包含頭節(jié)點(diǎn)和尾節(jié)點(diǎn)
typedef struct List {Node* head;Node* tail;
} List;// 初始化鏈表函數(shù)，設(shè)置頭節(jié)點(diǎn)和尾節(jié)點(diǎn)為NULL
void initList(List* list) {list->head = NULL;list->tail = NULL;
}// 插入節(jié)點(diǎn)到鏈表末尾
void insertNode(List* list, int data) {// 分配新節(jié)點(diǎn)的內(nèi)存Node* newNode = (Node*)malloc(sizeof(Node));// 設(shè)置新節(jié)點(diǎn)的數(shù)據(jù)newNode->data = data;// 置新節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為NULLnewNode->next = NULL;// 如果鏈表為空，設(shè)置新節(jié)點(diǎn)為頭節(jié)點(diǎn)和尾節(jié)點(diǎn)if (list->head == NULL) {// 設(shè)置頭節(jié)點(diǎn)為新節(jié)點(diǎn)list->head = newNode;// 設(shè)置尾節(jié)點(diǎn)為新節(jié)點(diǎn)list->tail = newNode;}// 如果鏈表不為空，插入新節(jié)點(diǎn)到尾節(jié)點(diǎn)后面else {// 設(shè)置尾節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為新節(jié)點(diǎn)list->tail->next = newNode;// 更新尾節(jié)點(diǎn)為新節(jié)點(diǎn)list->tail = newNode;}
}// 打印鏈表
void printList(List* list) {// 從頭節(jié)點(diǎn)開(kāi)始遍歷鏈表Node* current = list->head;// 遍歷鏈表，直到到達(dá)NULLwhile (current != NULL) {// 打印當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)printf("%d ", current->data);// 移動(dòng)到下一個(gè)節(jié)點(diǎn)current = current->next;}printf("\n");
}// 分配節(jié)點(diǎn)到桶中的函數(shù)
void allocateNodes(List* list, List* bucket, int digit) {// 分配節(jié)點(diǎn)到桶中Node* current = list->head; // 從頭節(jié)點(diǎn)開(kāi)始遍歷鏈表while (current != NULL) {// 計(jì)算當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)在當(dāng)前位數(shù)上的值int index = (current->data / digit) % 10;// 將當(dāng)前節(jié)點(diǎn)插入到對(duì)應(yīng)的桶中insertNode(&bucket[index], current->data);// 移動(dòng)到下一個(gè)節(jié)點(diǎn)current = current->next;}
}// 收集節(jié)點(diǎn)從桶中的函數(shù)
void collectNodes(List* list, List* bucket) {// 收集節(jié)點(diǎn)從桶中list->head = NULL;// 重置頭節(jié)點(diǎn)為NULLlist->tail = NULL;// 重置尾節(jié)點(diǎn)為NULLfor (int j = 0; j < 10; j++) {// 從每個(gè)桶中收集節(jié)點(diǎn)Node* current = bucket[j].head;// 從桶的頭節(jié)點(diǎn)開(kāi)始遍歷while (current != NULL) {// 將當(dāng)前節(jié)點(diǎn)插入到鏈表中insertNode(list, current->data);// 移動(dòng)到下一個(gè)節(jié)點(diǎn)current = current->next;}// 初始化每個(gè)桶initList(&bucket[j]);}
}// 基數(shù)排序函數(shù)
void radixSort(List* list) {int digit = 1;  // 初始化位數(shù)為個(gè)位（1）List bucket[10]; // 定義10個(gè)桶，用于存儲(chǔ)不同位數(shù)的數(shù)據(jù)for (int i = 0; i < 10; i++) {// 初始化每個(gè)桶initList(&bucket[i]);}// 進(jìn)行3次分配和收集（針對(duì)3位數(shù)字）for (int i = 0; i < 3; i++) {// 分配節(jié)點(diǎn)到桶中allocateNodes(list, bucket, digit);// 收集節(jié)點(diǎn)從桶中collectNodes(list, bucket);// 將位數(shù)乘以10（下一位）digit *= 10;// 打印當(dāng)前的數(shù)據(jù)狀態(tài)printf("第 %d 趟分配 + 收集后的數(shù)據(jù)：\n", i + 1);printList(list);}
}int main() {List list;initList(&list);int r[] = { 614,738,921,485,637,101,215,530,790,306 };int i;int n = sizeof(r) / sizeof(r[0]);for (i = 0; i < n; i++){insertNode(&list, r[i]);}// 插入示例數(shù)據(jù)printf("原始數(shù)據(jù)：\n");printList(&list);radixSort(&list);return 0;
}

適用范圍：多關(guān)鍵字排序可以處理多種數(shù)據(jù)類型，而鏈?zhǔn)交鶖?shù)排序僅適用于整數(shù)或字符串?dāng)?shù)據(jù)。

時(shí)間復(fù)雜度: O(k*(n+m))

? k:關(guān)鍵字個(gè)數(shù)，
? m:關(guān)鍵字取值范圍為m個(gè)值

空間復(fù)雜度: O(n+m)

穩(wěn)定性: 穩(wěn)定

10.7 各種內(nèi)部排序方法的比較討論

一、時(shí)間性能

1. 按平均的時(shí)間性能來(lái)分，有三類排序方法:·

   • 時(shí)間復(fù)雜度為O(nlogn)的方法有: 快速排序、堆排序和歸并排序，其中以快速排序?yàn)樽詈?/p>

   • 時(shí)間復(fù)雜度為O(n²)的有: 直接插入排序、冒泡排序和簡(jiǎn)單選擇排序，其中以直接插入為最好

   • 時(shí)間復(fù)雜度為O(n)的排序方法只有: 基數(shù)排序。

2. 當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)，直接插入排序和冒泡排序達(dá)到O(n)的時(shí)間復(fù)雜度;

   而對(duì)于快速排序而言，這是最不好的情況，此時(shí)的時(shí)間性能退化為O(n²)，因此是應(yīng)該盡量避免的情況。

二、空間性能：指的是排序過(guò)程中所需的輔助空間大小

1. 所有的簡(jiǎn)單排序方法(包括:直接插入、冒泡和簡(jiǎn)單選擇)和堆排序的空間復(fù)雜度為O(1)

2. 快速排序?yàn)镺(logn)，為棧所需的輔助空間

3. 歸并排序所需輔助空間最多，其空間復(fù)雜度為O(n)

4. 鏈?zhǔn)交鶖?shù)排序需附設(shè)隊(duì)列首尾指針，則空間復(fù)雜度為O(rd)

---

參考：

教材：嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)》（C語(yǔ)言版）.pdf

視頻：

數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)（青島大學(xué)-王卓）

表插入排序算法實(shí)現(xiàn)

博客：

2-路插入排序詳解