【学习笔记】数据结构（十）

内部排序

10.1 概述

排序 ：将一组杂乱无章的数据按一定规律顺次排列起来。即，将无序序列排成一个有序序列 (由小到大或由大到小) 的运算。

如果参加排序的数据结点包含多个数据域，那么排序往往是针对其中某个域而言。

排序方法分类 ：

• 按数据存储介质: 内部排序和外部排序

  • 内部排序：数据量不大、数据在内存，无需内外存交换数据
  • 外部排序：数据量较大、数据在外存(文件排序) —— 外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存

• 按比较器个数: 串行排序和并行排序

  • 串行排序：单处理机(同一时刻比较一对元素)
  • 并行排序：多处理机(同一时刻比较多对元素)

• 按主要操作: 比较排序和基数排序

  • 比较排序：用比较的方法 —— 插入排序、交换排序、选择排序、归并排序
  • 基数排序：不比较元素的大小，仅仅根据元素本身的取值确定其有序位置。

• 按辅助空间: 原地排序和非原地排序

  • 原地排序：辅助空间用量为O(1)的排序方法(所占的辅助存储空间与参加排序的数据量大小无关)·
  • 非原地排序：辅助空间用量超过O(1的排序方法(所占的辅助存储空间与参加排序的数据量大小有关)·

• 按稳定性: 稳定排序和非稳定排序

  • 稳定排序：能够使任何数值相等的元素，排序以后相对次序不变。例如：直接插入排序

  • 非稳定性排序：数值相等的元素，排序以后相对次序改变。例如：简单选择排序

    排序方法是否稳定，并不能衡量一个排序算法的优劣。

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

  • 自然排序：输入数据越有序排序的速度越快的排序方法。
  • 非自然排序：输入数据越有序排序的速度慢的排序方法。

存储结构 ：

• 顺序表存储：待排序的一组记录存放在地址连续的一组存储单元上。记录之间的次序关系由其存储位置决定，则实现排 序必须借助移动记录

  # define MAXSIZE 20     // 设记录不超过20个
  typedef int KeyType;    // 设关键字为int型typedef struct {         //定义每个记录(数据元素)的结构KeyType key;         //关键字//InfoType otherinfo;  //其它数据项
  }RedType;typedef struct {   // 定义顺序表结构RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度
  }SqList;
  

• 链表存储：待排序记录存放在静态链表中，记录之间的次序关系由 指针指示，则实现排序不需要移动记录，仅需修改指针即可；

• 地址存储：待排序记录本身存储在一组地址连续的存储单元内，同时另设一个指示各个记录存储位置的地址向量，在排序过 程中不移动记录本身，而移动地址向量中这些记录的“地址",在排序结束之后再按照地址向量中的值调整记录的存储位置。

10.2 插入排序

插入排序：

在有序序列中插入一个元素，保持序列有序，有序长度不断增加。

有序插入方法：

• 在插入a[i]前，数组a的前半段(a[0]~a[i-1])是有序段, 后半段(a[i]~a[n-1])是停留于输入次序的“无序段“
• 插入a[i]使a[0]~a[i-1]有序，也就是要为a[i]找到有序位置j (0≤j≤i) ,将a[i]插入在a[j]的位置上。

根据找插入位置方法不同分为：

• 顺序法定位插入位置：直接插入排序
• 二分法定位插入位置：二分插入排序
• 缩小增量多遍插入排序：希尔排序

10.2.1 直接插入排序

实现排序的基本操作有两个:

​ (1) “比较”序列中两个关键字的大小;

​ (2) “移动”记录。

#include<stdio.h># define MAXSIZE 20     // 设记录不超过20个
typedef int KeyType;    // 设关键字为int型typedef struct {         //定义每个记录(数据元素)的结构KeyType key;         //关键字
}RedType;typedef struct {   // 定义顺序表结构RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度
}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) //后面比前面数小，则需要进行排序{L->r[0] = L->r[i]; // 复制插入元素到哨兵//记录后移，寻找插入位置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];}//后面数大于等于前面数，只需继续循环，比较下一个数}
}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个元素

最好情况：顺序有序

• 比较次数：$$\sum _{i=2}^{n}1=n-1$$
• 移动次数：0
• 时间复杂度 O(n)

最坏情况：逆序有序

• 比较次数（平均值）：$$\sum _{i=2}^{n}i=\frac{(n+2)(n-1)}{2}$$

