排序

定义

排序算法，是一种将一组特定的数据按某种顺序进行排列的算法。

理解

排序，就是将输入数据按照一定的顺序重新排列，得到有序的输出数据。
最常用的排序方式是数值顺序以及字典顺序。
最终的输出数据，有以下两个特点：

  1. 是已经按照特定的顺序排列好的有序序列。
  2. 是输入序列的一种排列或重组。

常用排序算法

理解排序的概念是很容易的，但实现排序的方式多种多样。
常用的排序算法包括：选择排序、冒泡排序、插入排序、堆排序、归并排序、快速排序等。
接下来，将以如下问题为例，介绍各排序算法：

给定一维整数数组 aa（包含 nn 个元素，下标从 00 开始），用排序算法将其排列为非递减序列。

选择排序

选择排序是一种简单直观的排序算法。
工作原理是每次找出第 ii 小的元素（也就是 ai...na_{i...n} 中最小的元素），然后将这个元素与数组第 ii 个位置上的元素交换。

选择排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 O(n2)O(n^2)。

代码模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
void selection_sort(vector<int>& a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int tmp = i; // tmp 记录 a[i...n] 中最小元素的下标
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[tmp]) {
                tmp = j;
            }
        }
        swap(a[i], a[tmp]); // a[i...n] 中最小元素与 a[i] 交换，保证第 i 小的元素在位置 i 上
    }
    return;
}

冒泡排序

冒泡排序是一种简单的排序算法。由于在算法的执行过程中，较小的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序。
工作原理是每次检查相邻两个元素，如果前面的元素大于后面的元素，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。经过 ii 次扫描后，数列的末尾 ii 项必然是最大的 ii 项，因此冒泡排序最多需要扫描 n−1n-1 遍数组就能完成排序。

在序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为 O(n)O(n)。在最坏情况下，冒泡排序要执行 (n−1)n2\frac{(n-1)n}{2} 次交换操作，时间复杂度为 O(n2)O(n^2)。冒泡排序的平均时间复杂度为 O(n2)O(n^2)。

代码模板如下：

1
2
3
4
5
6
7
8
9
10
void bubble_sort(vector<int>& a, int n) {
    for(int i = 0; i < n - 1; i++){ // 外层循环总共执行 n - 1 次
        for(int j = 0; j < n - 1 - i; j++){ // 内层循环通过交换相邻的两项，将第 i 大的元素交换到数组的末尾第 i 个位置
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
            }
        }
    }
    return;
}

插入排序

插入排序是一种简单直观的排序算法。
工作原理是将待排列元素划分为「已排序」（a0...i−1a_{0...i-1}）和「未排序」（ai...n−1a_{i...n - 1}）两部分，每次从「未排序」的元素中选择一个（选择 aia_i）插入到「已排序」的元素中的正确位置。

插入排序的最优时间复杂度为 O(n)O(n)，在数列几乎有序时效率很高，最坏时间复杂度和平均时间复杂度都为 O(n2)O(n^2)。

代码模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
void insertion_sort(vector<int>& a, int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) { // 把 key(a[i]) 插入到「已排序」的元素中的正确位置
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
    return;
}

堆排序

堆排序是指利用「二叉堆」这种数据结构所设计的一种排序算法。其本质是建立在堆上的选择排序。
工作原理首先是基于输入数组建立大顶堆，然后将堆顶的元素取出，作为最大值，与数组尾部的元素交换，并维持残余堆的性质；之后将堆顶的元素取出，作为次大值，与数组倒数第二位元素交换，并维持残余堆的性质；以此类推，在第 n−1n-1 次操作后，整个数组就完成了排序。
堆排序的最优时间复杂度、平均时间复杂度、最坏时间复杂度均为 O(nlog⁡n)O(n\log n)。

