王道考研数据结构代码总结（第八章）

---

本文包含王道考研讲课中所涉及的数据结构中的所有代码，当PPT代码和书上代码有所区别时以咸鱼的PPT为主，个人认为PPT上的代码比王道书上的代码要便于理解，此外，本博客也许会补充一些额外的代码进来（不仅受限于王道考研），408中冷门考点频出，应该会囊括所有涉及到的代码，这也是我的DS的第二轮复习，希望与大家共勉之。

DS的后四章只有最后一章（排序）涉及大量的代码，而树，图，查找这三章，对于概念的考察比较深入，故本文对于前三章也会进行概念上的整理，代码的话也同样会全部给出。

（2023/06/27）由于博客体量问题，本博客只会总结第八章【排序】的知识点与代码

相关文章：
王道考研数据结构代码总结（前四章）
王道考研数据结构代码总结（第五章）
王道考研数据结构代码总结（第六章）

---

排序

插入排序

直接插入排序

算法思想:每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中,直到全部记录插入完成。

元素不会在一次操作中就到达最终的位置

核心代码（不带哨兵）：

void InsertSort(int A[], int n){
    for (int i = 1; i < n; i ++ ){
        if (A[i - 1] > A[i]){ // 前n-1个数已经是从小到大了，现在出现了比最大的数A[i-1]还小的数,所以要移动
            int temp = A[i], j;
            for (j = i - 1; j >= 0 && A[j] > temp; j -- )  // 开始遍历0~n-1的数,如果当前数比A[i]要大的话,证明A[i]还没有找到它的位置,退出循环的时候,j所指向的数的后面应该是插入点
                A[j + 1] = A[j];     // 边搜边移动这些比A[i]大的数(往后移动一格)
            A[j + 1] = temp;         // j+1所指的位置就是插入点,插入A[i]
        }
    }
}
1
2
3
4
5
6
7
8
9
10

可运行代码（不带哨兵）：

#include 

const int N = 55;

int A[N] = {5, 7, 9, 1, 4, 6, 8, 3};;

void InsertSort(int A[], int n){
    for (int i = 1; i < n; i ++ ){
        if (A[i - 1] > A[i]){ 
            int temp = A[i], j;
            for (j = i - 1; j >= 0 && A[j] > temp; j -- )  
                A[j + 1] = A[j];    
            A[j + 1] = temp;         
        }
    }
}