• 移动次数（平均值）：$$\sum _{i=2}^n(i+1)=\frac{(n+4)(n-1)}{2}$$

• 时间复杂度 O(n²)

平均情况：

• 比较次数（平均值）：$$\sum _{i=2}^n\frac{i+1}{2}=\frac{(n+2)(n-1)}{4}$$
• 移动次数（平均值）：$$\sum _{i=2}^n(\frac{i+1}{2}+1)=\frac{(n+6)(n-1)}{4}$$
• 时间复杂度 O(n²) - 最坏的情况的一半

空间复杂度：O(1)

稳定性：稳定

原始数据越接近有序，排序速度越快

10.2.2 其他插入排序

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

插入排序的基本操作是在一个有序表中进行查找和插入，这个==“查找“操作可利用“折半查找”==来实现，再进行插入，则称之为折半插入排序(Binary Insertion Sort)

#include<stdio.h># define MAXSIZE 20     // 设记录不超过20个
typedef int KeyType;    // 设关键字为int型typedef struct {         //定义每个记录(数据元素)的结构KeyType key;         //关键字
}RedType;typedef struct {   // 定义顺序表结构RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度
}SqList;void BInsertSort(SqList* L)
{int i, j;for (i = 2; i <= L->length; i++){L->r[0] = L->r[i]; // 复制插入元素到哨兵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) //插入点在低半区{high = m - 1;}else { //插入点在高半区low = m + 1;}}//循环结束，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;
}

折半插入排序特点：

• 折半查找比顺序查找快，
• 关键码比较次数与待排座对象序列的初始排列无关，仅依赖于对象个数。
• 当n较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差;
• 在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序执行的关键码比较次数要少;
• 平均性能优于直接插入排序

n个元素

折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变

时间复杂度：仍为O(n²)，

空间复杂度：O(1)

稳定性：稳定

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

2- 路插入排序是在折半插入排序的基础上再改进之，其目的是减少排序过程中移动 记录的次数，但为此需要n个记录的辅助空间。

• 初始化一个与原数组一样大小的辅助数组d，并将原数组的第一个元素放入辅助数组的第一个位置。
• 将d看成是一个循环向量,并设两个指针 first 和 final分别指示排序过程中得到的有序序列中的第一个和最后一个记录在d中的位置。
• 从第二个元素开始遍历原数组，对于每个待排序元素：
  • 如果待排序元素小于辅助数组的最小值，则通过移动first将其插入到最小值之前。
  • 如果待排序元素大于辅助数组的最大值，则过移动final将其插入到最大值之后。
  • 否则，通过移动final将大于的数值向后移动并将待排序元素插入到适当的位置。
• 处理完所有元素后，将辅助数组中的元素复制回原数组，完成排序。

#include<stdio.h>
#include<stdlib.h>#define MAXSIZE 20     // 设记录不超过20个
typedef int KeyType;    // 设关键字为int型typedef struct {         //定义每个记录(数据元素)的结构KeyType key;         //关键字
}RedType;typedef struct {   // 定义顺序表结构RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度
}SqList;void TwoWayInsertSort(SqList* L) {/* 初始化一个与原数组一样大小的辅助数组 */RedType* d;d = (RedType*)malloc((L->length) * sizeof(RedType));if (d == NULL) {return;}/* 设L的第1个记录为d中排好序的记录(在位置[0]) */d[0] = L->r[1];/* first、final分别指示d中排好序的记录的第1个和最后1个记录的位置 */int first, final;first = final = 0;int i, j;/* 依次将L的第2个～最后1个记录插入d中 */for (i = 2; i <= L->length; i++) {if (L->r[i].key < d[first].key) {/* 待插记录小于d中最小值，插到d[first]之前(不需移动d数组的元素) */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数组的元素) */final++;d[final] = L->r[i];}else {/* 待插记录大于d中最小值，小于d中最大值，插到d的中间(需要移动d数组的元素) */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++) { // 修改循环条件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); // 释放内存
}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个元素

‌时间复杂度‌：2-路插入排序的时间复杂度为O(n²)，移动次数大约为n²/8次，尽管减少了移动次数，但并不能完全避免移动操作。

‌空间复杂度‌：需要额外的辅助数组，空间复杂度为O(n)。

10.2.2.3 表插入排序（Table Insertion Sort）

在排序过程中不移动记 录，只有改变存储结构

算法思路：

• 初始化表头结点：设数组中下标为"0"的分量为表头结点，并令表头结点记录的关键字取最大整数 MAXINT
• 表插入排序的过程：
  • 首先将静态链表中数组下标为"1"的分量（结点）和表头结点构成一个循环链表
  • 然后依次将下标为"2"至"n"的分量（结点）按记录关键字非递减有序插人到循环链表中

#include<stdio.h>
#include<limits.h>#define MAXSIZE 20     // 设记录不超过20个
#define MAXVALUE INT_MAX  // 定义最大值typedef struct SLNode {int data;  // 存储数据int link;  // 存储指向下一个元素的索引
}SLNode, Table[MAXSIZE];void TableInsertSort(Table* tb, int n)
{//与第一个数据元素构成循环列表(*tb)[0].link = 1;  // 初始化顺序表的头结点，将其link指向第一个数据元素int p, q; // 用于在排序过程中存储当前元素和前驱元素的索引for (int i = 2; i < n; i++) // 从第二个元素开始遍历{p = (*tb)[0].link; q = 0;while (p != 0 && (*tb)[p].data <= (*tb)[i].data){q = p; //q是p的前驱p = (*tb)[p].link; // p更新为下一个元素的索引}(*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;// 初始化表头结点：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)

基本思想： 先将整个待排记录序列分割成为若干子序列分别进行直接插入排 序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

• 选择一个增量序列 D_k：D_M > D_M-1 > … > D₁ = 1 必须递减
• 对每个D_k进行“D_k-间隔”插入排序（K= M，M-1，…1）

#include<stdio.h>
#include<stdlib.h>#define MAXSIZE 20     // 设记录不超过20个
typedef int KeyType;    // 设关键字为int型typedef struct {         //定义每个记录(数据元素)的结构KeyType key;         //关键字
}RedType;typedef struct {   // 定义顺序表结构RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度
}SqList;void ShellInsert(SqList* L, int dk)
{int i, j;for (i = dk + 1; i <= L->length; i++)// 从第dk+1个元素开始向后遍历顺序表{ if (L->r[i].key < L->r[i - dk].key)// 如果当前元素的key小于它dk位置前的元素的key{            L->r[0] = L->r[i];// L->r[0]是暂存单元，暂存当前元素for (j = i - dk; j > 0 && (L->r[0].key < L->r[j].key); j = j - dk){// 从当前元素向前遍历，步长为dkL->r[j + dk] = L->r[j]; // 将比暂存元素大的元素向后移动dk个位置}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 增量序列排序结果：\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("排序结果：\n");for (i = 1; i <= 13; i++){printf("%d ", L.r[i].key);}return 0;
}

