常见的排序方法

部分 04 数据与系统章节 简单题 04/04创建 2024-10-16更新 2026-10-20阅读 –

常见的排序方法

以下五种排序算法均以初始数组 5 1 4 2 8 为例独立演示，各自推导排序过程与内存状态变化。

冒泡排序

遍历相邻两项并在逆序时交换，每轮将当前未排序区间的最大值推至最右端。若整轮未发生任何交换，说明数组已有序，可提前终止。

public void bubble(int[] a) {
    for (int end = a.length - 1; end > 0; end--) {
        boolean swapped = false;
        for (int i = 0; i < end; i++) {
            if (a[i] > a[i + 1]) {
                int temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) return;
    }
}

01 · 初始状态

初始数组为 5 1 4 2 8。从最左侧的相邻两项开始比较。

02 · 比较 [5, 1]

5 大于 1，发生交换，数组变为 1 5 4 2 8。

03 · 比较 [5, 4]

指针后移，5 大于 4，继续交换，数组变为 1 4 5 2 8。

04 · 比较 [5, 2]

5 大于 2，再次交换，数组变为 1 4 2 5 8。

05 · 第一轮结束（8 归位）

5 小于 8，不发生交换。本轮结束，最大元素 8 已沉底至最右侧，后续轮次不再遍历末位。此时左侧 1 4 2 5 仍处于无序状态。

06 · 第二轮遍历（5 归位）

重新从左侧遍历：1 与 4 无需交换；4 大于 2 发生交换；4 小于 5 不交换。次大元素 5 归位，数组变为 1 2 4 5 8。

07 · 提前终止

进入第三轮扫描，所有相邻元素均满足升序，未触发任何交换。布尔标志 swapped 保持为 false，算法提前退出。只在严格大于时交换，相同元素相对次序不变，属于稳定排序。

图 · 04.01.04STEP 00 / 00

选择排序

将数组划分为已排序区与未排序区。每轮扫描未排序区间找到最小值，将其与该区间首项交换。无论初始数据是否有序，比较次数均为固定的 $\frac{n(n-1)}{2}$ 次。

public void selection(int[] a) {
    for (int start = 0; start < a.length; start++) {
        int min = start;
        for (int i = start + 1; i < a.length; i++) {
            if (a[i] < a[min]) min = i;
        }
        int temp = a[start];
        a[start] = a[min];
        a[min] = temp;
    }
}

01 · 初始状态

初始数组 5 1 4 2 8。首轮扫描覆盖整个数组，暂定下标 0（数值 5）为最小值。

02 · 扫描并锁定最小值

向后遍历扫描到数值 1，小于当前最小值 5，更新最小值下标为 1。继续扫描后续元素（4、2、8），未发现更小值。

03 · 最小值交换首位

未排序区遍历完毕，将最小值 1 与区间首项 5 交换，1 归位至下标 0。剩余未排序区间为 5 4 2 8。

04 · 第二轮扫描（2 归位）

在未排序区间 5 4 2 8 中检索到最小值为 2，与该区间首位 5 交换。数组变为 1 2 4 5 8。已排序区间扩大至前两位。

05 · 最小值已在首位

扫描区间 4 5 8，当前最小值即为首位的 4。下标相同，虽执行赋值交换逻辑但数组实际无变化。已排序区间继续扩大。

06 · 遍历完成与稳定性缺陷

最后两位 5 与 8 均已在正确位置。由于每次交换是跨越多个元素的长距离操作，若存在相等元素（例如 [2a, 2b, 1]），首个 2a 会与 1 发生跨步交换导致与 2b 倒序，因此选择排序不稳定。

图 · 04.01.04STEP 00 / 00

插入排序

维护左侧已排序区间，逐个从未排序区间取出元素作为 key，在已排序区间中从后向前扫描，将大于 key 的元素依次后移，最后将 key 插入空位。

public void insertion(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

01 · 初始状态

初始数组 5 1 4 2 8。首个元素 5 天然构成初始已排序区间，待排序元素为右侧的 1 4 2 8。

02 · 插入元素 1

取 key = 1。已排序区间中的 5 大于 1，向后平移一格腾出位置，将 1 填入起始位置。已排序区间扩展为 1 5。

03 · 插入元素 4

取 key = 4。5 大于 4，5 后移一格；1 小于 4，终止扫描。将 4 插入 1 与 5 之间，已排序区间变为 1 4 5。

04 · 插入元素 2

取 key = 2。5 和 4 均大于 2，依次向右平移一格；1 小于 2，扫描停止。将 2 插入至 1 之后，已排序区间变为 1 2 4 5。

05 · 插入元素 8（无需移动）

取 key = 8。已排序区末位元素 5 小于 8，while 条件直接不成立，元素保持原位。只有手里的数值严格大于待插入项时才后移，相同元素保持原有次序，属于稳定排序。

图 · 04.01.04STEP 00 / 00

快速排序

基于分治思想，选定基准值（Pivot）将当前区间划分为“小于等于基准”与“大于基准”两部分。将基准归位后，再对左右两子区间递归执行同样的分区操作。

public void quickSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}

private int partition(int[] a, int lo, int hi) {
    int pivot = a[hi];
    int i = lo;
    for (int j = lo; j < hi; j++) {
        if (a[j] <= pivot) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
        }
    }
    int temp = a[i];
    a[i] = a[hi];
    a[hi] = temp;
    return i;
}

01 · 选取基准

初始数组 5 1 4 2 8。本例选取中位下标 2 对应的数值 4 作为基准值。

02 · 基准暂存末位

为便于单向指针扫描分区，将基准 4 与末尾元素 8 交换，数组变为 5 1 8 2 4。此时基准暂存于末尾 a[hi]。

03 · 元素 1 划入左区间

