排序算法_总述

发表于2021-11-11更新于2025-08-10阅读次数

八大排序算法，归于 5 类

有八种典型的排序算法，可归于五大类：

  1. 插入排序
    1. 直接插入排序
    2. 希尔排序
  2. 选择排序
    1. 简单选择排序
    2. 堆排序
  3. 交换排序
    1. 冒泡排序
    2. 快速排序
  4. 归并排序
  5. 基数排序

稳定性

两要素：

  1. 两个元素相同
  2. 排序后这两个元素是否能保持原来的顺序

以下讨论的默认都是从小到大的排序。

插入排序（直接、希尔）

直接插入排序

依次从待排序序列中取值，向已排序序列中投放，保证再次完全有序，直到待排序列中所有值取完。

插入排序大多数都是两层循环。

直接插入排序的思想：将待排序数据分为两部分，左边为有序的，右边是无序的。
从右边拿一个数据插入到左边（为了方便，每次拿右边的第一个数据），
需保持左边继续有序，直到右边没有数据。

过程可以参照扑克牌插入排序。

《算法导论》写法

思想：j指向的是左侧已排序的末尾。i指向的是未排序的开头。
外部for是从左到右遍历i的。
内部for是从右到左遍历j的。
每次，a[i]存入到了tmp，让a[j]和tmp比较，若大于，说明还没找到tmp（a[i]）应该在的位置。则--j继续找，直到找到一个小于tmp的位置。那么，退出内部for，把tmp存入到它的右边一个位置a[j + 1] = tmp。开始下一个a[i]的排序。

这个《算法导论》的写法可读性不如《算法》的写法，推荐看后者的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void straight_insert_sort(int a[], int n)
{
    for(int i = 1; i < n; ++i)
    {
        int tmp = a[i];
        for(int j = i - 1; j > -1; --j)//j指示欲插入的位置的前一个
        {
            if(a[j] > tmp)//移动
            {
                a[j + 1] = a[j];
            }
            else break;//j不减1
        }
        a[j + 1] = tmp;
    }
}

for循环体中的条件判断可以与for表达式合并

1
2
3
4
5
6
7
8
9
10
11
12
13
void straight_insert_sort(int a[], int n)
{
    for(int i = 1; i < n; ++i)
    {
        int tmp = a[i];
        for(int j = i - 1; tmp < a[j] && j > -1; --j)
        {
            a[j + 1] = a[j];
        }
        //j指示插入位置的前一个位置
        a[j + 1] = tmp;
    }
}

《算法》写法

在每遍历一个值时，直接把i和j同时指向了一个位置。第 0 个位置跳过（排序算法的常见套路，第 0 个位置略过，当作已排序数据）。

同时，不用存tmp了，直接封装到了swap函数中。

内部for循环条件，看a[j - 1]是否大于a[j]，大于则交换。
内部for循环做的事情，就是让a[i]在左侧（j的区域），从右到左，找到合适的位置插入。

1
2
3
4
5
6
7
8
9
10
void straight_insert_sort(int a[], int n)
{
    for(int i = 1; i < n; ++i)
    {
        for(int j = i; a[j - 1] > a[j] && j > 0; --j)
        {
            swap(&a[j], &a[j - 1]);
        }
    }
}
情况 时间复杂度
最好情况 O(n)O(n)
平均情况 O(n2)O(n^2)
最坏情况 O(n2)O(n^2)

希尔排序 - 插入排序的优化

《算法》的写法 - 3x+1 增量

最大间隔为 n / 3。每次除以 3 取整，间隔序列长度是O(log⁡3n)O(\log_3 n)级别。1, 4, 13, 40, 121, 364, 1093, …

在插入排序中加入一个外循环，来将 h 按照递增序列递减，就能得到这个简洁的希尔排序。
增幅 h 的初始值是数组长度乘以一个常数因子，最小为1。

假设 n 是 10 ，n / 3 是 3。则 h 初值为 4。
先按 下标间隔 4 进行排序。让数组a 每 4 个有序，即：0、4、8有序，1、5、9有序，2、6（没有10）有序，3、7有序。
再让 h 递减，h = h / 3，得 h 为 1 。即按 下标间隔 1 进行排序。让数组a 每 1 个有序，即：0、1、2、3、4、5、6、7、8、9有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void shell_sort(int a[], int n)
{
    int h = 1;
    while (h < n / 3) h = 3 * h + 1; // h 可能是 1, 4, 13, 40, 121, 364, 1093, ...
    while (h >= 1)
    {
        // 将数组变为 每 h 有序
        for (int i = h; i < n; ++i)
        {
            // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中
            for (int j = i; j - h > -1 && a[j] < a[j - h]; j -= h)
            {
                swap(&a[j], &a[j - h]);
            }
        }
        h = h / 3;
    }
}

在最坏的情况下该算法的比较次数 和 N3/2N^{3/2} 成正比。
经验平均复杂度（大量随机输入）：O(n3/2)O(n^{3/2})
最坏情况复杂度：O(n2)O(n^{2})。Shell 排序没有严格的最坏情况次方级优化保证，某些特殊序列会退化到平方级
最好情况复杂度（数组已经有序）：O(nlog⁡n)O(n \log n)。因为每个 h 排序只需一次线性扫描

Bubo的写法 - 折半增量

这是折半增量序列，虽然在常数因子上比普通插入排序好，但在数据规模大时明显慢于用 3x+1 序列的排序。