希尔排序算法效率与增量序列的取值有关：

Hibbard增量序列

• D_k = 2 ^k-1 —— 相邻元素互质
• 最坏: 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)

稳定性：不稳定

时间复杂度：O(n^1.25) ~ O(1.6n^1.25) – 经验公式

​ 最好：O(n)

​ 最坏：O(n²)

​ 最好：~O(n^1.3)

空间复杂度：O(1)

不宜在链式存储结构上实现

10.3 交换排序

交换排序：两两比较，如果发生逆序则交换，直到所有记录都排好序为止。

10.3.1 冒泡排序(Bubble Sort)

基本思想: 每趟不断将记录两两比较，并按“前小后大”规则交换

#include<stdio.h>
#include<stdlib.h>#define MAXSIZE 20     // 设记录不超过20个
typedef int KeyType;    // 设关键字为int型typedef struct {         //定义每个记录(数据元素)的结构KeyType key;         //关键字
}RedType;typedef struct {   // 定义顺序表结构RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度
}SqList;void bubble_sort(SqList *L) 
{int i, j;RedType x; // 交换时临时存储for (i = 1; i <= L->length - 1; i++) // 需要比较i趟，n个记录 总共n-1趟{for (j = 1; j <= L->length - i; j++) // 每一趟需要比较的次数，n个记录，比较n-i次{if (L->r[j].key > L->r[j + 1].key) // 比较 {//发生逆序 - 交换x = L->r[j]; L->r[j] = L->r[j + 1];L->r[j + 1] = x;}}printf("\n第 %d 趟排序结果：\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("排序结果：\n");for (i = 1; i <= 13; i++){printf("%d ", L.r[i].key);}return 0;
}

改进：冒泡处理过程中，没有进行任何交换，说明序列已有序，则停止交换