int main()
{
    InsertSort(A, 8);
    for (int i = 0; i < 8; i ++ ) printf("%d ", A[i]);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

核心代码（带哨兵）：

void InsertSort(int A[], int n){
    for (int i = 2; i <= n; i ++ ){
        if (A[i - 1] > A[i]){
            A[0] = A[i];
            int j;
            for (j = i - 1; A[0] < A[j]; j -- )
                A[j + 1] = A[j];
            A[j + 1] = A[0];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

哨兵就是把数组往后移了一格（空出来 A[0] 当哨兵，效果等同于不带哨兵的 temp，其优点在于每次循环不需要判断 j >= 0 （因为必定有 j=0 时, A[0] == A[j] ，即不满足 A[0] < A[j] 从而退出循环）

可运行代码（带哨兵）：

#include 

const int N = 55;

int A[N] = {0, 5, 7, 9, 1, 4, 6, 8, 3};;

void InsertSort(int A[], int n){
    for (int i = 2; i <= n; i ++ ){
        if (A[i - 1] > A[i]){
            A[0] = A[i];
            int j;
            for (j = i - 1; A[0] < A[j]; j -- )
                A[j + 1] = A[j];
            A[j + 1] = A[0];
        }
    }
}

int main()
{
    InsertSort(A, 8);
    for (int i = 1; i <= 8; i ++ ) printf("%d ", A[i]);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

总结：

1.空间复杂度：$O(1)$
2.时间复杂度：$O(n^2)$
3.由于我们在比较的时候仅仅是将比 A[i] 大的进行交换,所以算法是的算法是稳定的
4.算法中的元素在一趟无法确定其最终位置

折半插入

思路:先用折半查找找到应该插入的位置,再移动元素

核心代码（带哨兵）：

void InsertSort(int A[], int n){
    for (int i = 2; i <= n; i ++ ){
        A[0] = A[i];    // 哨兵
        int low = 1, high = i - 1;
        while (low <= high){
            int mid = (low + high) / 2;
            if (A[mid] > A[0]) high = mid - 1;   // 这里需要记一下是先看high的更新
            else low = mid + 1;
        }
        for (int j = i - 1; j >= high; j -- )    // 这里也需要记一下j是拿high为界
            A[j + 1] = A[j];
        A[high + 1] = A[0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

可运行代码（带哨兵）：

#include 

const int N = 55;

int A[N] = {0, 5, 7, 9, 1, 4, 6, 8, 3};;

void InsertSort(int A[], int n){
    for (int i = 2; i <= n; i ++ ){
        A[0] = A[i];   
        int low = 1, high = i - 1;
        while (low <= high){
            int mid = (low + high) / 2;
            if (A[mid] > A[0]) high = mid - 1; 
            else low = mid + 1;
        }
        for (int j = i - 1; j >= high; j -- )   
            A[j + 1] = A[j];
        A[high + 1] = A[0];
    }
}

int main()
{
    InsertSort(A, 8);
    for (int i = 1; i <= 8; i ++ ) printf("%d ", A[i]);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

总结：

1.空间复杂度：$O(1)$
2.时间复杂度：$O(n^2)$
3.算法是稳定的
4.算法中的元素在一趟无法确定其最终位置

希尔排序

先将待排序表分割成若干形如 L[i, i +d, i + 2d.... , i + kd]的“特殊”子表,对各个子表分别进行直接插入排序。缩小增量$d$，重复上述过程，直到 d = 1 为止。

核心代码（不带哨兵）：

void ShellSort(int A[], int n){
    // A[0]是暂存单元,不是哨兵
    for (int d = n / 2; d >= 1; d = d / 2)   // 步长
        for (int i = d + 1; i <= n; i ++ )   // 它是所有的有序增量子表"交替"的进行插入排序
            if (A[i] < A[i - d]){            // 将A[i]插到有序增量子表中
                A[0] = A[i];
                int j;
                for (j = i - d; j > 0 && A[0] < A[j]; j -= d) // 查找插入位置
                    A[j + d] = A[j];  
                A[j + d] = A[0];        // 插入
            }
}
1
2
3
4
5
6
7
8
9
10
11
12

可运行代码（不带哨兵）：

#include 

const int N = 55;

int A[N] = {0, 5, 7, 9, 1, 4, 6, 8, 3};;

void ShellSort(int A[], int n){
    for (int d = n / 2; d >= 1; d = d / 2)   
        for (int i = d + 1; i <= n; i ++ )  
            if (A[i] < A[i - d]){           
                A[0] = A[i];
                int j;
                for (j = i - d; j > 0 && A[0] < A[j]; j -= d) 
                    A[j + d] = A[j];  
                A[j + d] = A[0];       
            }
}

int main()
{
    ShellSort(A, 8);
    for (int i = 1; i <= 8; i ++ ) printf("%d ", A[i]);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

总结：

1.空间复杂度：$O(1)$
2.时间复杂度：$O(n^2)$[最坏]，$O(n^{1.3})$[$n$在某个范围内时]
3.算法是不稳定的
4.算法中的元素在一趟无法确定其最终位置

链表的插入排序

移动元素的次数变少了，但是关键字对比的次数依然是$O(n^2)$数量级,整体来看时间复杂度依然是$O(n^2)$

对链表的插入排序，只能使用直接插入排序

插入类排序总结

1.空间复杂度：$O(1)$
2.时间复杂度：平均$O(n^2)$，最好(原本有序) $O(n)$，最坏(原本逆序) $O(n^2)$
3.算法是稳定的（除希尔排序）
4.算法中的元素在一趟无法确定其最终位置

交换排序

冒泡排序

从后往前(或从前往后)两两比较相邻元素的值，若为逆序(即A[i - 1] > A[i])，则交换它们，直到序列比较完。称这样过程为“一趟”冒泡排序。

冒泡排序过程中的优化：若一趟排序没有发生交换，那么证明此时已经整体有序。

核心代码：

void sawp(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

void BubbleSort(int A[], int n){
    for (int i = 0; i < n - 1; i ++ ){      // i所指位置之前的元素都已"有序"
        bool flag = false;
        for (int j = n - 1; j > i; j -- ){  // 开始冒泡
            if (A[j - 1] > A[j]){           // 只有在这种交换条件下才是稳定的
                swap(A[j], A[j - 1]);
                flag = true;
            }
        }
        if (flag == false) return;          // 遍历完一趟之后没有发生交换,说明表已有序
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

可运行代码：

#include 

const int N = 55;

int A[N] = {5, 7, 9, 1, 4, 6, 8, 3};;

void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

void BubbleSort(int A[], int n){
    for (int i = 0; i < n; i ++ ){
        bool flag = false;
        for (int j = n - 1; j > i; j -- ){
            if (A[j - 1] > A[j]){
                swap(A[j], A[j - 1]);
                flag = true;
            }
        }
        if (flag == false) return;
    }
}

int main()
{
    BubbleSort(A, 8);
    for (int i = 0; i < 8; i ++ ) printf("%d ", A[i]);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

总结：

1.空间复杂度：$O(1)$
2.时间复杂度：$O(n^2)$
3.算法是稳定的
4.算法中的元素在一趟可以确定其最终位置
5.可以用于链表（从前往后"冒泡",每一趟将更大的元素"冒"到链尾）

快速排序

算法思想：在待排序表 L[1...n] 中任取一个元素 pivot 作为枢轴(或基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分 L[1...k-1] 和 L[k+1...n]，使得 L[1...k-1]中的所有元素小于pivot ，L[k+1...n] 中的所有元素大于等于 pivot，则 pivot 放在了其**最终**位置 L(k) 上，这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止,即所有元素放在了其最终位置上。

核心代码：(必背)

// 用第一个元素将待排序序列划分为左右两个部分
int Partition(int A[], int low, int high){
    int pivot = A[low];    // 选取第一个元素作为枢轴
    while (low < high){    // 用low和high搜索pivot的最终位置
		while (low < high && A[high] >= pivot) -- high;
    	A[low] = A[high];      // 比枢轴小的元素移动到左端
    	while (low < high && A[low] <= pivot) ++ low;
    	A[high] = A[low];  
    }  
    A[low] = pivot;
    return low;            // 返回存放枢轴的最终位置
}

// 快速排序
void QuickSort(int A[], int low, int high){
    if (low < high){                               // 递归跳出条件
        int pivotpos = Partition(A, low, high);    // 划分,并把枢轴元素放到它最终的位置上
        QuickSort(A, low, pivotpos - 1);           // 划分左子表
        QuickSort(A, pivotpos + 1, high);          // 划分右子表
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

可运行代码：

#include 

const int N = 55;

int A[N] = {5, 7, 9, 1, 4, 6, 8, 3};;

int Partition(int A[], int low, int high){
    int pivot = A[low];    
    while (low < high){    
		while (low < high && A[high] >= pivot) -- high;
    	A[low] = A[high];      
    	while (low < high && A[low] <= pivot) ++ low;
    	A[high] = A[low];  
    }  
    A[low] = pivot;
    return low;            
}

void QuickSort(int A[], int low, int high){
    if (low < high){                             
        int pivotpos = Partition(A, low, high);    
        QuickSort(A, low, pivotpos - 1);           
        QuickSort(A, pivotpos + 1, high);          
    }
}

int main()
{
    QuickSort(A, 0, 7);
    for (int i = 0; i < 8; i ++ ) printf("%d ", A[i]);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

总结：

1.空间复杂度：$O(lo{g}_{2}n)$[最好]，$O(n)$[最坏]
2.时间复杂度：$O(nlo{g}_{2}n)$[最好]，$O(n^2)$[最坏]
3.最坏情况分析：每一次枢轴元素的选取之后都将排序序列划分为很不均匀的两个部分，即导致递归层数增加，算法效率变低【若初始序列为有序或逆序，则快速排序的性能最差】
4.最好情况分析：每一次选中的枢轴元素都可以将待排序列划分为均匀的两个部分，这样递归深度最小，算法效率最高
5.排序算法的优化思路：尽可能选取可以把数据中分的枢轴元素。
6.快速排序是所有内部排序算法中平均性能最优的排序算法
7.算法是不稳定的
8.算法中的元素的 “一次划分” 可以确定其最终位置，“一趟排序” 也许可以确定多个元素的最终位置
9.不可以应用于链表

选择排序

简单选择排序

每一趟在待排序元素中选取关键字最小的元素加入有序子序列，即 $n$ 个元素的简单排序需要 $n-1$ 趟处理（最后一个元素不用再处理）。

核心代码：

void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

void SelectSort(int A[], int n){
    for (int i = 0; i < n - 1; i ++ ){
        int min = i;
        for (int j = i + 1; j < n; j ++ )
            if (A[j] < A[min]) min = j;
        if (min != i) swap(A[min], A[i]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

可运行代码：

#include 

const int N = 55;

int A[N] = {5, 7, 9, 1, 4, 6, 8, 3};;

void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

void SelectSort(int A[], int n){
    for (int i = 0; i < n - 1; i ++ ){
        int min = i;
        for (int j = i + 1; j < n; j ++ )
            if (A[j] < A[min]) min = j;
        if (min != i) swap(A[min], A[i]);
    }
}

int main()
{
    SelectSort(A, 8);
    for (int i = 0; i < 8; i ++ ) printf("%d ", A[i]);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

总结：

1.空间复杂度：$O(1)$
2.时间复杂度：$O(n^2)$
3.算法是不稳定的
4.算法中的元素在一趟可以确定其最终位置
5.无论有序、逆序、还是乱序，一定需要 $n-1$ 趟处理
6.可以用于链表

堆排序

若n个关键字序列L[1…n]满足下面某一条性质，则称为堆(Heap)：
①若满足：L(i) ≥ L(2i) 且 L(i) ≥ L(2i + 1) (1 ≤ i ≤ n / 2) ——大根堆(大顶堆) 【父节点比孩子们都大】
②若满足：L(i) ≤ L(2i) 且 L(i) ≤ L(2i + 1) (1 ≤ i ≤ n / 2) ——小根堆(小顶堆) 【父节点比孩子们都小】

建立大根堆：

思路：把所有非终端结点 i <= ⌊n / 2⌋ 都检查一遍（从 i == n / 2 查到 i == 1），是否满足大根堆的要求,如果不满足，则进行调整
检查当前结点是否满足根 ≥ 左、右,若不满足,将当前结点与**更大的一个孩子**互换
更小的元素下坠,可能会导致下一层的子树不符合大根堆的规则
若元素互换破坏了下一级的堆，则采用相同的方法继续往下调整(小元素不断“下坠”)

**注：**堆的建立和堆的插入是不一样的，堆的建立是查非终端结点并与孩子进行交换（自上而下），堆的插入则是先插入到堆的末尾后看是否需要向上调整（自下而上）

基于大根堆进行排序：

堆排序:每一趟将堆顶元素加入有序子序列(与待排序序列中的最后一个元素交换)，即选择排序：每一趟在待排序元素中选取关键字最大的元素加入有序子序列，并将待排序元素序列再次调整为大根堆(小元素不断“下坠”)

**总结1：**大根堆就是每一个父节点都比比左右孩子大的树，即最大值必为根节点，对大根堆的排序其实得到的是一个递增的序列，每次将根结点（目前未排序列中最大的元素）取下之后与未排序列中的最后一个元 a 素进行交换（即数组的最后几位才是已经有序的部分），然后将元素 a 执行 down 操作使得树（未排序的元素）仍然符合堆的结构

总结2：一个结点每下坠一层最多需要对比 $2$ 次关键字，若树高为 h，某结点在第 i 层,则将这个结点向下调整最多只需要“下坠” h-i 层，关键字对比次数不超过 2(h-i)，n个结点的完全二叉树树高 $h=\lfloor lo{g}_{2}n\rfloor +1$，建堆的时间复杂度为 $O(n)$，每一趟下坠的时间复杂度为 $O(lo{g}_{2}n)$
1.堆排序的时间复杂度为 $O(n)+O(nlo{g}_{2}n)=O(nlo{g}_{2}n)$
2.堆排序的空间复杂度为 $O(1)$
3.若左右孩子一样大,则优先和左孩子交换
4.堆排序是不稳定的
5.算法中的元素在一趟可以确定其最终位置
6.基于大根堆得到的是递增序列，基于小根堆得到的是递减序列

堆的插入

对于小根堆,新元素放到表尾，与父节点对比,若新元素比父节点更小,则将二者互换。新元素就这样一路“上升”,直到无法继续上升为止

堆的删除

被删除的元素用堆底元素替代,然后让该元素不断“下坠”,直到无法下坠为止

归并排序

归并:把两个或多个已经有序的序列合并成一个

只剩一个子表未合并时,可以将该表中剩余元素全部加到总表

二路归并：二合一，每选出一个小元素注需对比关键字 $1$ 次
四路归并：四合一，每选出一个小元素注需对比关键字 $3$ 次

结论：$m$ 路归并，每选出一个元素需要对比关键字 $m-1$ 次

核心代码：

int *B = (int *)malloc(n * sizeof(int));   // 辅助数组B

// A[low...mid]和A[mid+1...high]各自有序,将两个部分归并
void Merge(int A[], int low, int mid, int high){ 
    for (int k = low; k <= high; k ++ )
        B[k] = A[k];
    int i, j, k;
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k ++ ){
        if (B[i] <= B[j])       // 两个元素相等的时候优先去排靠前面那个(稳定性)
            A[k] = B[i ++];
        else
            A[k] = B[j ++];
    }
    while (i <= mid) A[k ++] = B[i ++];
    while (j <= high) A[k ++] = B[j ++];
}

void MergeSort(int A[], int low, int high){
    if (low < high){
        int mid = (low + high) / 2;     // 从中间划分
        MergeSort(A, low, mid);         // 右边归并
        MergeSort(A, mid + 1, high);    // 左边归并
        Merge(A, low, mid, high);       // 归并
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

可运行代码：

#include 
#include 

const int N = 55;

int A[N] = {5, 7, 9, 1, 4, 6, 8, 3};;

int *B = (int *)malloc(10 * sizeof(int));   // 辅助数组B

// A[low...mid]和A[mid+1...high]各自有序,将两个部分归并
void Merge(int A[], int low, int mid, int high){ 
    for (int k = low; k <= high; k ++ )
        B[k] = A[k];
    int i, j, k;
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k ++ ){
        if (B[i] <= B[j])       // 两个元素相等的时候优先去排靠前面那个(稳定性)
            A[k] = B[i ++];
        else
            A[k] = B[j ++];
    }
    while (i <= mid) A[k ++] = B[i ++];
    while (j <= high) A[k ++] = B[j ++];
}

void MergeSort(int A[], int low, int high){
    if (low < high){
        int mid = (low + high) / 2;     // 从中间划分
        MergeSort(A, low, mid);         // 右边归并
        MergeSort(A, mid + 1, high);    // 左边归并
        Merge(A, low, mid, high);       // 归并
    }
}

int main()
{
    MergeSort(A, 0, 7);
    for (int i = 0; i < 8; i ++ ) printf("%d ", A[i]);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

总结：n个元素的2路归并排序

1.空间复杂度：$O(n)$，来自于辅助数组 B
2.归并趟数 $O(\lceil lo{g}_{2}n\rceil )$
3.每趟归并的时间复杂度为 $O(n)$，算法的时间复杂度为 $O(nlo{g}_{2}n)$
4.算法中的元素在一趟不可以确定其最终位置
5.算法是稳定的

基数排序

比如要求得到关键字“递减”的有序序列

第一趟：

初始态：

中间状态：

结束态（第一趟）：

第一趟收集结束：

第二趟：

第三趟：

基数，如上例中十进制的基数就是10，即每一位可以取 $[0,9]$，初始化的队列需要有 $r$ 个

$d$元组，如上例中 d = 3，即我们分为个，十，百，三个不同的权值。
总结：

1.空间复杂度：$O(r)$，需要 $r$ 个辅助队列
2.时间复杂度：一趟分配 $O(n)$，收集一个队列只需 $O(1)$ 时间，一趟收集 $r$ 个队列共 $O(r)$，总共 $d$ 趟分配、收集，总的时间复杂度$=O(d(n+r))$
3.算法是稳定的
4.算法中的元素在一趟不可以确定其最终位置
基数排序擅长解决的问题：

①数据元素的关键字可以方便地拆分为 $d$ 组，且 $d$ 较小；反例：给5个人的身份证号排序
②每组关键字的取值范围不大，即 $r$ 较小；反例：给中文人名排序
③数据元素个数 $n$ 较大；擅长：给十亿人的身份证号排序