Java 经典排序算法六件套：从冒泡到堆排，一次彻底搞懂
面试官让你手写排序？稳住，看完这一篇就上岸了
引言
排序算法是程序员的基本功，也是面试的\”硬通货\”——大厂校招笔试几乎必考，现场手写快排、归并、堆排更是家常便饭。
网上讲排序的文章多如牛毛，但大多停留在\”翻译课本\”层面：列定义、贴代码、说复杂度，看完你还是不会用、不会选、不会变形。
这篇文章不一样。我用 6 个核心算法 × 5 个固定板块（核心思想 → 代码实现 → 关键细节 → 适用场景 → 面试变形）的统一结构，把每种排序讲透。每段代码都经过实测，每个细节都是面试高频坑，每个变形都是大厂真题改编。
读完这一篇，你能做到的：
- 6 种排序闭着眼睛都能手写
- 知道每种排序的\”最佳战场\”和\”绝对禁区\”
- 面对排序变形题（比如 TopK、第 k 大）有清晰的思路模板
1. 冒泡排序：最简单的排序，没有之一
面试官让手写排序？掏出冒泡，至少能及格
核心思想
- 从头到尾依次比较相邻两个元素
- 如果前面比后面大，就交换（大的往后\”冒\”）
- 每一趟结束后，最大的元素沉到了最后
- 重复以上过程，每趟少比较一个（最后已有序）
优化点：如果某趟一次都没交换，说明数组已经有序——立即终止，这就是最好情况 O(n) 的来源。
复杂度：最坏 O(n²) / 最好 O(n) / 平均 O(n²)
Java 实现
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n – 1; i++) {
boolean swapped = false;
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 = true;
}
}
if (!swapped) break;
}
}
}
三个关键细节
- 外层循环 i < n – 1，不是 i < n——n 个元素排好 n-1 个
- 内层循环 j < n – 1 – i，减 i 是关键（末尾已有序）
- swapped 标志必须有——O(n²) 变 O(n) 的唯一机会
适用场景
- 适用：数据量极小（< 100）/ 基本有序 / 教学演示
- 不适用：大数据量 / 生产环境
面试变形
- 鸡尾酒排序（双向冒泡）：从左到右冒大，从右到左冒小
- 奇偶排序：奇数位和偶数位分别比较，适合并行
- 冒泡第 k 大：只跑 k 趟冒泡
2. 选择排序：最简单粗暴的\”找最小\”
每一轮都挑最矮的站前面——像极了军训排队
核心思想
- 从位置 i 开始，扫描 i 到末尾所有元素
- 找到最小元素的下标 minIndex
- 把 arr[i] 和 arr[minIndex] 交换
- i++，重复直到末尾
每轮只交换一次（比冒泡交换次数少），但比较次数不变。
复杂度：最好/最坏/平均 O(n²)。原地排序，不稳定。
Java 实现
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n – 1; i++) {
int minIndex = i;