#include<stdio.h>
#include<stdlib.h>#define MAXSIZE 20     // 设记录不超过20个
typedef int KeyType;    // 设关键字为int型typedef struct {         //定义每个记录(数据元素)的结构KeyType key;         //关键字
}RedType;typedef struct {   // 定义顺序表结构RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度
}SqList;void bubble_sort(SqList *L) 
{int i, j;int flag = 1;RedType x; // 交换时临时存储for (i = 1; (i <= L->length - 1) && (flag == 1); i++) // 需要比较i趟，n个记录 总共n-1趟{flag = 0;for (j = 1; j <= L->length - i; j++) // 每一趟需要比较的次数，n个记录，比较n-i次{if (L->r[j].key > L->r[j + 1].key) // 比较 {flag = 1;//发生逆序 - 交换x = L->r[j]; L->r[j] = L->r[j + 1];L->r[j + 1] = x;}}printf("\n第 %d 趟排序结果：\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("排序结果：\n");for (i = 1; i <= 13; i++){printf("%d ", L.r[i].key);}return 0;
}

最好情况：正序

• 比较次数：n-1
• 移动次数：0
• 时间复杂度 O(n)

最坏情况：逆序

• 比较次数（平均值）：$$\sum _{i=1}^{n-1}(n-i)=\frac{(n^2-n)}{2}$$

• 移动次数（平均值）：$$3\sum _{i=1}^{n-1}(n-i)=\frac{3(n^2-n)}{2}$$

• 时间复杂度 O(n²)

平均情况：

• 时间复杂度 O(n²)

空间复杂度：O(1)

稳定性：稳定

10.3.2 快速排序(Quick Sort)

基本思想:

• 任取一个元素 (如:第一个) 为中心pivot - 可以是第一个数、最后一个数、最中间一个数、任选一个数等

• 所有比它小的元素一律前放，比它大的元素一律后放形成左右两个子表;

• 对各子表重新选择中心元素并依此规则调整 【递归思想】

• 直到每个子表的元素只剩一个

#include<stdio.h>
#include<stdlib.h>#define MAXSIZE 20     // 设记录不超过20个
typedef int KeyType;    // 设关键字为int型typedef struct {         //定义每个记录(数据元素)的结构KeyType key;         //关键字
}RedType;typedef struct {   // 定义顺序表结构RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度
}SqList;int Partition(SqList* L, int low, int high)
{int pivotkey = L->r[low].key; //任取一个元素 (第一个) 为中心pivotL->r[0] = L->r[low];  // 将中心pivot放到0处while (low < high){while (low < high && L->r[high].key >= pivotkey) // high >= 中心  ，移动high向前{--high;}L->r[low] = L->r[high]; //high < 中心, 把该值移动到low那一侧while (low < high && L->r[low].key <= pivotkey)// low <= 中心  ，移动low向后{++low;}L->r[high] = L->r[low];//low > 中心, 把该值移动到high那一侧}L->r[low] = L->r[0]; // 中心放到对应位置return low;
}void QSort(SqList *L, int low, int high) 
{if (low < high)//长度大于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); //对低子表递归排序QSort(L, pivotloc + 1, high);  //对高子表递归排序，}
}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("排序结果：\n");for (i = 1; i <= 13; i++){printf("%d ", L.r[i].key);}return 0;
}

划分元素的选取是影响时间性能的关键

最好情况：

• 时间复杂度 O(nlogn)

最坏情况：

• 时间复杂度 O(n²)

平均情况：

• 时间复杂度：O(nlogn)

​ QSort()：O(logn)

​ Partition()：O(n)

空间复杂度：

​ 平均情况：O(logn)

​ 最坏情况：O(n)

稳定性：不稳定

快速排序不适于对原本有序或基本有序（包括正序和逆序）的记录序列进行排序，退化成冒泡排序

10.4 选择排序

10.4.1 简单选择排序(Simple Selection Sort)

基本思想： 在待排序的数据中选出最大(小)的元素放在其最终的位置。

基本操作:

• 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换
• 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换
• 重复上述操作，共进行n-1趟排序后，排序结束

#include<stdio.h>
#include<stdlib.h>#define MAXSIZE 20     // 设记录不超过20个
typedef int KeyType;    // 设关键字为int型typedef struct {         //定义每个记录(数据元素)的结构KeyType key;         //关键字
}RedType;typedef struct {   // 定义顺序表结构RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度
}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 次排序结果：\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("排序结果：\n");for (i = 1; i <= 13; i++){printf("%d ", L.r[i].key);}return 0;
}