最大间隔为n / 2。增量依次为：n/2,n/4,n/8,…,1。序列长度 约等于 log⁡2n\log_2 n。 1, 2, 4, 8, 16, 32, 64, …

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void shell_sort(int a[], int n)
{
    for(int k = n / 2; k > 0; k /= 2) // k为组距或组数
    {
        // 组内进行"直接插入排序"
        for(int i = k; i < n; i += k)
        {
            for(int j = i; j > k - 1 && a[j - k] > a[j]; j -= k)
            {
                swap(&a[j - k], &a[j]);
            }
        }
    }
}

由于最后一次 k=1 等同于直接插入排序，且前几轮效果不够显著，总体时间复杂度：O(n2)O(n^2)
平均情况：依然接近O(n2)O(n^2)。比单纯的插入排序快常数倍，但数量级不变。
最好情况：如果数组初始就是有序的，每轮只做一次扫描，复杂度：O(nlog⁡n)O(n \log n)

情况 时间复杂度
最好情况 O(nlog⁡n)O(n \log n)
平均情况 O(n2)O(n^2)
最坏情况 O(n2)O(n^2)
所以，这种（折半增量）如果不在序列增量（3x+1 增量）上进行优化，还不如直接用直接插入排序。

3x+1 对比 折半 增量的优势

插入排序的一个核心特点 —— 它的效率高度依赖数据的有序程度，所以序列不同性能差异会很大。

折半增量的早期问题：
当 gap 很大时（比如 n/2）：

  • 子序列很短：
    gap = n/2 → 每个子序列只有 2 个元素
    gap = n/4 → 每个子序列只有 4 个元素
  • 比较覆盖度低：
    大 gap 排序时，只比较很稀疏的元素对，大部分元素间的相对顺序并没有直接调整
  • 逆序对消除效率低：
    Shell 排序的性能提升依赖于尽早减少逆序对
    但大 gap 只能消除相隔很远的逆序对，很多局部逆序（相隔 < gap 的）还留着，等到 gap 变小时才会处理

3x+1 增量 对比 折半增量的优势

  • 折半增量 n/2=8 第一轮时，每个子序列长度只有 2，对局部逆序几乎没影响；
  • 3x+1 第一轮 h=13 时，子序列长达 3 或 4，能一次调整更大范围的元素，迅速减少逆序对
  • 到 h=1 时，3x+1 版本剩下的乱序非常少，所以最后插入排序很快

原始数组（逆序）：
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

折半增量第一轮：

1
2
3
原始：16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1
gap=8: (16,8), (15,7), (14,6), (13,5), (12,4), (11,3), (10,2), (9,1)
结果： 8  7  6  5  4  3  2  1 16 15 14 13 12 11 10  9

虽然位置变化很大，但前 8 个和后 8 个依旧是逆序的；
绝大多数局部逆序还在，下一轮 gap=4 时才开始打乱它们。

3x+1 增量第一轮：

  • 子序列是按下标相差 13 分的分组：
    • 组1: (16, 3)
    • 组2: (15, 2)
    • 组3: (14, 1)
    • 其他元素只和自己比较
  • 对每个子序列进行插入排序：
1
3  2  1 13 12 11 10  9  8  7  6  5  4 16 15 14

3x+1 增量第二轮（h = 4）

  • 子序列（间隔 4）
    • 组1: (3, 12, 8, 4)
    • 组2: (2, 11, 7, 16)
    • 组3: (1, 10, 6, 15)
    • 组4: (13, 9, 5, 14)
  • 各组内部插入排序：

结果：
3 2 1 5 8 7 6 9 12 11 10 13 4 16 15 14
（已经更接近有序）

插入排序总结

  • 逆序对分析：时间复杂度与数组中的逆序对数量成正比
  • 与希尔排序关系：希尔排序是插入排序的推广（多间隔插入），解决了大规模数据移动代价高的问题
  • 实际案例：C++ STL 的 std::sort 对小数组（一般 ≤ 32 元素）内部会用插入排序收尾（快速排序的尾递归部分），因为它在缓存命中率和分支预测上很高效。
  • 非常适合小规模或接近有序的数据
  • 不同的增量序列 → 决定了希尔排序每一轮能消除多少逆序对 → 决定了最后 gap=1 时的工作量 → 直接影响性能。

增量序列的作用

  • 希尔排序的效率，取决于它能多快把逆序对减少到接近 0。
  • gap 很大时 → 只能消除长距离的逆序对（下标差 ≥ gap）
  • gap 变小时 → 才能处理更短距离的逆序对（下标差 < gap）

最后一轮 gap=1（普通插入排序） → 必须处理剩余所有短距离逆序对

  1. 折半增量（n/2, n/4, …, 1）
    • 前几轮 gap 很大时，每个子序列很短
    • 只能消除少量长距离逆序对，很多短距离逆序对要留到最后一次 gap=1 时处理
    • 导致最后一轮几乎是完整的 O(n2)O(n^2) 插入排序
  2. 优化过的增量（3x+1）
    • gap 序列递减比例较小（约 2~3 倍），而不是直接减半
    • 每一轮的子序列更长，能一次消除多种不同跨度的逆序对
    • 到最后 gap=1 时，数组已经接近有序，逆序对很少 → 插入排序非常快

逆序对是什么？

1
2
3
[3, 1, 2]
逆序对：(3, 1)、(3, 2)
总共 2 个逆序对。

选择排序（简单、堆排）

