排序

2026-05-03

排序

核心定义

排序是把一组记录按关键字从无序变为有序的过程。排序题不只是”会排”，而是要判断 稳定性、时间复杂度、空间复杂度、关键字特征。

插入排序：将元素 逐个插入已排好的子序列，最好 $O(n)$ （已有序），平均/最坏 $O(n^2)$ ，稳定。

希尔排序：按 增量分组 进行插入排序，平均约 $O(n^{1.3})$ ，不稳定（跨组交换可能改变相对顺序）。

冒泡排序：相邻元素两两比较交换，最好 $O(n)$ （加标志位），最坏 $O(n^2)$ ，稳定。

快速排序：分治选基准（pivot），平均 $O(n \log n)$ ，最坏退化到 $O(n^2)$ （当序列 已有序或逆序 且选端点做 pivot），不稳定。

归并排序：分治合并，始终 $O(n \log n)$ ，稳定，但需要 额外数组（空间 $O(n)$ ）。

堆排序：利用堆结构选极值，始终 $O(n \log n)$ ，不稳定（堆调整可能改变相同关键字相对次序），原地排序空间 $O(1)$ 。建堆时间 $O(n)$ 。

基数排序：逐位分配收集，非比较排序，时间 $O(d \cdot (n+r))$ （ $d$ 为位数， $r$ 为基数），稳定，需要额外空间。

计数排序统计每个关键字出现的次数，时间 $O(n + k)$ （ $k$ 为关键字范围），稳定，非比较排序，需要 $O(k)$ 的辅助数组。

桶排序将元素分到有限数量的桶中，每个桶内部再用 插入排序 等排序，平均时间 $O(n)$ （当分布均匀时）。稳定性定义：若两个关键字相同的元素排序后 相对次序保持不变 则稳定，否则不稳定。比较排序的时间下界为 $\Omega(n \log n)$ ，非比较排序可以突破此下界。考研常考”在什么条件下选什么算法”。

关键细节 / 操作步骤

先判断题目要求的是 稳定性 还是速度还是空间。
若问稳定排序，优先考虑 插入排序、归并排序、冒泡排序。
若问平均快，优先考虑 快速排序（平均 $O(n \log n)$ ）或 堆排序。
若问非比较排序，考虑 基数排序、计数排序（适合关键字范围小的整数）。
若问最坏情况，注意快速排序可能退化到 $O(n^2)$ ——性能高度依赖 基准选择，优化方法有三数取中或随机选基准。
若问额外空间，归并排序需要 $O(n)$ ，快速排序递归栈 $O(\log n)$ ，堆排序 $O(1)$ 。
若问是否适合大规模外部排序，优先想 归并思想（数据分块排序后合并）。
若问关键字分布，考虑是否适合 桶排序、计数排序或基数排序。
若问排序过程中移动次数，注意 插入排序 和 冒泡排序 的行为差异。
内排序和外排序的区别在于 数据能否全部放入主存。
若问简单选择排序，每趟选 最小元素 放到最终位置，不稳定（如 {5,5,2}），时间始终 $O(n^2)$ ，比较次数与初始序列无关。
若问结果是否唯一，先看是否存在 相同关键字 和 算法是否稳定。
若问堆排序建堆过程，从 $\lfloor n/2 \rfloor$ 号结点开始向下调整，建堆时间 $O(n)$ 。
若问冒泡排序的优化，使用 flag 标记 记录一趟是否有交换，若无交换则已有序，最好时间降为 $O(n)$ 。
若问插入排序的最好情况，序列已有序时每次只需 比较一次 不移动，时间 $O(n)$ 。
若问快速排序的空间复杂度，平均 $O(\log n)$ （递归栈），最坏 $O(n)$ （退化成单链时栈深度为 $n$ ）。
若问归并排序的递归深度，共需 $\lceil \log_2 n \rceil$ 趟归并，每趟时间 $O(n)$ 。

⚠️ 易错辨析 快排平均快但最坏会退化；归并稳定但需要额外空间；堆排不稳定——真题常把这三点混在一起考。“稳定”不等于”更快”，稳定只说明 相同关键字的相对顺序不变。归并排序虽然稳定但不一定是原地排序，不要把”稳定”和”原地”划等号。快速排序的性能高度依赖基准选择，若 划分不均 则递归会退化。堆排不稳定的核心原因是 堆调整会改变相同关键字的相对次序。简单选择排序不稳定的原因是 交换可能跨越相等元素。反例：对基本有序的序列用快排（选第一个元素做 pivot），每次划分极不均匀，退化为 $O(n^2)$ 。

💡 技巧与口诀 口诀：插归冒稳定，快堆平均快，基数看关键字。适用场景：遇到”稳定性判断”题，先用口诀筛掉明显不稳定的算法（快排、堆排、希尔、简单选择）。若题目问复杂度，不要只写一个数字，要分别想 最好、平均、最坏。基数排序适合 有限位数关键字，核心是逐位分配而非比较。归并稳定的核心原因是 合并时可保持相等关键字的先后顺序。快速排序”平均快”的核心原因是 分治划分后子问题规模通常较均衡。

📝 真题闭环 题目：给定一组待排序关键字，要求排序算法既稳定又时间复杂度为 $O(n \log n)$ ，应选择哪种排序算法？若不允许额外空间呢？若关键字为 0~999 的整数且 $n$ 很大呢？

解题思路：审题抓”稳定”和 $O(n \log n)$ ，切入点是 归并排序；方法选择依据为稳定性与分治思想；计算关键点是归并天然稳定且始终 $O(n \log n)$ ；易错防范是不要选堆排序（不稳定）或快速排序（不稳定）。

答案：允许额外空间时选 归并排序；不允许额外空间时，不存在既稳定又原地的 $O(n \log n)$ 比较排序。若关键字为 0~999 的整数且 $n$ 很大，可选 基数排序 或 计数排序（非比较排序，可突破 $O(n \log n)$ 下界）。
// T=O(n log n) S=O(log n)
void quicksort(int a[], int l, int r) {
    if (l >= r) return;
    int i = l, j = r, pivot = a[l];
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;
        while (i < j && a[i] <= pivot) i++;
        if (i < j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
    }
    a[l] = a[i]; a[i] = pivot;
    quicksort(a, l, i - 1);
    quicksort(a, i + 1, r);
}

cd ..