排序
2026/4/10大约 15 分钟常用算法题排序
排序
📌 排序算法整体分类
排序算法分为两大类，核心区别在于是否依赖元素间的比较：
📊 核心性能指标对照表
面试必背，重点关注时间复杂度、空间复杂度、稳定性三个维度：
| 算法名称 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 | 考察频率 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | ✅ 稳定 | ⭐ |
| 简单选择排序 | O(n²) | O(n²) | O(n²) | O(1) | ❌ 不稳定 | ⭐ |
| 插入排序 | O(n²) | O(n) | O(n²) | O(1) | ✅ 稳定 | ⭐⭐ |
| 希尔排序 | O(n^1.3) | O(n) | O(n²) | O(1) | ❌ 不稳定 | ⭐ |
| 快速排序 | O(nlogn) | O(nlogn) | O(n²) | O(logn) | ❌ 不稳定 | ⭐⭐⭐⭐⭐ |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | ✅ 稳定 | ⭐⭐⭐⭐ |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | ❌ 不稳定 | ⭐⭐⭐⭐ |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | ✅ 稳定 | ⭐⭐ |
| 桶排序 | O(n+k) | O(n+k) | O(n²) | O(n+k) | ✅ 稳定 | ⭐⭐ |
| 基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | ✅ 稳定 | ⭐⭐ |
注：k 为数据范围 / 桶数量；稳定性指相等元素排序后相对顺序不变，业务排序场景非常重要。
⚡ 大厂高频核心算法拆解
1. 快速排序（考察频率最高）
- 核心思想：分治思想。选定一个基准值，通过一轮分区操作将小于基准的元素放左侧、大于基准的放右侧，再递归排序左右两个子区间。
- 面试核心考点：基准值选择、分区实现、退化场景优化。
2. 归并排序
- 核心思想：分治思想。将数组对半拆分至单个元素，再两两合并为有序数组，自底向上完成整体排序。
- 核心优势：唯一稳定的 O (nlogn) 排序，最坏情况性能不退化；天然适配外排序、链表排序场景。
- 核心缺点：需要 O (n) 额外辅助空间，不适合极致内存受限场景。
3. 堆排序
- 核心思想：利用大顶堆 / 小顶堆的结构特性，每次取出堆顶极值，调整堆结构后重复操作，最终得到有序序列。
- 核心优势：原地排序仅需 O (1) 额外空间，是海量数据 TopK 问题的最优解，无需加载全量数据。
- 核心缺点：不稳定，对 CPU 缓存不友好，随机数据下实际运行性能略逊于快排。
💻 核心亮点代码实现（面试手写标准版）
以下 3 种实现均带工业级优化点，手写即可体现工程素养 ✨
1. 优化版快速排序（三数取中 + 小数组插入排序）
对齐 JDK 底层快排优化思路，彻底解决基础快排的核心缺陷
public class QuickSortOptimized {
// JDK同款阈值：小数组切换插入排序，抵消递归开销
private static final int INSERT_THRESHOLD = 17;
public void quickSort(int[] arr, int left, int right) {
// 技术亮点1：小数组降级插入排序，小数据量性能比纯快排高30%+
if (right - left <= INSERT_THRESHOLD) {
insertionSortRange(arr, left, right);
return;
}
// 技术亮点2：三数取中选基准，避免有序数组下O(n²)时间复杂度退化
int pivotIndex = medianThree(arr, left, right);
swap(arr, left, pivotIndex);
int pivot = arr[left];
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) j--;
arr[i] = arr[j];
while (i < j && arr[i] <= pivot) i++;
arr[j] = arr[i];
}
arr[i] = pivot;
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
// 三数取中：返回左、中、右三个位置中值的下标
private int medianThree(int[] arr, int left, int right) {
int mid = left + ((right - left) >> 1); // 位运算防溢出+提速
if (arr[left] > arr[mid]) swap(arr, left, mid);
if (arr[left] > arr[right]) swap(arr, left, right);
if (arr[mid] > arr[right]) swap(arr, mid, right);
return mid;
}
// 指定区间内的插入排序
private void insertionSortRange(int[] arr, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= left && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}2. 归并排序（带有序性预判优化）
稳定排序标杆实现，是外排序、链表排序的核心基础
public class MergeSort {
public void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
int mid = left + ((right - left) >> 1);
// 分治：递归拆分数组
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 技术亮点：左右区间已有序时直接跳过合并，最佳场景复杂度降至O(n)
if (arr[mid] <= arr[mid + 1]) return;
// 合并两个有序区间
merge(arr, left, mid, right);
}
private void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
// 优先取左区间元素，严格保证排序稳定性
temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
// 批量拷贝回原数组，比循环赋值性能更优
System.arraycopy(temp, 0, arr, left, temp.length);
}
}3. 手写小顶堆实现 TopK（面试高频应用题）
海量数据求 TopN 的标准工业级方案
public class TopKHeap {
// 技术亮点：空间复杂度仅O(k)，支持TB级数据流式处理，无需全量加载
public int[] findTopK(int[] arr, int k) {
if (k <= 0 || arr.length < k) return new int[0];
// 前k个元素构建初始小顶堆
int[] heap = new int[k];
System.arraycopy(arr, 0, heap, 0, k);
buildMinHeap(heap);
// 遍历剩余元素：比堆顶大则替换，再下沉调整堆结构
for (int i = k; i < arr.length; i++) {
if (arr[i] > heap[0]) {
heap[0] = arr[i];
siftDown(heap, 0, k);
}
}
return heap;
}
// 自底向上构建小顶堆
private void buildMinHeap(int[] heap) {
int len = heap.length;
// 从最后一个非叶子节点开始向前调整
for (int i = (len - 1) / 2; i >= 0; i--) {
siftDown(heap, i, len);
}
}
// 堆元素下沉调整
private void siftDown(int[] heap, int index, int len) {
while (true) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int smallest = index;
if (left < len && heap[left] < heap[smallest]) smallest = left;
if (right < len && heap[right] < heap[smallest]) smallest = right;
if (smallest == index) break;
swap(heap, index, smallest);
index = smallest;
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}🏗️ Java 原生排序工程实现（进阶区分考点）
这是区分新手和熟手的关键问题，JDK 排序做了大量工业级优化：
- 基本数据类型排序（
Arrays.sort(int[])）：底层采用双轴快速排序（DualPivotQuicksort），基本类型无需保证稳定性，优先追求极致性能。 - 对象类型排序（
Arrays.sort(Object[])）：底层采用TimSort（归并排序 + 二分插入排序的优化版），严格保证稳定性，对业务中常见的部分有序数据性能极佳。 Collections.sort()：本质是将集合转为数组，调用Arrays.sort实现，排序逻辑与上述规则完全一致。
🧩 排序场景核心技术难点与解决方案
| 难点场景 | 问题本质 | 解决方案 | 落地适用场景 |
|---|---|---|---|
| 有序 / 近乎有序数组下，快排时间复杂度退化到 O (n²) | 基准值选到区间极值，分区极度不均匀，递归深度退化为 O (n) | 1. 三数取中 / 随机选择基准值，破坏数据有序性 2. 双轴快排拆分为 3 个区间，减少重复比较 3. 递归过深时自动切换堆排序（Introsort 思路） | 通用业务排序、JDK 原生排序底层实现 |
| 百亿级海量数据排序，单机内存无法容纳全量数据 | 内存容量物理限制，无法执行全量内排序 | 外排序方案：分块 + 多路归并 1. 数据切分为内存可容纳的小块 2. 每块内排序后写入磁盘 3. 多路归并所有有序块得到最终结果 | 大数据离线数仓、大日志文件排序、全量数据归档 |
| 业务需要稳定排序，同时要求高性能 | 快排 / 堆排序不稳定，插入排序性能不足，归并排序空间开销大 | 采用 TimSort 算法（归并 + 二分插入） 识别数据中连续有序段，合并时跳过有序部分，最坏 O (nlogn)，最好 O (n) | Java 对象排序、Python sorted 函数、MySQL order by 优化 |
| 数据取值范围小、重复值极多（如年龄、分数），通用排序效率低 | 大量重复元素导致比较操作冗余，分区效率低下 | 1. 计数排序：数据范围小时按计数直接回填 2. 三路快排：将相等元素单独放中间区间，避免重复排序 | 用户标签排序、考试分数排名、枚举值排序 |
| 小数据量排序（n<20），高级排序性能反而不如简单排序 | 快排 / 归并的递归、分区、函数调用开销，超过排序本身的收益 | 小数组统一降级为插入排序 插入排序常数项极低，n<20 时实际运行速度远超 O (nlogn) 算法 | 所有高级排序算法的底层优化、JDK 排序默认阈值 |
| 多字段组合排序，二次排序会破坏前序结果 | 不稳定排序打乱上一轮的顺序，导致多字段优先级失效 | 1. 使用稳定排序算法，按优先级从低到高依次排序 2. 自定义比较器，一次排序完成多字段逻辑判断 | 电商商品多维排序、报表多维度排序、数据库多字段 order by |
❓ 面试高频追问速答
1. 排序稳定性有什么实际业务意义？
答：业务中常有多字段排序需求，比如先按销量排序、再按价格排序。稳定排序可以保证价格相等的商品，依然保持之前的销量顺序，不需要重复计算排序权重。
2. 10 亿个整数找 Top100，用什么方案？
答：用大小为 100 的小顶堆。遍历所有数，比堆顶大就入堆并调整堆结构，时间复杂度 O (nlog100)，内存只需要存 100 个数，支持流式读取，不需要加载全量数据。
3. 快排最坏情况怎么避免？
答：最常用的是三数取中法选基准（取区间首尾中间三个数的中位数），或者随机选择基准值，破坏数组的有序性，从概率上避免最坏 O (n²) 的退化。
真实面试模拟
真实面试模拟
面试官 👨💻：
同学你好，那咱们先热个身，聊聊 排序算法。不要求你把所有算法都背一遍，你先说说，常见排序算法的时间/空间复杂度、稳定性，以及你怎么选型？
我 😊：
好的面试官，这题我习惯用一张表来记，非常直观：
| 算法 | 平均时间 | 最坏时间 | 最好时间 | 空间 | 稳定性 | 一句话选型建议 |
|---|---|---|---|---|---|---|
| 快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n) | ❌ 不稳定 | 🔥 通用最快，实际开发的老大 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ 稳定 | 🧠 需要稳定或外部排序时首选 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ 不稳定 | 📦 内存极其苛刻时的救星 |
| 插入排序 | O(n²) | O(n²) | O(n) | O(1) | ✅ 稳定 | 🐌 数据量小或基本有序时无敌 |
| 冒泡/选择 | O(n²) | O(n²) | O(n²) / O(n) | O(1) | 不稳/稳 | 😅 面试必考，工作不用 |
选型上我遵循一个原则：数据量小用插排，大数据快排为主，需稳定切归并，内存紧用堆排。就像下边这个简单图示，快排就是分治递归，思路很清晰：
[5, 1, 3, 7, 2]
pivot=3
↙ ↘
[1,2] 3 [5,7]
↙ ↘ ↙ ↘
1 2 5 7面试官 💬：
基础挺扎实。那现在请你 手写一个快速排序，主要写 partition 核心部分和递归框架。不用 IDE，用笔在纸上写的感觉来。
我 ✍️：
好，我先写最经典的版本，拿最左边元素做基准。
// 核心：分区函数，返回基准最终位置
int partition(int[] arr, int low, int high) {
int pivot = arr[low];
int left = low;
int right = high;
while (left < right) {
// 从右向左找第一个小于 pivot 的
while (left < right && arr[right] >= pivot) right--;
// 从左向右找第一个大于 pivot 的
while (left < right && arr[left] <= pivot) left++;
if (left < right) {
swap(arr, left, right);
}
}
// 基准归位
swap(arr, low, left);
return left;
}
// 递归框架
void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}面试官 🤔：
这段代码在极端情况下，比如数组已经有序，性能会怎么样？如果让你 优化到能上生产环境，你会加哪些手段？
我 👍：
这正是我想说的亮点。上面代码在有序数组下会退化成 O(n²)，栈深度 O(n)。生产环境我至少加 三把锁：
- 三数取中选 pivot：防最坏情况退化。
- 小数组切换插入排序：长度小于 47 时，插排常数时间更优。
- 尾递归优化/优先处理短分段：把递归深度压到 O(log n)。
我直接写优化版代码：
void quickSortOpt(int[] arr, int low, int high) {
int INSERT_THRESHOLD = 47;
while (low < high) {
// 优化1：小数组直接插排
if (high - low < INSERT_THRESHOLD) {
insertionSort(arr, low, high);
return;
}
// 优化2：三数取中，并将中值换到 low 位置
int median = medianOfThree(arr, low, (low + high) >>> 1, high);
swap(arr, low, median);
int pi = partition(arr, low, high);
// 优化3：先递归较短部分，另一部分用迭代（尾递归优化）
if (pi - low < high - pi) {
quickSortOpt(arr, low, pi - 1);
low = pi + 1;
} else {
quickSortOpt(arr, pi + 1, high);
high = pi - 1;
}
}
}
// 三数取中示例
int medianOfThree(int[] arr, int a, int b, int c) {
if (arr[a] > arr[b]) { int t=a; a=b; b=t; }
if (arr[a] > arr[c]) { int t=a; a=c; c=t; }
if (arr[b] > arr[c]) { int t=b; b=c; c=t; }
return b; // 返回中间值的索引
}这些优化其实就是 JDK DualPivotQuicksort 的思想前置，实际 JDK 用了双轴，更复杂，但优化方向一致。
面试官 🧐：
这个优化很好。那我再问你一个实际场景： Java 里 Arrays.sort() 对 int[] 和 Object[] 用了不同的排序算法，你知道原因吗？
我 💡：
知道，这恰好考了 稳定性 的工程意义。
- 对基本类型 (int[])，JDK 用的是 双轴快排，因为它不关心稳定性，追求速度最快、内存开销小。两个 3 谁先谁后无所谓。
- 对对象数组 (Object[])，底层用的是 TimSort（归并排序 + 二分插入的混合算法），因为对象排序可能需要多级排序，比如“先按年龄排，再按姓名排”，这种场景必须保证前一次排序的相对顺序不被破坏，所以需要 稳定排序。
这是非常精妙的工程权衡 😄。
面试官 🌊：
假如现在有 10G 的日志文件，只有 512M 内存，要对里面每行数据排序，你怎么做？
我 📂：
这就得用 外部排序（多路归并）。
- 切分：把 10G 文件切成比如 20 个 500M 的小文件，每个文件读入内存用快排或堆排排序后写回磁盘。
- 归并：打开所有小文件，用 堆（PriorityQueue） 维护每个文件当前读取的最小值，每次弹出堆顶写入最终文件，再从对应文件补充下一行。
这种方式内存可控，完美解决海量数据排序，也是 MapReduce 里 Shuffle 排序的基础思路。
面试官 🎯：
最后一个问题，如果待排数组有大量重复元素，比如 [2,2,2,1,1,3,3,3]，你前面的快排会怎么表现？有没有更优解？
我 🎯：
大量重复元素下，普通二路快排仍会把等于 pivot 的元素分到一边，导致大量无效交换和递归。最优解是 三路快排，把数组分成 <、=、> 三段，等值部分直接跳过。核心代码极简：
void threeWayQuickSort(int[] arr, int low, int high) {
if (low >= high) return;
int lt = low, i = low + 1, gt = high;
int v = arr[low];
while (i <= gt) {
if (arr[i] < v) swap(arr, lt++, i++);
else if (arr[i] > v) swap(arr, i, gt--);
else i++;
}
// 中间 [lt, gt] 全部等于 v，无需再排
threeWayQuickSort(arr, low, lt - 1);
threeWayQuickSort(arr, gt + 1, high);
}这个在处理包含大量相同元素的场景（比如按状态码排序）下，效率远超普通快排。
面试官 😊：
可以，从原理到优化，再到工程实际和极端场景，讲得很透。排序这部分我没问题了，咱们接着聊别的……