代码模板如下：

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
void heap_sort(vector<int>& a, int n){
    // 建立大顶堆
    for(int i = n / 2 - 1; i >= 0; i--){
        heapify(a, i, n - 1);
    }

    // 每次取出堆顶的最大值（a[0]），将其交换到数组尾部
    for(int i = n - 1; i > 0; i--){
        swap(a[0], a[i]);
        heapify(a, 0, i - 1);
    }
    return;
}

//维护大顶堆
void heapify(vector<int>& nums, int start, int end){
    int p = start;
    int c = 2 * start + 1;
    while(c <= end){
        if(c < end && nums[c] < nums[c + 1])  c++;
        if(nums[c] > nums[p]){
            swap(nums[c], nums[p]);
            p = c;
            c = c * 2 + 1;
        }
        else{
            break;
        }
    }
    return;
}

归并排序

归并排序是高效的排序算法。
工作原理包括两个过程：分治和合并。

  1. 分治：将待排序的序列一分为二，划分为左右两段，分别进行排序。
  2. 合并：将两个有序的序列合并为一个有序序列。

归并排序的时间复杂度在最优、最坏与平均情况下均为 O(nlog⁡n)O(n \log n)。

代码模板如下：

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
void merge_sort(vector<int>& a, int l, int r) {
    if (r - l < 1){
        return;
    }
    // 分治
    int mid = l + ((r - l) >> 1);
    merge_sort(a, l, mid), merge_sort(a, mid + 1, r);
    // 合并
    merge(a, l, mid, r);
}

void merge(vector<int>& a, int l, int mid, int r) {
    vector<int> tmp;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[j] < a[i]) {
            tmp.push_back(a[j]);
            j++;
        }
        else{
            tmp.push_back(a[i]);
            i++;
        }
    }

    // 此时一个数组已空，另一个数组非空，将非空的数组并入 tmp 中
    for (; i <= mid; i++) tmp.push_back(a[i]);
    for (; j <= r; j++) tmp.push_back(a[j]);

    // 将存储在临时数组中的结果拷贝回原数组
    for(int k = 0; k < tmp.size(); k++) a[k + l] = tmp[k];
    return;
}

逆序对

对于一个序列 aa，若 i<ji < j 且 ai>aja_i > a_j，则称 aia_i 与 aja_j 构成逆序对。

利用归并排序可以求出序列中逆序对的个数。

在归并排序过程中，分治步骤对左右两半序列进行排序，则可以把左右两半各自内部的逆序对数作为子问题进行计算，因此只需要在合并时考虑当前左右两个序列，“左边一半里一个较大的数”与“右边一半里一个较小的数”构成逆序对的情况，将这一情况下的逆序对个数累加到答案中。
具体来说，在合并操作时，合并两个有序序列 al...mida_{l...mid} 和 amid+1...ra_{mid+1...r} 采用两个指针 ii 和 jj 分别对二者进行扫描，不断比较两个指针所指向元素 aia_i 和 aja_j 的大小，将较小的元素加入到排好序的结果序列中。如果较小的元素是 aja_j，则 ai...mida_{i...mid} 都比 aja_j 要大，都会与 aja_j 构成逆序对。

在代码层面上，只需要修改 merge 函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void merge(vector<int>& a, int l, int mid, int r, int& cnt) { // cnt 记录逆序对的个数
    vector<int> tmp;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[j] < a[i]) {
            tmp.push_back(a[j]);
            cnt += mid - i + 1; // a[i~mid] 都可以和 a[j] 构成逆序对
            j++;
        }
        else{
            tmp.push_back(a[i]);
            i++;
        }
    }

    for (; i <= mid; i++) tmp.push_back(a[i]);
    for (; j <= r; j++) tmp.push_back(a[j]);

    for(int k = 0; k < tmp.size(); k++) a[k + l] = tmp[k];
    return;
}

快速排序

