排序是计算机科学中最基础也是最重要的问题之一。本章我们将探讨从基础的 $O(n^2)$ 算法到高效的 $O(n \log n)$ 算法，最后再看看神奇的线性排序 $O(n)$。

基础排序算法 ($O(n^2)$)

这些算法虽然效率不高，但逻辑简单直观，是理解排序的起点。

冒泡排序 (Bubble Sort)

想象一下水底的气泡，轻的气泡会一点点往上冒。冒泡排序也是这个道理：让大的元素像气泡一样，通过一次次交换，"浮"到数组的顶端（末尾）。

冒泡排序的流程是：

  1. 从头开始，比较相邻的两个元素。
  2. 如果前一个比后一个大，就交换它们。目标是让大的元素往后跑。
  3. 这样一轮下来，最大的元素一定会被交换到数组的最后面。
  4. 重复这个过程，只是下一轮不用管最后一个元素了（因为它已经排好了）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0; // 优化标志：如果一轮没发生交换，说明已经排好了
        // 每一轮将最大的元素冒到 n-1-i 的位置
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 发现逆序就执行交换
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break; // 提前下班
    }
}
冒泡排序
正在比较
交换中
已排序
点击"播放"开始演示，或使用"上一步/下一步"逐步观察
步骤 0 / 0

选择排序 (Selection Sort)

选择排序的逻辑非常符合人类直觉：每次从乱堆里挑一个最小的，放到已排好序的队伍后面。

那么符合人类直觉的排序流程就是：

  1. 在整个数组中扫描，找到最小的那个元素。
  2. 把它和数组第一个元素交换位置（现在第一个元素就是最小的了）。
  3. 接着在剩下的元素里再找最小的，放到第二个位置。
  4. 如此往复，直到所有元素都排好。

选择排序比较老实。不管数组是不是已经有序了，它都要从头到尾扫描一遍，所以复杂度永远是 $O(n^2)$。但它的优点是交换次数最少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        // 在 [i, n-1] 区间里找最小值的下标
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }
        // 找到后，把它换到当前位置 i
        if (min_idx != i) {
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }
}
选择排序
当前位置 i
当前最小值
正在比较
已排序
选择排序：每轮从未排序部分找出最小元素，放到已排序部分的末尾
步骤 0 / 0

插入排序 (Insertion Sort)

这就好比我们在打扑克牌理牌。你手里已经有一把排好序的牌，现在摸了一张新牌，你需要从后往前比对，找到合适的位置把它插进去。

首先：

  1. 假设第一个元素已经排好了
  2. 从未排序部分拿出一个元素，并从右往左与已排序的元素逐一比较，找到合适的位置。在这个情况下我们就看这个元素应该插在第一个的前面还是后面
  3. 每次执行上面插入元素的操作时，比它大的元素都要往后挪一位，直到我们将所有的元素完成插入操作，结束排序流程。

如果数组本身就是基本有序的，插入排序会飞快（接近 $O(n)$），因为它几乎不需要挪动元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // 摸到的新牌
        int j = i - 1;
        // 在已排序的手牌里从后往前找位置
        // 如果手牌比新牌大，就往后挪一位
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key; // 插入
    }
}
插入排序
待插入的"新牌" (key)
正在比较
向后移动
已排序区域
插入排序：像打扑克理牌，拿起新牌，从右往左找合适位置插入
步骤 0 / 0

为什么它们都是 $O(n^2)$？(The Inversion Argument)

这里有个很重要的理论概念：逆序对 (Inversion)。
如果 $i < j$ 但 $A[i] > A[j]$，这就叫一个逆序对。排序的本质就是消除所有的逆序对。

交换两个相邻元素，最多只能消除 1 个逆序对。而一个乱序数组平均有 $O(n^2)$ 个逆序对。
所以，任何只通过交换相邻元素来排序的算法（如冒泡、插入），平均都需要 $O(n^2)$ 次操作。

要想突破这个限制，必须进行远距离交换，这就是高级排序算法的秘诀。

堆排序 (Heap Sort)

堆排序利用二叉堆 (Binary Heap) 这种数据结构来实现 $O(n \log n)$ 的排序。

什么是大根堆？

想象一个金字塔，大根堆要求金字塔的每一个"父亲"都要比他的"儿子"们大（或者相等）。
这样一来，塔尖（根节点）永远是最大的。

