_{王道C++班级参考资料}
——
C语言部分^卷6算法基础
^{_节2基础排序算法}

最新版本V3.0
王道C++团队
COPYRIGHT ⓒ 2021-2024. 王道版权所有

概述

_Gn!

在本小节中，我们先来学习三种基础的排序算法：

1. 选择排序

2. 冒泡排序

3. 插入排序

其中插入排序是比较重要，比较常用的。

选择排序

_Gn!

选择排序(Selection Sort)是一种简单直观、非常易于理解、符合人类"暴力求解问题"思维的排序算法。这是一种很笨的排序算法，了解就行，一般在任何情况下都不推荐使用选择排序。

注：在讲解七大排序算法时，我们都会以"将一个整数数组从小到大进行排序"为例子。这么做是为了简化实现，如果需要排序的元素是其他类型或者需要逆序排序，也并不影响排序算法的思想。

假如存在一个数组：[16, 1, 45, 23, 99, 2, 18, 67, 42, 10]

选择排序的基本思路可以参考下图：

工作原理如下：

1. 第一轮选择排序：一开始整个数组都处于未排序状态，记录未排序序列的开头位置(第一轮就是数组首元素)，遍历整个数组找到最小值，将最小值放在未排序序列的开头，然后在未排序的序列中去掉该元素。

2. 第二轮选择排序：除了首元素外，数组所有元素处于未排序状态，记录未排序序列的开头位置(第二轮就是数组的第二个元素)，遍历剩余未排序序列中的元素找到最小值，将最小值放在未排序序列的开头，然后在未排序的序列中去掉该元素。

3. ....

4. 重复过程：重复1和2两个过程，每一轮选择排序中，都会从剩余未排序的元素中继续寻找最小元素，然后放到未排序的序列的开头。

5. 最后一轮选择排序：直到未排序序列的开头已经是倒数第二个元素，进行最后一轮选择排序。随后未排序序列就只剩最后一个元素，此元素一定就是数组元素最大值，选择排序结束。

选择排序听起来逻辑简单直接，但真的要手写实现，其实还是要仔细琢磨的。用C语言实现，参考代码如下：

选择排序-参考代码

xxxxxxxxxx
49
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3

4
#define ARR_LEN(arr) (sizeof(arr) / sizeof(arr[0]))
5
#define SWAP(arr, i, j ) {      \
6
    int tmp = arr[i];           \
7
    arr[i] = arr[j];            \
8
    arr[j] = tmp;               \
9
}
10

11
void print_arr(int arr[], int len) {
12
    for (int i = 0; i < len; i++) {
13
        printf("%d ", arr[i]);
14
    }
15
    printf("\n");
16
}
17

18
// 选择排序
19
void selection_sort(int arr[], int len) {
20
    /*
21
    * i表示未排序序列的开头元素
22
    * 最后一轮选择排序时, 未排序序列的开头元素是数组倒数第二个元素
23
    * i的每个取值都表示一轮选择排序
24
    * 也就是选择排序一共执行9趟
25
    */ 
26
    for (int i = 0; i < len - 1; i++) {
27
        // 不妨直接假设未排序序列的开头i位置元素就是最小值
28
        int min_index = i;
29
        // 遍历未排序数组序列,找出真正的最小值下标,此时应遍历最后一个元素
30
        for (int j = i + 1; j < len; j++) {
31
            if (arr[j] < arr[min_index]) {
32
                min_index = j;  // 记录较小值的下标
33
            }
34
        }   // for循环结束时，未排序序列的最小值下标就是min_index
35

36
        // 交换min_index和下标i的元素
37
        SWAP(arr, min_index, i);
38
        // 选择排序一趟打印一次数组
39
        print_arr(arr, len);
40
    }
41
}
42

43
int main(void) {
44
    // 测试选择排序
45
    int arr[] = { 1,10,2,5,3,4,5,6,3,2 };
46
    int len = ARR_LEN(arr);
47
    selection_sort(arr, len);
48
    return 0;
49
}

时间复杂度分析：

在分析以比较为核心的排序算法的时间复杂度时，我们重点关注两点就可以了：

1. 比较次数

2. 交换元素次数

在选择排序当中，无论什么情况下，比较次数和交换元素次数都是一样的：

1. 比较次数：

2. 每一轮的比较次数会随着未排序序列减少递减

3. 即一共比较(n - 1) + (n - 2) + ... + 1 = n * (n - 1) / 2 次（等差数列求和）

4. 交换元素次数：数组一共有n个元素，除了末尾元素不需要交换，其它元素都需要交换，固定交换(n - 1)次。