扫描指针遍历：5 大于基准 4，留在右侧；遍历至 1，不大于基准，与分界指针 i 交换，数组变为 1 5 8 2 4，i 右移一格。

04 · 元素 2 划入左区间

8 大于基准，跳过；遍历至 2，不大于基准，与当前分界点 i 处的 5 交换，数组变为 1 2 8 5 4，分界指针继续右移。

05 · 基准归位

单向扫描结束，将末位的基准 4 与分界指针 i 所在位置的 8 交换，数组变为 1 2 4 5 8。基准 4 最终归位，左侧元素均小于等于 4，右侧均大于等于 4。

06 · 递归子区间与最坏退化

对左子区间 [1, 2] 与右子区间 [5, 8] 递归执行分区。两区间已满足单调，递归边界触发返回。若基准每次都选到极值，划分将极度不平衡，时间复杂度退化至 $O(n^2)$ 。

图 · 04.01.04STEP 00 / 00

堆排序

利用数组模拟完全二叉树（节点 $i$ 的左孩子为 $2i+1$ ，右孩子为 $2i+2$ ）。先自底向上建大顶堆，随后反复将堆顶最大值交换至末位，并对剩余区间缩小规模重新下沉调整。

public void heapSort(int[] a) {
    for (int i = a.length / 2 - 1; i >= 0; i--) heapify(a, a.length, i);
    for (int end = a.length - 1; end > 0; end--) {
        int temp = a[0];
        a[0] = a[end];
        a[end] = temp;
        heapify(a, end, 0);
    }
}

private void heapify(int[] a, int size, int root) {
    int largest = root;
    int left = root * 2 + 1;
    int right = root * 2 + 2;
    if (left < size && a[left] > a[largest]) largest = left;
    if (right < size && a[right] > a[largest]) largest = right;
    if (largest == root) return;
    int temp = a[root];
    a[root] = a[largest];
    a[largest] = temp;
    heapify(a, size, largest);
}

01 · 检查末位非叶节点

初始数组 5 1 4 2 8。最后一个非叶节点位于下标 1（值为 1），其左右子节点分别为 2 与 8，右孩子 8 为最大值。

02 · 局部下沉调整

节点 1 与较大的子节点 8 交换，数组变为 5 8 4 2 1，局部子树恢复大顶堆性质。

03 · 根节点下沉，完成大顶堆

继续向前调整根节点 0（值为 5）。其左孩子 8 大于根节点，两者交换。大顶堆构建完成：8 5 4 2 1。此时整树堆顶已为最大值。

04 · 最大值交换至末尾

将堆顶 8 与当前堆末尾元素 1 交换，最大值 8 完成最终定位。有效堆大小缩减为 4，剩余待调整区间为 1 5 4 2。

05 · 堆顶下沉恢复大顶堆

对根节点 1 执行 heapify，1 与较大子节点 5 交换，5 上浮至堆顶，有效堆重构为 5 2 4 1（末位 8 不参与）。

06 · 次大值 5 归位

将当前堆顶 5 与有效堆末位 1 交换，5 锁定在倒数第二位。对剩余 3 个元素重新下沉，4 上浮至新堆顶：4 2 1 5 8。

07 · 元素 4 归位

将堆顶 4 交换至其最终位置，剩余两个元素下沉调整后，2 成为堆顶：2 1 4 5 8。

08 · 最终两项交换

堆顶 2 与末项 1 执行最后一次交换，排序全部完成：1 2 4 5 8。建堆耗时为 $O(n)$ ，后续 $n-1$ 次堆调整耗时为 $O(n \log n)$ 。父子跨层级交换导致其属于不稳定排序。

图 · 04.01.04STEP 00 / 00

选型与工程权衡

算法	平均时间	最坏时间	最好时间	空间复杂度	稳定性	核心特征与场景
插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定	数据量小（如 $n \le 16$ ）或几乎有序时开销极低。许多混合排序（如 Timsort、Dual-Pivot Quicksort）在子区间缩小时均以此收尾。
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定	借助提前终止标志可在近有序数据下达到 $O(n)$ 比较，但每次逆序均发生相邻元素写入，写操作开销通常高于插入排序。主要用于教学。
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	交换次数恒定为 $O(n)$ 。无论数据分布如何都必须完成全量比较，且跨步交换破坏稳定性，工程中极少单独使用。
快速排序	$O(n \log n)$	$O(n^2)$	$O(n \log n)$	$O(\log n)$	不稳定	缓存命中率高、常数因子极小，平均吞吐量在原地排序中最具优势；最坏情况依赖三数取中或随机基准规避。
堆排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	不稳定	时间复杂度绝对稳定且严格 $O(1)$ 辅助空间。但树状跳跃访问对 CPU Cache 不友好，平均耗时通常慢于快速排序。适合对最坏停顿敏感且内存受限的系统。

决策依据：

数据规模极小或近乎有序：首选插入排序。当逆序对极少时，其内层循环能快速跳出，实际执行开销往往优于具有函数调用开销的高阶排序。
多字段复合排序（需严格保序）：在无额外内存分配的前提下，选用插入排序；数据量较大时选用具有稳定性的归并排序（Merge Sort）。
追求通用吞吐量：首选优化后的快速排序。通过三数取中避免极值分区，并在小区间切入插入排序以降低递归开销。
硬性拒绝 $O(n^2)$ 最坏波动且禁止额外内存：选用堆排序，以固定的 $O(n \log n)$ 上界保障系统下限。

评论WALINE

常见的排序方法 ​

冒泡排序 ​

选择排序 ​

插入排序 ​

快速排序 ​

堆排序 ​

选型与工程权衡 ​

常见的排序方法

冒泡排序

选择排序

插入排序

快速排序

堆排序

选型与工程权衡