时间复杂度 - O(n²)：

• 移动次数

  • 最好情况：0
  • 最坏情况：3(n-1)

• 比较次数：

  • 最好情况：O(n²)
  • 最坏情况：O(n²)
  • 平均情况：O(n²)

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

空间复杂度：O(1)

稳定性：不稳定

10.4.2 树形选择排序(Tree Selection Sort)

又称锦标赛排序(Tournament Sort)

基本思想： 首先对n个记录的关键字进行两两比较，然后在 其中⌈ n / 2⌉个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。

10.4.3 堆排序(Heap Sort)

若n个元素的序列{a₁，a₂,…, a_n}满足 a_i ≤ a_2i && a_i ≤ a_2i+1 则称该序列为小根堆

若n个元素的序列{a₁，a₂,…, a_n}满足 a_i ≥ a_2i && a_i ≥ a_2i+1 则称该序列为大根堆

从堆的定义可以看出，堆实质是满足如下性质的完全二叉树:二又树中任一非叶子结点均小于(大于)它的孩子结点

堆排序: 若在输出堆顶的最小值(最大值)后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值(次大值)…如此反复，便能得到一个有序序列。【堆顶就是最小值(最大值)，每次都取堆顶，就可得到一个有序序列】

堆序列需解决两个问题：

• 如何由无序序列建成一个堆?

  1. 单结点的二又树是堆

  2. 在完全二叉树中所有以叶子结点(序号i>n/2【最后一个结点是n，那么他的双亲是n/2，所以叶子结点是 > n/2】)为根的子树是堆。

  3. 只需依次将以序号为n/2，n/2 - 1，… 1的结点为根的子树均调整为堆即可。

  

• 如何在输出堆顶元素后，调整剩余元素为一个新的堆?

  ​ 小根堆:

  1. 输出堆顶元素之后，以堆中最后一个元素【编号最大的元素】替代之;

  2. 然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换，

  3. 重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选

  

#include<stdio.h>
#include<stdlib.h>#define MAXSIZE 20     // 设记录不超过20个
typedef int KeyType;    // 设关键字为 int 型typedef struct {         //定义每个记录(数据元素)的结构KeyType key;         //关键字
}RedType;typedef struct {   // 定义顺序表结构RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵int length; //顺序表的长度
}SqList;
typedef SqList HeapType; // 堆采用顺序表存储表示/*大根堆*/
void HeapAdjust_big(HeapType* H, int s, int m)
{//调整R[s]关键字，使R[s...m]成为一个大根堆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]的左子结点和右子结点，比较出两者之间最大值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]最大，即无需改动位置break;}H->r[s] = H->r[j];s = j;}H->r[s] = rc;//插入
}/*小根堆*/
void HeapAdjust_small(HeapType* H, int s, int m)
{//调整R[s]关键字，使R[s...m]成为一个小根堆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)
{//对顺序表H进行堆排序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--)  //进行n-1趟排序{printf("%d ", H->r[1].key);//根与最后一个元素交换H->r[0] = H->r[i];H->r[i] = H->r[1];H->r[1] = H->r[0];//对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("排序结果：\n");HeapSort(&H);return 0;
}

时间复杂度：

• 初始堆化所需时间不超过O(n)
• 排序阶段(不含初始堆化)
  • 一次重新堆化所需时间不超过O(logn)
  • n-1次循环所需时间不超过O(nlogn)
• Tw(n)=0(n)+ O(nlogn)= O(nlogn) —— 最好情况、最坏情况、平均情况

空间复杂度：O(1)

稳定性：不稳定

不适用于待排序记录个数n较少的情况，但对于n较大的文件还是很有效的。

10.5 归并排序(Merging Sort)

基本思想：将两个或两个以上的有序子序列“归并”为一个有序序列，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题 分(divide) 成一些小的问题然后递归求解，而 治(conquer) 的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

通常采用2-路归并排序：将两个位置相邻的有序子序列R[l…]m]和R[m+1…]n] 归并为一个有序序列R[l…n]

整个归并排序仅需 ⌈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;
}

时间复杂度：O(nlogn) —— 最好情况、最坏情况、平均情况

空间复杂度：O(n)

稳定性：稳定

10.6 基数排序(Radix Sorting)

10.6.1 多关键字的排序

基本步骤：