将两者加起来就是总的指令执行数量。

除此之外，我们发现选择排序，在数组已经有序、逆序还是完全无序的各种情况下，这些比较和交换都不会减少。

所以用大O表示法，选择排序的时间复杂度是O(n²)，任何情况下都一样。

空间复杂度分析：

选择排序是一种原地排序算法，不需要占用额外内存空间。空间复杂度是O(1)

稳定性分析：

选择排序稳定吗？答：不稳定！

选择排序在每一轮中选择最小元素，并与未排序部分的第一个元素交换。如果存在相等的元素，选择排序可能会改变它们的相对顺序。所以选择排序不是一个稳定的排序算法。

这样的例子随手可举，比如对于一个数组：

[3, 5, 3', 2, 8]

两个3是相同的元素，相对位置是3在前，3'在后。在选择排序后，得出结果是：

[2, 3', 3 , 5, 8]

变成3'在前，3在后。

冒泡排序

_Gn!

冒泡排序(Bubble Sort)同样是一种简单直观的排序算法，当然它的效率同样很一般。一般来说，冒泡排序同样被认为是一种仅具有教学意义的排序算法，不会作为实际应用。

以数组[16, 1, 45, 23, 99, 2, 18, 67, 42, 10]为例子，其基本的思路可以参考下图：

工作原理如下(按照从小到大排序)：

1. 第一轮冒泡排序：从数组的第一个元素开始，比较相邻的元素。如果第一个元素比第二个元素大，则交换它们的位置。然后，移动到下一对相邻元素，重复这个过程，直到比较最后一对元素。每一轮冒泡排序都会使当前比较序列的最大值到达数组末尾，随后第二轮排序过程中，需要比较的元素就减1。(将尾部最大的元素减去不再排序)

2. 第二轮冒泡排序：重复第一轮的过程，但这次只比较和交换直到倒数第二个元素（因为最后一个元素已经是最大的了）。在这一轮结束时，倒数第二大的元素会被“冒泡”到倒数第二的位置。

3. ...

4. 结束条件：

   1. 在不设置任何额外结束条件的前提下，冒泡排序每一轮都会将未排序序列的最大值"冒泡"到末尾。冒泡排序需要进行固定的(n - 1)轮！

   2. 但实际上在这(n - 1)轮冒泡排序的过程中，只要某一轮完全不存在元素的交换，就说明数组已经完全有序了，排序就可以结束了。

   3. 所以我们可以设定一个布尔值来标记此轮冒泡排序是否存在元素交换，如果没有元素交换，直接结束整个排序。这种做法可以优化冒泡排序的性能，尤其是当原数组已基本有序时。

参考代码如下：

冒泡排序-参考代码

xxxxxxxxxx
52
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3

4
#define ARR_LEN(arr) (sizeof(arr) / sizeof(arr[0]))
5

6
#define SWAP(arr, i, j ) {      \
7
    int tmp = arr[i];           \
8
    arr[i] = arr[j];            \
9
    arr[j] = tmp;               \
10
}
11

12
void print_arr(int arr[], int len) {
13
    for (int i = 0; i < len; i++) {
14
        printf("%d ", arr[i]);
15
    }
16
    printf("\n");
17
}
18

19
void bubble_sort(int arr[], int len) {
20
    // 外层for的i表示第几轮冒泡排序,最多需要进行len-1轮
21
    for (int i = 1; i < len; i++) {
22
        // 标记在这一次冒泡排序中有没有交换,false表示没有交换
23
        bool swapped = false;
24
        /*
25
        * j表示两两比较元素中的第一个元素的下标
26
        * 第一轮j的最大取值是数组倒数第二个元素,并且逐步减小
27
        * 所以j的条件是小于 (len - i)
28
        */ 
29
        for (int j = 0; j < len - i; j++) {
30
            if (arr[j] > arr[j + 1]) {
31
                SWAP(arr, j, j + 1);
32
                // 发生了交换改变标记
33
                swapped = true;
34
            }
35
        }
36
        // 在一轮冒泡排序中没有任何交换,则排序已经完成,终止循环
37
        if (!swapped) {
38
            break;
39
        }
40
        // 打印一轮冒泡排序后数组的元素排列
41
        print_arr(arr, len);
42
    }
43
}
44

45
int main(void) {
46
    // 测试冒泡排序
47
    int arr[] = { 16, 1, 45, 23, 99, 2, 18, 67, 42, 10 };
48
    int len = ARR_LEN(arr);
49
    bubble_sort(arr, len);
50

51
    return 0;
52
}

需要注意的是：

在上述参考代码中使用了"swapped"标记来使得冒泡排序可以在"一轮冒泡没有任何交换时结束"。这在某些场景下，可以提升算法的效率，尤其是最佳情况——输入的数组已经是有序的情况下。

假设n为数组的长度，分析以下复杂度：

时间复杂度分析：

最佳情况：由于使用了"swapped"标记，所以在最佳情况下，即输入的数组已经是有序的情况下，算法仅需要一次数组遍历就可以确定排序完成。

即：

比较次数： (n - 1)

交换次数： 0

所以最佳情况下的时间复杂度是 O(n)。

最坏情况：

在最坏的情况下（当数组完全逆序时），冒泡排序第一轮需要执行( n - 1) 次比较和交换，第二次执行( n - 2 )次，依此类推，直到最后一次执行 1 次。所以，总的执行次数是等差数列求和：n * ( n - 1) / 2。所以最坏情况下的时间复杂度是 O(n²)。

平均情况：在平均情况下，时间复杂度也是 O(n²)。虽然不是所有的元素都需要交换，但总体而言，性能接近最坏情况。

空间复杂度分析：

冒泡排序是一种原地排序算法，不需要占用额外内存空间。空间复杂度是O(1)

稳定性分析：

冒泡排序显然是一种稳定的排序算法，因为交换的过程中不会交换任何两个相同的元素。

插入排序

_Gn!

插入排序(Insertion Sort)同样是一种非常简单、直观的排序算法。当然它的效率同样不高。

插入排序的过程就非常类似于我们在打扑克的过程中，抓牌——整理手牌顺序——再抓牌...的过程。

其基本的思路可以参考下图：

工作原理是(将数组从小到大排序)：

1. 以数组的首元素为初始状态：这个初始状态相当于抓到的第一张牌，它默认就是有序的。

2. 从数组的第二个元素开始遍历：相当于抓一张牌，然后从小到大整理手牌。

3. 比较与交换：将新插入的元素和前面的元素逐一比较，如果新插入元素较小，则交换两个元素，直到完全不可交换，则完成一轮排序。

4. 重复步骤2和3，直到步骤2遍历到最后一个元素。

参考代码如下：

插入排序交换元素实现-参考代码

xxxxxxxxxx
36
1
#define SWAP(arr, i, j ) {      \
2
    int tmp = arr[i];           \
3
    arr[i] = arr[j];            \
4
    arr[j] = tmp;               \
5
}
6
#define ARR_LEN(arr) (sizeof(arr) / sizeof(arr[0]))
7