我们在内存里通常用数组来模拟这个金字塔：

  • 塔尖在数组下标 0。
  • 对于任意一个在 i 位置的节点：
    • 它的左子节点在 2*i + 1
    • 它的右子节点在 2*i + 2
    • 它的父节点在 (i-1)/2，必要时向下取整。

向下堆化 (Heapify)

这是维护金字塔规则的关键。假设有一个节点，它的左右子树都是合格的堆，但它自己可能太小了，配不上"父亲"这个位置。这时候我们就需要把它往下沉：

  1. 看看它和两个子节点谁最大。
  2. 如果某个子节点比它大，就和最大的这个子节点交换位置。
  3. 交换后，它到了新的位置，可能还是比新子节点小，那就继续往下沉，直到它比子节点大，或者沉到底为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 维护以 i 为根的子树的堆性质，n 是堆的大小
void heapify(int arr[], int n, int i) {
    int largest = i;       // 假设当前节点是最大的
    int l = 2 * i + 1;     // 左子节点
    int r = 2 * i + 2;     // 右子节点

    // 如果左子节点比我大，记录下来
    if (l < n && arr[l] > arr[largest])
        largest = l;

    // 如果右子节点比目前最大的还大，记录下来
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // 如果需要执行交换
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest); // 继续调用递归来往下继续检测下沉
    }
}

堆排序流程

有了上面的工具，排序就很简单了：

  1. 首先要建堆：先把乱序数组整理成一个大根堆。

    • 技巧：从最后一个非叶子节点开始，倒着往前一个个做 heapify。这样保证了每个小金字塔都是合规的，最后整个大金字塔就合规了。

  2. 排序：

    • 现在堆顶是最大的元素，把它和数组最后一个元素交换（相当于把最大值扔到最后排好序）。
    • 此时堆顶换上来一个小节点，破坏了大根堆规则。
    • 对堆顶做一次 heapify，让它沉下去，新的老大浮上来。
    • 重复这个过程，直到堆空了就结束排序
1
2
3
4
5
6
7
8
9
10
11
void heapSort(int arr[], int n) {
    // 1. 建堆：从最后一个非叶子节点开始倒序堆化
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 2. 排序：不断把堆顶（最大值）交换到末尾
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]); // 把老大请到最后面去
        heapify(arr, i, 0);     // 剩下的元素重新选老大
    }
}
堆排序
正在比较
交换中
当前处理节点
已排序（移出堆）
堆排序分两步：1. 建堆 2. 不断取出堆顶最大值
步骤 0 / 0

高级排序算法 ($O(n \log n)$)

归并排序 (Merge Sort)

归并排序的核心思想是分治 (Divide and Conquer)。

想象你有一堆乱序的扑克牌：

分：把这堆牌一分为二，分给两个人。两个人再分，直到每个人手里只有一张牌（一张牌自然是有序的）。
治：两个人把手里的有序牌堆，一张张比对，合并成一个更大的有序牌堆。

那么说得好。我们该如何实现呢？

  1. 准备两个指针，分别指向两个有序数组的开头。
  2. 比较两个指针指向的数，谁小就取谁，放到结果数组里，然后指针后移。
  3. 就像拉链一样，把两个有序序列"拉"在一起。

归并排序非常稳健，不管数据多乱都是 $O(n \log n)$。而且它是稳定的（相等的元素顺序不会变）。缺点是需要额外的空间$O(n)$来存临时数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 合并两个有序子数组 arr[l..m] 和 arr[m+1..r]
void merge(int arr[], int l, int m, int r) {

    // 这边省略创建临时数组L,R，和赋值的代码

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        // 谁小取谁。注意 <= 保证了稳定性（左边的先取）
        if (L[i] <= R[j]) arr[k++] = L[i++]; 
        else arr[k++] = R[j++];
    }
    // 把剩下的元素接在后面
}
归并排序
左子数组 L
右子数组 R
正在合并
已合并完成
归并排序：先"分"成单个元素，再"治"（合并）成有序序列
步骤 0 / 0

快速排序 (Quick Sort)

快速排序也是分治，但它的策略更暴力。

首先挑选基准。这一步我们随便找个人来当基准(Pivot)。
随后你要求所有人站队，比基准小的站左边，比基准大的站右边。
最后你对左边的队伍和右边的队伍调用递归，重复上面的过程。

  1. 选定一个 pivot（比如最后一个元素）。
  2. 用一个指针 i 记录"小于区"的边界。
  3. 扫描数组，只要发现比 pivot 小的数，就把它换到 i 的位置，然后 i 前进。
  4. 最后把 pivot 放到 i+1 的位置，这样 pivot 左边全比它小，右边全比它大。

