五大经典排序算法全攻略：插入、希尔、冒泡、选择、堆排序
这五个算法是学习排序算法时最常遇到的“入门+进阶”组合，它们在思想、复杂度、稳定性、适用场景上各有特点，非常适合对比学习。
下面按从简单到相对复杂的顺序详细讲解，并给出清晰对比表、核心思想、代码实现（Java）、关键性质和真实使用场景。
一、五大排序算法对比表（强烈建议背下来）
| 排序算法 | 时间复杂度（最好/平均/最坏） | 空间复杂度 | 稳定性 | 原地排序 | 思想关键词 | 最佳适用场景 |
|---|---|---|---|---|---|---|
| 插入排序 | O(n) / O(n²) / O(n²) | O(1) | 稳定 | 是 | 像打扑克牌插牌 | 小规模数据、近乎有序的数组 |
| 希尔排序 | O(n log 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 log n) / O(n log n) / O(n log n) | O(1) | 不稳定 | 是 | 构建大/小顶堆 + 堆顶交换 | 需要稳定 O(n log n) 且空间紧张的场景 |
二、逐个详细讲解
1. 插入排序（Insertion Sort）
核心思想：
把数组分为“已排序”和“未排序”两部分，每轮从未排序部分取一个元素，插入到已排序部分的正确位置（类似打扑克牌插牌）。
Java 实现（最清晰版本）
public void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i]; // 当前要插入的数
int j = i - 1;
// 将大于 key 的元素向后移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // 插入到正确位置
}
}稳定性：稳定（相同元素相对顺序不变）
优化点：可以用二分查找优化查找插入位置（→ 折半插入排序）
2. 希尔排序（Shell Sort）
核心思想：
插入排序的升级版，先进行大跨度分组插入排序，逐渐缩小分组间距（增量），最后变成增量为1的普通插入排序。
增量序列（常见几种）：
- 原始 Shell：n/2, n/4, …, 1
- Hibbard：2^k – 1
- Sedgewick：… 推荐使用较优序列
Java 实现（经典 /2 序列）
public void shellSort(int[] arr) {
int n = arr.length;
// 增量从大到小
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个分组做插入排序
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}特点：
- 打破了 O(n²) 的魔咒（平均远好于 O(n²)）
- 不稳定（跨组交换导致）
3. 冒泡排序（Bubble Sort）
核心思想：
相邻元素两两比较，如果顺序错误就交换，每轮把最大的元素“冒泡”到末尾。
Java 实现（带优化）
public void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
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;
}
}优化：加 swapped 标志位可提前结束
4. 选择排序（Selection Sort）
核心思想：
每轮从未排序部分选出最小（或最大）的元素，放到已排序部分的末尾。
Java 实现
public void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
// 在未排序部分找最小
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换到正确位置
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}特点：交换次数最少（最多 n-1 次）
5. 堆排序（Heap Sort）
核心思想：
利用二叉堆（通常是大顶堆）特性：
- 先把数组建成大顶堆
- 每次把堆顶（最大元素）放到数组末尾
- 调整剩余堆，重复直到排序完成
Java 实现（大顶堆）
public void heapSort(int[] arr) {
int n = arr.length;
// 建堆（从第一个非叶子节点开始）
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 依次取出堆顶放到末尾
for (int i = n - 1; i > 0; i--) {
// 交换堆顶和末尾
swap(arr, 0, i);
// 调整剩余堆
heapify(arr, i, 0);
}
}
// 堆调整（大顶堆）
private void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, n, largest); // 递归向下
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}三、总结与选择建议
快速记忆口诀：
- 小数据 / 近乎有序 → 插入排序
- 中等数据 + 想简单优化 → 希尔排序
- 教学演示 / 理解交换 → 冒泡
- 交换次数最少 → 选择排序
- 稳定 O(n log n) + 空间 O(1) → 堆排序
面试常问对比问题：
- 哪些是稳定的？（插入、冒泡）
- 哪些一定是 O(n²)？（冒泡、插入、选择）
- 为什么堆排序不稳定？
- 希尔排序为什么比插入快很多？
- 实际项目中你会用哪种排序？为什么？
如果你想看这五种算法的动画演示对比、稳定性动画、不同数据规模下的性能实测，或者需要其他语言的实现（Python、C++、Go等），可以告诉我，我继续补充。