每次找到剩余序列中最小的元素，放到已排序序列的尾部（或者看作剩余序列的头部）。
不断地选择剩余元素之中的最小者。

简单选择排序

《算法》的写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void selection_sort(int a[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        int min_idx = i;
        for (int j = i + 1; j < n; ++j)
        {
            if (a[j] < a[min_idx])
            {
                min_idx = j;
            }
        }
        // 注意，是 a[i]而不是a[j] 和 a[min_idx]交换
        swap(&a[i], &a[min_idx]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
i min   0 1 2 3 4 5 6 7 8 9 10
        S O R T E X A M P L E
0  6    S O R T E X A M P L E
1  4    A O R T E X S M P L E
2  10   A E R T O X S M P L E
3  9    A E E T O X S M P L R
4  7    A E E L O X S M P T R
5  7    A E E L M X S O P T R
6  8    A E E L M O S X P T R
7  10   A E E L M O P X S T R
8  8    A E E L M O P R S T X
9  9    A E E L M O P R S T X
10 10   A E E L M O P R S T X

优化：第一层for中的i可以优化为i < n - 1，因为排最后一个时，剩余序列就1个数了，无需再找最小了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void selection_sort(int a[], int n)
{
    int min_idx;
    for(int i = 0; i < n - 1; ++i)
    {
        min_idx = i;
        for(int j = i + 1; j < n; ++j)
        {
            if(a[j] < a[min_idx])
            {
                min_idx = j;
            }
        }
        swap(&a[i], &a[min_idx]);
    }
}

堆排序

堆的作用是产生一个极值元素。

堆是一种完全二叉树。（区分概念：二叉树、满二叉树、完全二叉树）

总体的排序过程：首先要保证整个二叉树是一个大（小）根堆，即每一个父节点都要比其子节点大（小），如此就能保证整个树的根节点就是最大（小）的节点，即产生了一个极值元素。
我们把它和未排序的最后一个叶子节点互换值，而交换完之后，根节点打乱了大（小）根堆的结构，需要重新保证整个二叉树是一个大（小）根堆，才能产生极值元素与最后位置交换。
如此，循环往复，每找到一个极值点，就换其到最后（归到已排序数列中），就可以达到排序的目的。

其中，找极值元素，即保证树为大（小）根堆的过程，是一个递归过程：因为大（小）根堆的概念就是：完全二叉树中，每一个父节点都要比其子节点大（小）。由于涉及到树，并且涉及到层层相扣的大小关系，因此堆化的过程是一个递归过程。

如果把数据抽象为堆结构去排序，那么首先我们需要建立堆。需要从最后一个非叶子节点进行逆向遍历，依次以节点为根进行堆化。

堆化函数

堆化函数，递归地让整颗完全二叉树每个节点都大于（小于）其子节点。根节点大于字节点则是大根堆，根节点小于子节点则是小根堆。

注意！！！堆化函数只适用于：只有根节点不是大（小）根堆，而其他节点符合大（小）根堆 的情况。

以下的堆化函数，是基于一个root为根到last节点的大根堆。（这段代码，事实上是：由于节点比子节点小，进行下沉操作）
堆化函数，让它确保恢复到大根堆的状态。

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
void heapify(int a[], int root_idx, int last_idx)
{
    int left = root_idx * 2 + 1; //root最小值可能为0
    int right = left + 1;
    // 判断该根节点是否有子节点，如果left超过了last_idx值则退出
    if(left > last_idx) return;
    int max = root_idx;
    // 运行到这里时，left > last_idx，即last_idx <= left，由于是完全二叉树的逻辑结构，因此max一定有左子树，所以我们直接看[left]和[max]的大小关系
    if(a[left] > a[max])
    {
        max = left;
    }
    // 但我们不能确定是否max有右子树，需要判断
    if(right <= last_idx)
    {
        if(a[right] > a[max])
        {
            max = right;
        }
    }
    if(max != root_idx)
    {
        exchange(a, &a[root_idx], &a[max]);
        heapify(a, max, last_idx);
    }
}

堆化函数和优先级队列的关系 - 上浮、下沉函数

优先级队列，可以看作是一个大根堆，根节点的优先级最大。

大根堆中，上浮，swim，或FilterUp。即由于一个节点大于其父节点，上浮。
大根堆中，下沉，sink，或FilterDown。即由于一个节点小于其所有子节点，下放。

我们以下描述的均为数组下标。因此，假设某节点对应的下标为i，则左子节点的下标就为2 * i + 1

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 FilterDown(int a[], int start_idx, int end_idx)
{
    int i = start_idx;
    int j = i * 2 + 1;
    // 看有没有子节点。
    while (j <= end_idx)
    {
        // 看 有没有 右子节点。如果有则 看 左子节点和右子节点哪个更大。
        if (j < end_idx && a[j + 1] > a[j])
        {
            j = j + 1;
        }
        // 把更大的子节点a[j] 与 a[i]比较。如果a[i] 大于等于 a[j]，则 i 节点不用换位置了
        if (a[i] >= a[j])
        {
            break;
        }
        swap(&a[i], &[j]);
        // a[i] 和 a[j] 交换后，i 节点和 它的子节点有序了
        // 但是，j 节点的值换成了 a[i]，有可能 j 节点和它的子节点乱序了。重新开始。
        i = j;
        j = i * 2 + 1;
    }
}

(i - 1) / 2是i节点的父节点。
所谓上浮，是重点关注于该节点本身，与父节点比较大小。无需关注兄弟节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
void FilterUp(int a[], int start_idx)
{
    int i = start_idx;   // 子节点
    int j = (i - 1) / 2; // 父节点
    // 若 子节点 大于 父节点 则 上位
    while (i > 0 && a[i] > a[j])
    {
        swap(&a[i], &a[j]);
        // a[i] 和 a[j] 交换后，i 节点和 它的父节点 j 有序了（目前a[i] < a[j]，子节点小于父节点）
        // 但是，有可能 j 节点 和 j 的父节点 乱序。重新开始。
        i = j;
    }
}

建堆

再次注意！！！堆化函数只适用于只有根节点不是大（小）根堆，而其他节点符合大（小）根堆 的情况。

因此在堆化之前我们应该先建立一个大（小）根堆！

怎么建立大（小）根堆呢？我们要利用上面这个堆化函数。而刚才一直在反复强调，堆化函数只能用于除了根节点没有堆化，其他节点已全部堆化的情况。所以：只能从非叶子节点逆着依次堆化！最后一个非叶子节点为：(last_idx - 1) / 2。（last_idx表示数组下标，从0开始）

1
2
3
4
5
6
7
void create_heap(int a[], int root_idx, int last_idx)
{
    for(int i = (last_idx - 1) / 2; i > -1; --i)
    {
        heapify(a, i, last_idx);
    }
}

排序

如上文，每次产生一个极值元素，和未排序的最后一个叶子节点互换值，就可以达到排序的目的。

1
2
3
4
5
6
7
8
9
10
void heap_sort(int a[], int n)
{
    create_heap(a, 0, n - 1);
    for(int i = n - 1; i > 0; )
    {
        exchange(a, &a[0], &a[i]);
        --i;
        heapify(a, 0, i);
    }
}

用下沉函数进行堆排序

此处，sink，生成了一个大根堆。
之后每次把大根（整棵树的最大值）放到后面，当作已排序序列。再对未排序进行大根化。以此往复。
因此，基于大根堆的排序之后的序列是升序的（从小到大）
同理，基于小根堆的排序之后的序列是降序的（从大到小）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void heap_sort(int a[], int n)
{
    // i 初始化为 尾 节点的 父 节点
    // 从 最后一个 有分支的 节点 开始，一直到 0 节点（整棵树的根）每个 二叉树 都 做一次 大根化 操作
    for (int i = (n - 1) / 2; i >= 0; i--)
    {
        // sink 的 第三个参数传入的是 下标，n - 1指尾节点的下标
        sink(a, i, n - 1);
    }
    int i = n - 1;
    // i 等于 0 时，则 未排序的只剩一个数了，不用再排序。
    while (i > 0)
    {
        // 目前 0 位置就是最大值，放到最后（就是 i 位置），然后最后的边界缩小 1（--i），让 0 到新边界大根化，生成下一个极值。
        swap(&a[0], &a[i]);
        --i;
        sink(a, 0, i);
    }
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void bubble_sort(int a[], int n)
{
    for(int i = 0; i < n - 1; ++i)
    {
        // 每完成一次 内部 for 循环，都会为 已排序序列 确定一个数。因此 已排序序列的边界 更新为 i
        for(int j = n - 1; j > 0 + i; --j)
        {
            // 把 左边大的数 交换到了 右边，因此最后生成了 升序序列（从小到大）
            if(a[j - 1] > a[j])
            {
                swap(&a[j - 1], &a[j]);
            }
        }
    }
}

第一层for循环退出的条件可以由i < n优化成i < n - 1。因为当i == n - 1时，最后的数一定是最大的数。

优化：如果第一次for循环，从尾部到头部一路比较下来，发现，没有交换过，说明这是一个已经有升序的序列，直接return，不再进行往后无谓的排序了。
最好情况（已排序数组）只需 O(n)O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void bubble_sort(int a[], int n)
{
    for(int i = 0; i < n - 1; ++i)
    {
        int is_exchanged = 0;
        for(int j = n - 1; j > 0 + i; --j)
        {
            if(a[j - 1] > a[j])
            {
                swap(&a[j - 1], &a[j]);
                is_exchanged = 1;
            }
        }
        if(!is_exchanged)
            return;
    }
}

快速排序

划分基准

在快速排序中，最重要的即为划分过程，每个数的位置将在每一次划分后确定。

那么，基准值（pivot）其实可以从未定序列（除了确定位置的其他值）中随机选择。

在不同教材中，讲解的快速排序往往有两大方案，一是每次选择左首为基准，二是每次选择右尾为基准进行划分。

在《算法导论》中，选择的是右尾；
在《算法》（普林斯顿大学）中选择的是左首。
在Bubo的讲解中，选择的是右尾；
在老杨派系的讲解中，选择的是左首。
在网络上，大部分选择的是左首。

划分方向 - 左右向 + 单双向

除了基准位置的选取不同。迭代方向也有所不同：分为单向（单轴）法（需要分左右）、双轴法等。

这些各式各样的方法，无所谓其细节，其实达到的效果都是一样的，

即我们需要关注其核心本质，不要忘了快速排序中，划分函数的初心是什么。

所以，我们可以想象，如果每次选择左首划分，那么其实给元素的位置交换多了一些麻烦，即出现不同的情况。

而如果选择右尾划分，我们可以发现，划分区域的扩张过程很简洁，那么元素的位置交换也不需要太多的分情况，所以思路相对简洁。

总的来说，划分的方式有三大要素：左首、右尾划分；单向、双向划分；左、右划分（如果是双向划分则是先左后右或先右后左）

单向划分方法又称为：Lomuto 分区（Lomuto partition scheme）
双向划分（向中间逼近）又称为：Hoare 分区（Hoare partition scheme）
单向、双向都是把数组分成了两个区域加一个基准值。
还有一种三路划分（Dutch National Flag partition），是分成了三个区域，小于的、等于的、大于的。
三路划分单独处理了数组中和基准值重复过多的情况。

总之，可分为：

  1. 左首、单向、左划分；
  2. 左首、单向、右划分；
  3. 左首、双向、先左后右划分；
  4. 左首、双向、先右后左划分；
  5. 右尾、单向、左划分；
  6. 右尾、单向、右划分；
  7. 右尾、双向、先左后右划分；
  8. 右尾、双向、先右后左划分；
  9. 三路划分

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
void quick_sort_3way(int a[], int left, int right)
{
    if (left >= right) return;
    int pivot = a[left];
    int lt = left, i = left + 1, gt = right; // a[left..lt - 1] < p, a[lt ..gt] == p, a[gt+1..right] > p
    while (i <= gt)
    {
        if (a[i] < pivot)
        {
            swap(&a[lt], &a[i]);
            ++lt;
            ++i;
        }
        else if (a[i] > pivot)
        {
            swap(&a[i], &a[gt]);
            --gt;
        }
        else
        {
            ++i;
        } // a[i] == pivot
    }
    quick_sort_3way(a, left, lt - 1);
    quick_sort_3way(a, gt + 1, right);
}

1：左首、单向、左划分（老杨）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void quick_sort(int a[], int left, int right)
{
    if (left >= right) return;
    int pivot = a[left];
    int i = left;
    int j = i + 1;
    // j 遍历向右
    while (j <= right)
    {
        if (a[j] <= pivot)
        {
            swap(&a[i + 1], &a[j]);
            ++i;
        }
        ++j;
    }
    // i 的位置是 左侧部分的末尾。
    // left 属于 左侧部分。不应与i+1交换，而是与i交换
    swap(&a[i], &a[left]);
    // i 的位置是基准值，已固定。只需排除了i之后剩下的。
    quick_sort(a, left, i - 1);
    quick_sort(a, i + 1, right);
}

优化：if (a[j] <= pivot)中最好把<=改为<。

  1. 优化前，如果数组中等值太多，则会进行多次无意义的交换。
    • 设数组全是相同值，选左端为轴。
    • 对每个 j，a[j] <= pivot 都成立，于是 i 每次自增，循环结束后 i == right，最后再把 pivot 和 a[i] 交换——轴被放到最右端。
    • 递归变成：[left, right-1]（规模 n-1）和空区间。于是递归关系 T(n)=T(n-1)+O(n)，整体退化到 O(n^2)。
  2. 优化后，用 < 会好一点（少很多交换），但在“全等/大量重复”的数据上还是会退化到 O(n2)O(n^2)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void quick_sort(int a[], int left, int right)
{
    if (left >= right) return;
    int pivot = a[left];
    int i = left;
    int j = i + 1;
    // j 遍历向右
    while (j <= right)
    {
        if (a[j] < pivot)
        {
            swap(&a[i + 1], &a[j]);
            ++i;
        }
        ++j;
    }
    // i 的位置是 左侧部分的末尾。
    // left 属于 左侧部分。不应与i+1交换，而是与i交换
    swap(&a[i], &a[left]);
    // i 的位置是基准值，已固定。只需排除了i之后剩下的。
    quick_sort(a, left, i - 1);
    quick_sort(a, i + 1, right);
}

3：左首、双向、先左后右划分（《算法》 - 普林斯顿大学）

以左首为基准的双向划分，不推荐先从左划分，代码可读性不太好，而且最后i、j边界不能乱用。
以左首为基准的双向划分，推荐先右后左划分（老杨版本）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//此方法是前置++，i和j的位置最后不一定重合，会错开1位！
//由于是以左首划分，那么最后替换到左首的值则应该是一个小于（等于）左首的值。
//以上两个条件决定了，必须选择a[j]（即j停下来的位置的值）与左首交换，则j就作为确定的划分界限。

//另外，左右划分的顺序无所谓！先左先右都可以！
void quick_sort(int a[], int left, int right)
{
    if (left >= right) return;
    int i = left, j = right + 1;//为了便于下面++i和--j的代码统一性，所以从left到right+1，实际上只考察到了left+1到right的部分
    int pivot = a[left];
    while(1)
    {
        while(a[++i] <= pivot)
            if(i == right) break;
        while(a[--j] > pivot)
            if(j == left) break;
        if(i >= j) break;
        swap(&a[i], &a[j]);
    }
    swap(&a[left], &a[j]);// a[left]为左首元素，即基准值
    quick_sort(a, left, j - 1);
    quick_sort(a, j + 1, right);
}

可读性更好的自用版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void quick_sort(int a[], int left, int right)
{
    if (left >= right) return;

    int pivot = a[left];
    int i = left + 1, j = right;

    while (1)
    {
        while (i <= j && a[i] <= pivot) ++i; // 停在 > pivot
        while (i <= j && a[j] >  pivot) --j; // 停在 <= pivot
        if (i > j) break;
        swap(&a[i], &a[j]);
        ++i; --j;
    }
    // 轴与 j 交换，保证 [left..j-1] <= pivot，pivot 在 j
    swap(&a[left], &a[j]);

    quick_sort(a, left, j - 1);
    quick_sort(a, j + 1, right);
}

指针交错（或相遇）后应把 pivot 与 a[j] 交换，而不是和 a[i]。用 i 会出错（如 [1,3,2] 会变成 [3,1,2]）。

4：左首、双向、先右后左划分（仿照Bubo的“右尾、双向、先左后右划分”方法写的，见7）

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
void quick_sort(int a[], int left, int right)
{
    if (left >= right) return;
    int l = left + 1, pivot = left, r = right;
    while (l < r)
    {
        if (a[r] > a[pivot])
            --r;
        else if (a[l] <= a[pivot]) 
            ++l;
        else
            swap(&a[l], &a[r]);
    }
    if (a[r] > a[pivot])
    {
        swap(&a[r - 1], &a[pivot]);
        pivot = r - 1;
    }
    else
    {
        swap(&a[r], &a[pivot]);
        pivot = r;
    }
    quick_sort(a, left, pivot - 1);
    quick_sort(a, pivot + 1, right);
}

上面的代码是初版，最后的if-else想复杂了，以下是优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void quick_sort(int a[], int left, int right)
{
    if (left >= right) return;
    int l = left + 1, pivot = left, r = right;
    while (l < r)
    {
        if (a[r] > a[pivot])
            --r;
        else if (a[l] <= a[pivot])
            ++l;
        else
            swap(&a[l], &a[r]);
    }
    if (a[l] < a[pivot])
    {
        swap(&a[l], &a[pivot]);
        pivot = l;
    }
    quick_sort(a, left, pivot - 1);
    quick_sort(a, pivot + 1, right);
}

⭐老杨版（挖坑法）

挖坑法（又叫“填坑法”）是快速排序的一种原地分区写法：先把轴值（pivot）暂存出来，把它原来的位置当成“坑”，然后从数组两端向中间扫，用遇到的元素去“填”当前的坑；被搬走的位置又形成新的坑，交替进行，直到左右指针相遇，最后把轴值放回这个最终的坑。

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
void quick_sort(int a[], int left, int right)
{
    if (left >= right) return;
    int pivot = a[left];
    int i = left;
    int j = right;
    while (i < j)
    {
        while (i < j && a[j] > pivot)
        {
            --j;
        }
        if (i < j) // a[right] <= pivot
        {
            a[i] = a[j];
        }
        while (i < j && a[i] <= pivot)
        {
            ++i;
        }
        if (i < j) // a[left] >= pivot
        {
            a[j] = a[i];
        }
    }
    a[i] = pivot;
    quick_sort(a, left, i - 1);
    quick_sort(a, i + 1, right);
}

⭐5：右尾、单向、左划分（北航算法）

left到i的区域为小于等于基准值的区域。

在划分结束前，i + 1到right的区域，均为大于基准值的区域。

划分结束后，i + 1为基准值最后落到的位置。（需要单独进行a[i+1]和a[right]的交换）

left和right均为数组下标。

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 quick_sort(int a[], int left, int right)
{
    if(left >= right) return;
    int i = left - 1, j = left;
    int pivot = a[right];
    while(j < right)
    {
        if(a[j] > pivot)
        {
            ++j;
        }
        else
        {
            swap(&a[i + 1], &a[j]);
            ++i;
            ++j; // 不管if是否成立，都++j
        }
    }
    // i 的位置是 左侧部分的末尾。
    // right 属于 右侧部分。不应与i交换，而是与i+1交换
    swap(&a[i + 1], &a[right]);
    quick_sort(a, left, i);
    quick_sort(a, i + 2, right);
}

if-else优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void quick_sort(int a[], int left, int right)
{
    if(left >= right) return;
    int i = left - 1, j = left;
    int pivot = a[right];
    while(j < right)
    {
        if(a[j] <= pivot)
        {
            swap(&a[i + 1], &a[j]);
            ++i;
        }
        ++j;  // 不管if是否成立，都++j
    }
    // i 的位置是 左侧部分的末尾。
    // right 属于 右侧部分。不应与i交换，而是与i+1交换
    swap(&a[i + 1], &a[right]);
    quick_sort(a, left, i);
    quick_sort(a, i + 2, right);
}

i的初始值应为left - 1

以上程序，i的初始值不应是left，而是left - 1：

怎么记住呢？我们可以想象一下，如果划分两个元素，那么right = 1，left = 0。如果i一开始和j都等于left，那么如果a[j] <= pivot，则a[i + 1]和a[j]交换，这时i + 1是right，造成小数在右，所以错误。

实际上，i、j指示器分别代表左、右部分的末端。

两个极端的情况就是：如果i超出数组左边界（值为-1）则说明左部分为空，即没有比基准值小于（等于）的值；
如果j超出待排数组右边界（当以右尾划分时，j超出边界时值为right）则说明右部分为空，即没有比基准值大的值。

遍历数组过程中，主要依托j的行进，如果遇到的值比基准值大，则j单独进步；如果遇到值比基准值小（等），则需要与右部分的首位置替换，如此，遇到的小的值去了左部分，原先首位置的值换到了右部分的最末端。最后，i和j同时进一步。

7：右尾、双向、先左后右划分：（Bubo）

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
//这个版本下，left和right必定相等
//但是，存在一种情况，即只有两个元素进行划分，如2、3；
//那么此时left和right一上来就相等，都指向2
//如果我们不去做a[l]和a[pivot]的大小对比，那么最后就会划分为3、2（3为基准），此时发现，2比3小，却错误的排到后面了。
//所以，必须在后面加上a[l]和右尾值的大小对比！才能进行替换

//另外，此方法不能交换划分顺序！即必须先左划分，后右划分，否则错误！
void quick_sort(int a[], int left, int right)
{
    if (left >= right) return;
    //此时若只有两个元素，则出现l == r
    int l = left, pivot = right, r = right - 1;
    while (l < r)
    {
        if (a[l] <= a[pivot])
            ++l;
        else if (a[r] > a[pivot])
            --r;
        else
            swap(&a[l], &a[r]);
    }
    if (a[l] > a[pivot])
    {
        swap(&a[l], &a[pivot]);
        pivot = l;
    }
    quick_sort(a, left, pivot - 1);
    quick_sort(a, pivot + 1, right);
}

8：右尾、双向、先右后左划分；（仿照“左首、双向先左后右划分”《算法》写的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void quick_sort(int a[], int left, int right)
{
    if (left >= right) return;
    int i = left - 1, j = right;//为了便于下面++i和--j的代码统一性，所以从left-1到right，实际上只考察到了left到right-1的部分
    int pivot = a[right];
    while (1)
    {
        while (a[--j] > pivot)
            if (j == left) break;
        while (a[++i] <= pivot)
            if (i == right) break;
        if (i >= j) break;
        swap(&a[i], &a[j]);
    }
    swap(&a[right], &a[i]);// a[right]为右尾元素，即基准值 //必须和a[i]交换，否则不对
    quick_sort(a, left, i - 1); // 必须是i - 1，否则不对
    quick_sort(a, i + 1, right);// 必须是i + 1，否则不对
}

其实我们发现，先左后右划分也正确，但是后三句中的基准位置是i，不能是j

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void quick_sort(int a[], int left, int right)
{
    if (left >= right) return;
    int i = left - 1, j = right;//为了便于下面++i和--j的代码统一性，所以从left-1到right，实际上只考察到了left到right-1的部分
    int pivot = a[right];
    while (1)
    {
        while (a[++i] <= pivot)
            if (i == right) break;
        while (a[--j] > pivot)
            if (j == left) break;
        if (i >= j) break;
        swap(&a[i], &a[j]);
    }
    swap(&a[right], &a[i]);// a[right]为右尾元素，即基准值 //必须和a[i]交换，否则不对
    quick_sort(a, left, i - 1); // 必须是i - 1，否则不对
    quick_sort(a, i + 1, right);// 必须是i + 1，否则不对
}

总结

1
2
3
4
若用前置++，i和j的位置最后不一定重合，可能会错开1位！
由于是以左首划分，那么最后替换到左首的值则应该是一个小于（等于）左首的值。
以上两个条件决定了，必须选择a[j]（即j停下来的位置的值）与左首交换，则j就作为确定的划分界限。
相反，如果以右尾划分，那么替换到右尾的值则应该是一个大于（等于）右尾的值。则必须选择a[i]与右尾交换，则i就作为确定的划分界限。

综上所述，快排划分函数的细节需要注意：

  1. 如果你选择的是双向划分——最终的i、j指针是一定重合吗？有可能错开1位吗？
    1. 如果错开1位，则先左先右无所谓！
    2. 如果一定重合，则必须有个先左或先右的顺序！（为什么呢？）
  2. 你选择以左首或右尾划分，决定了你最后替换左首（右尾）的条件和具体位置！这个和i、j错不错开没关系！如果选择左首划分，则需要拿比左首小的值与之替换；如果选择右尾划分，则需要拿比右尾大的值与之替换；
    1. 如果你的方法有可能使i、j错开，那么i停下的位置一定是比基准值大于（等于）的；j停下的位置一定是比基准值小于（等于）的
    2. 如果你的方法使i、j最后一定重合，那么由于两个元素时i、j也恰巧重合，所以不能直接替换左首（右尾），需要比较i（或j，他俩一样，无所谓），如果你选择左首划分，则判断左首是否比i（或j）位置的值小（等）；如果你选择右尾划分，则判断右尾是否比i（或j）位置的值大（等）——若不是，则交换值，更新基准下标（pivot）；

非递归形式

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
41
42
43
44
45
46
47
48
49
int Partition(int * ar, int left, int right)
{
    int i = left;
    int j = right;
    int pivot = ar[left];
    while (i < j)
    {
        while (i < j && ar[j] > pivot)
        {
            --j;
        }
        if (i < j) // ar[j] <= pivot
        {
            ar[i] = ar[j];
        }
        while (i < j && ar[i] <= pivot)
        {
            ++i;
        }
        if (i < j)
        {
            ar[j] = ar[i];
        }
    }
    ar[i] = pivot;
    return i;
}
void QuickSort(int * ar, int n)
{
    std::queue<int> qu;
    qu.push(0);
    qu.push(n - 1);
    while (!qu.empty())
    {
        int left = qu.front(); qu.pop();
        int right = qu.front(); qu.pop();
        int mid = Partition(ar, left, right);
        if (left < mid - 1)
        {
            qu.push(left);
            qu.push(mid - 1);
        }
        if (mid + 1 < right)
        {
            qu.push(mid + 1);
            qu.push(right);
        }
    }
}

优化：随机基准或三位取中

优化：尾递归消除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// partition 返回轴最终下标 p；两侧为 [left, p-1] 与 [p+1, right]
void quick_sort(int a[], int left, int right)
{
    while (left < right)
    {
        int p = partition(a, left, right);  // 任选 Lomuto/挖坑，保证返回轴位 p
        // 递归较小一侧，较大一侧用循环“缩区间”
        if (p - left < right - p)
        {
            quick_sort(a, left, p - 1);  // 小的那半递归
            left = p + 1;                // 大的那半转为尾部迭代
        }
        else
        {
            quick_sort(a, p + 1, right);
            right = p - 1;
        }
    }
}

最终代码

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
41
42
43
#define INSERTION_SORT_THRESHOLD 16

// 三数取中：把 a[left], a[mid], a[right] 排成 a[left] <= a[mid] <= a[right]，然后把中位数放到 left 当轴
static inline void median_of_three_to_left(int a[], int left, int right)
{
    int mid = left + ((right - left) >> 1);
    if (a[mid]   < a[left])  swap_int(&a[mid]  , &a[left]);
    if (a[right] < a[left])  swap_int(&a[right], &a[left]);
    if (a[right] < a[mid])   swap_int(&a[right], &a[mid]);
    // 此时 a[left] <= a[mid] <= a[right]，取中位数作为轴：交换到 left
    swap_int(&a[left], &a[mid]);
}
// 快速排序（挖坑法 + 尾递归消除 + 小区间插排 + 三数取中选轴）
void quick_sort(int a[], int left, int right)
{
    while (left < right)
    {
        // 小区间用插入排序更快
        if (right - left + 1 <= INSERTION_SORT_THRESHOLD)
        {
            insertion_sort(a, left, right);
            return;  // 当前区间完成，直接返回（外层 while 退出）
        }

        // 选轴优化：三数取中，并将中位数放到 left
        median_of_three_to_left(a, left, right);

        // 分区
        int p = partition_pit(a, left, right);

        // 尾递归消除：总是递归较小的一侧，较大的一侧改为迭代
        if (p - left < right - p)
        {
            quick_sort(a, left, p - 1);  // 递归较小段
            left = p + 1;                // 大段转为下一轮循环
        }
        else
        {
            quick_sort(a, p + 1, right);
            right = p - 1;
        }
    }
}

归并排序

归并排序涉及到分治（Divide & Conquer）策略的思想。分治策略有很多例子，比如MapReduce用于大规模数据集（大于1TB）的并行运算。涉及"Map（映射）“和"Reduce（归约）”。

需要注意，min和max是绝对下标，即要排序的整个数组的下标。

1
2
3
4
5
6
7
8
void divide_conquer(int a[], int min, int max, int b[])
{
    if(min >= max) return;              //终止条件
    int mid = (max - min) / 2 + min;    //找到中间位置(奇数时左边多1个)
    divide_conquer(a, min, mid, b);     //处理完之后，此次递归时的min~max的左半侧已经有序
    divide_conquer(a, mid + 1, max, b); //处理完之后，此次递归时的min~max的有半侧已经有序
    conquer(a, min, max, b);            //conquer即合并两边数组的前提是左右双边均已有序
}

conquer即合并两边数组的前提是左右双边均已有序。

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
void conquer(int a[], int min, int max, int b[])
{
    int mid = (max - min) / 2 + min;
    int i = min;      //左半边
    int j = mid + 1;  //右半边
    int k = min;      //合并的新空间的下标
    while(k <= max)
    {
        if(i <= mid && j <= max)//i和j都没到结尾，则需要一一比对大小
        {
            if(a[i] < a[j])
            {
                b[k] = a[i++];
            }
            else b[k] = a[j++];
        }
        else if(i > mid)        //左半侧已结束，则右半侧(j)剩下的可直接全部放入b
        {
            b[k] = a[j++];
        }
        else b[k] = a[i++];     //右半侧已结束，右半侧(i)剩下的可直接全部放入b
        ++k;
    }
    // 别忘了b数组中处理完成之后还要复制一份给a数组
    for(int k = min; k <= max; ++k)
    {
        a[k] = b[k];
    }
}
1
2
3
4
5
6
7
void merging_sort(int a[], int n)
{
    int * b = (int *)malloc(n * sizeof(a[0]));
    divide_conquer(a, 0, n - 1, b);
    // 无须再把b数组复制给a数组，因为再conquer过程中b数组已经复制给了a数组
    free(b);
}

基数排序

用的少，考的少，基本上已经退出历史舞台，暂不讨论。

随机数-测试用

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
#include<stdio.h>
#include<time.h>
#define SIZE 13
void show(int * arr, int len)
{
    for(int i = 0; i < len; ++i)
    {
        printf("%i  ", arr[i]);
    }
    printf("\n");
}
bool isSort(int * arr, int len)
{
    for(int i = 0; i < len - 1; ++i)
    {
        if(arr[i] > arr[i + 1])
            return false;
    }
    return true;
}
int main()
{
    int arr[SIZE] = { 0 };
    // 设置一个随即因子
    srand((unsigned)(time(NULL)));
    for(int i = 0; i < SIZE; ++i)
    {
        arr[i] = rand() % 100;
    }
    show(arr, SIZE);  //展示原始数据
    XXX(arr);         //调用排序算法
    show(arr, SIZE);  //展示排后数据
    if(isSort(arr, SIZE))
        printf("数据已经完全有序\n");
    else printf("数据无序\n");
}

为何快速排序和归并排序很重要

因为这两个算法可以把整个数据进行划分，所以可以使用多线程处理划分的任务，处理完后，最后再用一个主线程处理所有数据。这是可划分算法的优势。