快速排序的平均速度最快，是很多标准库排序的首选。但如果运气不好（比如数组本来就有序，你还每次选第一个当基准），它会退化成 $O(n^2)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选最后一个当基准
    int i = (low - 1);     // 小于区的边界

    for (int j = low; j <= high - 1; j++) {
        // 如果当前数比基准小，就把它扔到小于区去
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    // 最后把基准放到中间
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}
快速排序
基准 (pivot)
指针 i（小于区边界）
指针 j（扫描中）
已归位
快速排序：选基准 → 分区（小的左边，大的右边）→ 递归
步骤 0 / 0

线性排序 (Linear Sorts)

前面讲的排序都是基于比较的（比大小）。数学上证明了，基于比较的排序最快也只能是 $O(n \log n)$。
那有没有更快的？有！如果我们不比大小，而是利用数字本身的特性，就能达到 $O(n)$。

计数排序 (Counting Sort)

假设你要给全校同学按年龄排序。年龄的范围很小（比如 0-100 岁）。这个时候使用计数排序就很不赖。

在这个情景内，计数排序的逻辑大概是：

  1. 准备 101 个桶（数组），标号 0 到 100。
  2. 遍历所有同学。假如遍历到一个 19 岁的同学，就在 19 号桶里放个豆子（计数 +1）。
  3. 最后，从 0 号桶开始，桶里有几个豆子，就直接在结果上写几个对应的年龄出来。

非常有意思的解决方案。

计数排序的速度极快 $O(n+k)$，其中 $k$ 是数据范围。而计数排序的问题在于几乎只能排整数，且范围不能太大，否则桶太多内存超级大爆。

计数排序
📥 原始数组
🪣 计数桶 (count[])
📤 输出数组
正在处理
计数桶
已输出
计数排序：统计每个值出现的次数，然后按顺序输出
步骤 0 / 0

基数排序 (Radix Sort)

那么如果要排很大的数字（比如手机号），或者字符串，计数排序的桶就太多了。这时候就可以使用基数排序。

  1. 先按个位数字，把数据分到 0-9 号桶里，然后按顺序倒出来。
  2. 再按十位数字，分桶，倒出来。
  3. ... 直到最高位。
  4. 随后你惊讶的发现，现在数组已经完全有序了（

这样做的道理在于因为每一次分桶收集，都是一次稳定的排序。当我们排高位时，由于稳定性，低位的相对顺序被保留了下来。

基数排序
🔢 按位分桶（0-9）
当前处理
当前位高亮
完成
基数排序：从低位到高位，依次按每一位进行稳定排序
步骤 0 / 0

总结与考试重点

算法 平均时间 空间 稳定性 一句话特点
冒泡 $O(n^2)$ $O(1)$ 稳 像气泡一样上浮，简单但慢
插入 $O(n^2)$ $O(1)$ 稳 像理扑克牌，基本有序时最快
选择 $O(n^2)$ $O(1)$ 不稳 每次挑最小的，交换次数最少
堆排 $O(n \log n)$ $O(1)$ 不稳 利用堆结构，空间最省的高级排序
归并 $O(n \log n)$ $O(n)$ 稳 分治合并，稳定但费空间
快排 $O(n \log n)$ $O(\log n)$ 不稳 选基准分区，平均最快
计数 $O(n+k)$ $O(k)$ 稳 不比大小，利用统计，范围要小

有关稳定性：记住"快选堆"（快排、选择、堆排）是不稳定的，其他的基本都稳定。
最坏情况：快排最坏是 $O(n^2)$，归并和堆排最坏依然是 $O(n \log n)$。
应用场景：

  • 数据量小且基本有序 -> 插入排序
  • 数据量大且要求稳定 -> 归并排序
  • 数据量大且内存紧张 -> 堆排序
  • 一般情况下的最快选择 -> 快速排序

排序算法可视化实验室

在这里你可以直观地对比不同排序算法的执行过程。

准备就绪 比较次数: 0 | 交换/赋值次数: 0
算法 算法/排序 算法/排序/冒泡排序 算法/排序/选择排序 算法/排序/插入排序 算法/排序/堆排序 算法/排序/归并排序 算法/排序/快速排序 算法/排序/计数排序 算法/排序/基数排序
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~