排序算法 (Sorting Algorithms)

为什么排序很重要

排序是高效数据处理的基石——它使二分查找、去重以及复杂的数据分析成为可能：

• 数据库查询：ORDER BY 背后运行着高度优化的排序引擎。
• 搜索优化：几乎所有的对数级查找算法都以前提有序为基础。
• 数据分析：寻找中位数、百分位数或识别离群点。
• 算法前置：许多高级算法（如贪心、双指针）的第一步通常是排序。

实际影响：对 100 万个整数进行排序：

• 冒泡排序：约需 1 小时（$O(n^2)$）。
• 快速排序：仅需约 50 毫秒（$O(n \log n)$） —— 速度提升 7 万倍。

---

核心概念

基于比较的排序

这类算法通过比较元素大小来决定顺序。数学证明其时间复杂度下界为 $O(n \log n)$。

• 归并排序 (Merge Sort)：稳定，非原地（需要额外空间）。
• 快速排序 (QuickSort)：不稳定，原地（生产环境首选）。
• 堆排序 (Heap Sort)：不稳定，原地，保证最差 $O(n \log n)$。

非比较类排序

通过利用数据的特定属性（如整数范围）突破 $O(n \log n)$ 的限制，达到 $O(n)$。

算法	时间复杂度	稳定性	限制条件
计数排序	O(n + k)	稳定	整数范围 k 较小
基数排序	O(d * n)	稳定	适用于整数或定长字符串
桶排序	O(n + k)	稳定	数据分布较均匀

排序的稳定性 (Stability)

稳定排序能保证相等元素的相对顺序在排序前后不发生改变。

• 为什么重要：当你需要先按“部门”排序，再在部门内部按“工资”排序时，只有稳定排序能保留之前的部门层级结构。

---

深入理解

1. 快速排序 (QuickSort)

核心逻辑：分治法。选取一个“基准值” (Pivot)，将数组划分为比它小和比它大的两部分，递归执行。

• 优化：使用三数取中法或随机选取基准值，以避免在近乎有序的数组上退化为 $O(n^2)$。

2. Java 内部排序算法

• 原生类型 (int[] 等)：使用 双基准快速排序 (Dual-Pivot Quicksort)。两个基准值将数组三分，缓存局部性更好，速度极快。
• 对象类型 (List<T> 等)：使用 TimSort。这是一种归并排序与插入排序的混合体，针对真实世界中“局部有序”的数据进行了极致优化，且是稳定排序。

---

面试高频题

Q1: 合并两个有序数组 (简单)

思路：逆向双指针。从两个数组的末尾（最大值位置）开始向前填充，避免了移动元素产生的 $O(n)$ 开销。

Q2: 最小 K 个数 (中等)

思路：

1. 排序法：$O(n \log n)$。
2. 堆法：$O(n \log k)$。
3. 快速选择 (QuickSelect)：平均 $O(n)$，这是面试中的最优解法。

Q3: 颜色分类 (中等)

思路：典型的荷兰国旗问题。利用三指针（左、中、右）一次遍历完成 0, 1, 2 的归位。

---

延伸阅读

• 外部排序：了解当内存装不下海量数据时，如何利用磁盘进行归并排序。
• 二分查找：学习排序完成后的第一步操作。
• 分治思想：深度掌握递归与任务拆分的精髓。
• LeetCode：排序标签题目