1. 确定每个关键字的优先级
2. 对每个关键字进行排序
3. 根据优先级合并排序结果

关键字的次序：K⁰, K¹, … , K^d-1

最主位关键字：K⁰

最次位关键字：K^d-1

最高位优先 (Most Significant Digit first)法，简称 MSD 法

• 先对最主位关键字 K⁰ 进行排序，将序列分成若干子序列，每个子序 列中的记录都具有相同的K⁰值，

• 然后分别就每个子序列对关键字 K¹ 进行排序，按K¹值 不同再分成若干更小的子序列，

• 依次重复，

• 直至对 K^d-2 进行排序之后得到的每一子序列 中的记录都具有相同的关键字(K⁰, K¹, … , K^d-2),

• 而后分别每个子序列对 K^d-1 进行排 序，最后将所有子序列依次联接在一起成为一个有序序列

​

最低位优先 (Least Significant Digit first) 法，简称 LSD 法

• 从最次位关键字 K^d-1 起进行排序。
• 然后再对高一位的关键字 K^d-2 进行排序，
• 依次重复，
• 直至对 K⁰ 进行排序后便成 为一个有序序列

​

/*--------------使用LSD基数排序算法---------------*/
/* K 由 3个关键字(K0,0K1 ,K2)组成，其中 K0 是百位数，K1 是十位数，K2 是个位数；*/#include<stdio.h>
#include<stdlib.h>// 定义最大数字的位数
#define MAX_DIGITS 3  // 3位数字，百位、十位、个位// 定义桶的大小
#define BUCKET_SIZE 10   // 10个桶，分别对应0-9/*** 函数：分配数据到桶中* @param data 要排序的数据数组* @param bucket 桶数组，用于统计每个数字出现的次数* @param n 数据数组的长度* @param digit 当前正在处理的位数（1、10、100）*/
void distribute(int* data, int* bucket, int n, int digit) {int i;// 遍历数据数组，统计每个数字在当前位数上的值for (i = 0; i < n; i++) {// 计算当前数字在当前位数上的值int index = (data[i] / digit) % 10;// 将该值对应的桶计数加1bucket[index]++;}
}/*** 函数：收集数据从桶中* @param data 要排序的数据数组* @param bucket 桶数组，用于统计每个数字出现的次数* @param temp 临时数组，用于存储收集的数据* @param n 数据数组的长度* @param digit 当前正在处理的位数（1、10、100）*/
void collect(int* data, int* bucket, int* temp, int n, int digit) {int i, j = 0;// 遍历桶数组，收集数据for (i = 0; i < BUCKET_SIZE; i++) {// 循环直到该桶的计数为0while (bucket[i] > 0) {// 遍历数据数组，找到对应的数字for (int k = 0; k < n; k++) {// 如果当前数字在当前位数上的值与桶的索引相等if ((data[k] / digit) % 10 == i) {// 将该数字收集到临时数组中temp[j] = data[k];j++;// 将桶的计数减1bucket[i]--;}}}}// 将收集的数据复制回原始数据数组for (i = 0; i < n; i++) {data[i] = temp[i];}
}// 函数：基数排序
void radixSort(int* data, int n) {int digit = 1;int* temp = (int*)malloc(n * sizeof(int));int bucket[BUCKET_SIZE] = { 0 };// 进行MAX_DIGITS次分配和收集for (int i = 0; i < MAX_DIGITS; i++) {// 分配数据到桶中distribute(data, bucket, n, digit);// 收集数据从桶中collect(data, bucket, temp, n, digit);// 将位数乘以10（下一位）digit *= 10;// 重置桶数组for (int j = 0; j < BUCKET_SIZE; j++) {bucket[j] = 0;}// 打印当前的数据状态printf("第 %d 趟分配 + 收集后的数据：\n", i);for (int i = 0; i < n; i++) {printf("%d ", data[i]);}printf("\n");}
}// 主函数
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 链式基数排序

基数排序是借助 “分配“和“收集“ 两种操作对单逻辑关键字进行排序，并用链表作存储结构 的一种内部排序 方法。

基本步骤：

1. 将数据分成多个桶，每个桶对应一个基数位
2. 对每个桶进行排序，使用链表存储排序结果
3. 迭代基数位，重复步骤1和2，直到所有基数位完成