快速排序，又称分区交换排序，简称「快排」，是一种被广泛运用的排序算法。
工作原理包括三个过程：

  1. 将数列划分为两部分（要求保证相对大小关系）。
  2. 递归到两个子序列中分别进行快速排序。
  3. 不用合并，因为此时数列已经完全有序。

快速排序的最优时间复杂度和平均时间复杂度为 O(nlog⁡n)O(n\log n)，最坏时间复杂度为 O(n2)O(n^2)。

第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系。具体来说，第一步要是要把数列分成两个部分，然后保证前一个子数列中的数都小于后一个子数列中的数。为了保证平均时间复杂度，一般是随机选择序列中一个数 m 来当做两个子数列的分界。之后，维护一前一后两个指针 p 和 q，依次考虑当前的数是否放在了应该放的位置（前一个子序列还是后一个子序列）。如果当前的数没放对，比如说如果后面的指针 q 遇到了一个比 m 小的数，那么可以交换 p 和 q 位置上的数，再把 p 向后移一位。当前的数的位置全放对后，再移动指针继续处理，直到两个指针相遇。

代码模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void quick_sort(vector<int>& a, int l, int r){
    if (l < r) {
        int p = partition(a, l, r);
        quick_sort(a, l, p - 1);
        quick_sort(a, p + 1, r);
    }
}

int partition(vector<int>& nums, int l, int r){ // 快速选择
    int p = rand() % (r - l + 1) + l; // 随机选择一个作为分界
    swap(nums[p], nums[r]);
    int q = l - 1;
    for(int i = l; i < r; i++){
        if(nums[i] < nums[r]){
            swap(nums[++q], nums[i]);
        }
    }
    swap(nums[++q], nums[r]);
    return q;
}

第 k 大数

第 k 大数被定义为序列排成升序时，倒数第 k 个位置上的数。

可以借助快速排序的思想解决这个问题。
考虑快速排序的划分过程，在快速排序的「划分」结束后，序列 al...ra_{l...r} 被分成了 al...pa_{l...p} 和 ap+1...ra_{p + 1...r}，此时可以按照右边元素的个数 r−pr - p 和 kk 的大小关系来判断是只在左边还是只在右边递归地求解。
如果采用随机选取分界值的方式，可以证明在期望意义下，程序的时间复杂度为 O(n)O(n)。

在代码层面上，只需要利用快速排序中的 partition 函数就可以找到第 k 大数：

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
int find_kth_largest(vector<int>& a, int k) {
    int len = a.size();
    int l = 0, r = len - 1;
    int tmp;
    while(1){
        tmp = partition(a, l, r);
        if(tmp == len - k) break;
        else if(tmp < len - k){
            l = tmp + 1;
        }
        else{
            r = tmp - 1;
        }
    }
    return a[tmp];
}

int partition(vector<int>& nums, int l, int r){ // 快速选择
    int p = rand() % (r - l + 1) + l; // 随机选择一个作为分界
    swap(nums[p], nums[r]);
    int q = l - 1;
    for(int i = l; i < r; i++){
        if(nums[i] < nums[r]){
            swap(nums[++q], nums[i]);
        }
    }
    swap(nums[++q], nums[r]);
    return q;
}

分类

稳定性

稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。
拥有稳定性这一特性的算法会让原本有相等键值的元素维持相对次序，即如果一个排序算法是稳定的，当有两个相等键值的元素 RR 和 SS，且在原本的序列中 RR 出现在 SS 之前，在排序过的序列中 RR 也将会是在 SS 之前。

稳定的排序算法：冒泡排序、插入排序、归并排序等。
不稳定的排序算法：选择排序、堆排序、快速排序等。

时间复杂度

基于比较的排序算法的时间复杂度下限是 O(nlog⁡n)O(n\log n) 。

一般来说，认为
O(n2)O(n^2) 的排序算法：选择排序、冒泡排序、插入排序等。
O(nlog⁡n)O(n \log n) 的排序算法：堆排序、归并排序、快速排序等。