8
void print_arr(int arr[], int len) {
9
    for (int i = 0; i < len; i++) {
10
        printf("%d ", arr[i]);
11
    }
12
    printf("\n");
13
}
14

15
// 通过交换元素的方式实现插入排序
16
void insertion_sort(int arr[], int len) {
17
    // 外层for循环中的i表示每轮选择排序新插入元素的下标,也就是"新摸手牌"的下标
18
    // 从数组第二个元素开始,后面的每一个元素都相当于"你要摸的手牌"
19
    for (int i = 1; i < len; i++) {
20
        // 内层for循环的j表示新插入元素需要比较元素的下标,也就是每一张"老手牌"的下标
21
        // j从i的前一个位置开始,递减,但不可能成为负数
22
        for (int j = i - 1; j >= 0; j--) {
23
            if (arr[j] > arr[j + 1]) {  // 注意:这里如果加等号就不是稳定的排序算法了
24
                // 前面的元素比后面的元素大,交换
25
                SWAP(arr, j, j + 1);
26
            }
27
            else {
28
                // 只需要在某一次比较中,发现前一个元素小于等于后一个元素
29
                // 那么前面的元素就一定都是排序好的,此时这一轮选择排序结束
30
                break;
31
            }
32
        }
33
        // 打印每一轮选择排序后,数组的元素序列
34
        print_arr(arr, len);
35
    }
36
}

上面的实现是通过交换元素取值实现排序的，交换是一个比较"重量级"的操作，需要连续三次赋值来完成。所以我们可以用移动元素来取代交换元素，这样可以轻微提升一些性能。思路是：

先使用一个temp临时存储新插入元素，然后和前面的元素逐一比较，若前面的元素较大就向后移动一位，直到比较完前面所有元素或者比较到一个元素比新插入元素小。

参考代码如下：

插入排序移位元素实现-参考代码