#include <stdio.h>
#include <stdlib.h>// 定义节点结构，包含数据和指向下一个节点的指针
typedef struct Node {int data;struct Node* next;
} Node;// 定义链表结构，包含头节点和尾节点
typedef struct List {Node* head;Node* tail;
} List;// 初始化链表函数，设置头节点和尾节点为NULL
void initList(List* list) {list->head = NULL;list->tail = NULL;
}// 插入节点到链表末尾
void insertNode(List* list, int data) {// 分配新节点的内存Node* newNode = (Node*)malloc(sizeof(Node));// 设置新节点的数据newNode->data = data;// 置新节点的下一个节点为NULLnewNode->next = NULL;// 如果链表为空，设置新节点为头节点和尾节点if (list->head == NULL) {// 设置头节点为新节点list->head = newNode;// 设置尾节点为新节点list->tail = newNode;}// 如果链表不为空，插入新节点到尾节点后面else {// 设置尾节点的下一个节点为新节点list->tail->next = newNode;// 更新尾节点为新节点list->tail = newNode;}
}// 打印链表
void printList(List* list) {// 从头节点开始遍历链表Node* current = list->head;// 遍历链表，直到到达NULLwhile (current != NULL) {// 打印当前节点的数据printf("%d ", current->data);// 移动到下一个节点current = current->next;}printf("\n");
}// 分配节点到桶中的函数
void allocateNodes(List* list, List* bucket, int digit) {// 分配节点到桶中Node* current = list->head; // 从头节点开始遍历链表while (current != NULL) {// 计算当前节点的数据在当前位数上的值int index = (current->data / digit) % 10;// 将当前节点插入到对应的桶中insertNode(&bucket[index], current->data);// 移动到下一个节点current = current->next;}
}// 收集节点从桶中的函数
void collectNodes(List* list, List* bucket) {// 收集节点从桶中list->head = NULL;// 重置头节点为NULLlist->tail = NULL;// 重置尾节点为NULLfor (int j = 0; j < 10; j++) {// 从每个桶中收集节点Node* current = bucket[j].head;// 从桶的头节点开始遍历while (current != NULL) {// 将当前节点插入到链表中insertNode(list, current->data);// 移动到下一个节点current = current->next;}// 初始化每个桶initList(&bucket[j]);}
}// 基数排序函数
void radixSort(List* list) {int digit = 1;  // 初始化位数为个位（1）List bucket[10]; // 定义10个桶，用于存储不同位数的数据for (int i = 0; i < 10; i++) {// 初始化每个桶initList(&bucket[i]);}// 进行3次分配和收集（针对3位数字）for (int i = 0; i < 3; i++) {// 分配节点到桶中allocateNodes(list, bucket, digit);// 收集节点从桶中collectNodes(list, bucket);// 将位数乘以10（下一位）digit *= 10;// 打印当前的数据状态printf("第 %d 趟分配 + 收集后的数据：\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]);}// 插入示例数据printf("原始数据：\n");printList(&list);radixSort(&list);return 0;
}

适用范围：多关键字排序可以处理多种数据类型，而链式基数排序仅适用于整数或字符串数据。

时间复杂度: O(k*(n+m))

​ k:关键字个数，
​ m:关键字取值范围为m个值

空间复杂度: O(n+m)

稳定性: 稳定

10.7 各种内部排序方法的比较讨论

一、时间性能

1. 按平均的时间性能来分，有三类排序方法:·

   • 时间复杂度为O(nlogn)的方法有: 快速排序、堆排序和归并排序，其中以快速排序为最好

   • 时间复杂度为O(n²)的有: 直接插入排序、冒泡排序和简单选择排序，其中以直接插入为最好

   • 时间复杂度为O(n)的排序方法只有: 基数排序。

2. 当待排记录序列按关键字顺序有序时，直接插入排序和冒泡排序达到O(n)的时间复杂度;

   而对于快速排序而言，这是最不好的情况，此时的时间性能退化为O(n²)，因此是应该尽量避免的情况。

二、空间性能：指的是排序过程中所需的辅助空间大小

1. 所有的简单排序方法(包括:直接插入、冒泡和简单选择)和堆排序的空间复杂度为O(1)

2. 快速排序为O(logn)，为栈所需的辅助空间

3. 归并排序所需辅助空间最多，其空间复杂度为O(n)

4. 链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)

---

参考：

教材：严蔚敏《数据结构》（C语言版）.pdf

视频：

数据结构与算法基础（青岛大学-王卓）

表插入排序算法实现

博客：

2-路插入排序详解