xxxxxxxxxx
35
1
// 插入排序 优化: 用向后移动腾出插入位置,然后插入实现插入排序
2
void insertion_sort2(int arr[], int len) {
3
    // 现在第一个元素就是第一张手牌,从第二个元素开始就是每一次要摸的牌
4
    // 外层for循环代表每一轮摸到的新手牌, 也就是每一轮插入排序
5
    for (int i = 1; i < len; i++) {
6
        // 先记录一下新手牌的值, 便于后续的插入操作
7
        int tmp = arr[i];
8
        int j = i - 1;
9
        for (;j >= 0; j--) {
10
            if (arr[j] > tmp) { // 注意:不能加=,加了就不是稳定排序算法了
11
                arr[j + 1] = arr[j];    // 将旧手牌中大于新手牌的所有牌都向后移
12
            }
13
            else
14
            {
15
                break;  // 只要发现一张旧手牌更小或相等, 就说明已经找到新手牌的插入位置了
16
            }
17
        }
18
        /*
19
            现在还有一件事情没做:新手牌要插入,需要确定插入位置
20
            分析: for循环什么时候结束?
21
            两种情况:
22
            1.j=-1时,循环结束,说明新手牌是最小的,所以插入到0这个位置,也就是j+1
23
            2.arr[j] <= tmp 也就是旧手牌更小或相等,此时新手牌放在j+1的位置
24
        */
25
        arr[j + 1] = tmp;
26
        print_arr(arr, len);    // 每一轮摸牌后查看排序后的数组
27
    }
28
}
29

30
int main(void) {
31
    int arr[] = { 1, 21, 45, 231, 99, 2, 18, 7, 4, 9 };
32
    int len = ARR_SIZE(arr);
33
    insertion_sort2(arr, len);
34
    return 0;
35
}

这个优化后的版本，由于减少了操作指令的次数，可以轻微的提升算法效率。虽然这个提升并不会带来什么质变，但对于算法而言，点滴的提升都是有必要的。

性能分析

_Gn!

以版本2为选择排序的实现，假设n为数组的长度，分析以下复杂度：

时间复杂度分析：

最佳情况：

1. 当输入的数组已经是排序好的，此时不需要移动任何元素，但比较还是需要的。

2. 比较次数(外层for循环次数)：(n - 1)

3. 移动次数：0

所以最佳情况下的时间复杂度是 O(n)。

最坏情况：

1. 在最坏的情况下，即数组完全逆序时。

2. 比较和交换的次数是相同的，第一轮需要比较和移动1次，第二轮需要比较和移动2次....最后一个元素需要比较和移动 (n - 1)次

3. 等比数列求和：需要比较和移动各n(n-1)/2次，加起来就是T(n²- n)

所以最坏情况下的时间复杂度是 O(n²)。

平均情况：

1. 在平均情况下，可以粗略的认为移动次数和比较次数是最坏情况除以2

2. 所以在平均情况下，时间复杂度也是 O(n²)。

空间复杂度分析：

插入排序是一种原地排序算法，不需要占用额外内存空间。空间复杂度是O(1)

稳定性分析：

插入排序显然也是一种稳定的排序算法，因为对于两个相同的元素，我们始终都不会交换它们的相对位置。

注意：如果判断的条件改成arr[j] >= arr[j + 1]，即在前后元素相等时也交换/移动元素，算法就会变成不稳定的。

总结

_Gn!

选择排序、冒泡排序和插入排序都是基础的排序算法，同样的基于比较而实现，同样的简单直观，同样的原地算法。

这里对它们做一个总结分析：

1. 选择排序在任何情况下时间复杂度都是O(n²)，且它是一个不稳定的排序算法。比起作为算法去使用，它更具有教学意义，一般不推荐去使用它。

2. 冒泡排序和插入排序看起来很类似，它们都有最坏和平均情况下O(n²)的时间复杂度，都有最优情况下O(n)的时间复杂度。但在小数据集或者数据集基本有序的情况下，仍然更推荐使用插入排序。

这是因为：

1. 插入排序的移动操作比冒泡排序的交换操作效率更高。在冒泡排序中，每轮冒泡都可能涉及大量交换元素操作，而插入排序用移动操作替代了交换。从指令执行数量上来说，移动操作效率更高。

2. 在数据基本有序的情况下，插入排序往往表现要更好。这是因为在数据基本有序的情况下，插入排序往往只需要挪动元素很少的次数，而冒泡排序可能还需要，慢慢的一步步的两两交换多次。这里同样存在移动操作和交换操作指令数量上的差异！

The End