五大经典排序算法全攻略：插入、希尔、冒泡、选择、堆排序
（2026年面试/刷题/教学最实用版，带原理、动画思路、代码、复杂度、优缺点对比）
这五大算法是排序家族的入门基石，几乎所有大厂算法面试/数据结构课程都会反复考查。它们都是比较排序，且原地排序（除了极少数变体），空间大多O(1)。
一、五大算法速览对比表（背这个就够了）
| 排序算法 | 时间复杂度（最好/平均/最坏） | 空间复杂度 | 稳定性 | 原地 | 适用场景 / 特点 | 面试常考点 |
|---|---|---|---|---|---|---|
| 冒泡 | O(n) / O(n²) / O(n²) | O(1) | 稳定 | 是 | 小数据、教学演示、几乎不用生产 | 简单但低效 |
| 选择 | O(n²) / O(n²) / O(n²) | O(1) | 不稳定 | 是 | 小数据、辅助内存极少时 | 交换次数最少（≈n次） |
| 插入 | O(n) / O(n²) / O(n²) | O(1) | 稳定 | 是 | 近乎有序数据、在线排序、小数组 | 实际比冒泡快2倍左右 |
| 希尔 | O(n log n) ~ O(n^{1.3}) / O(n²) | O(1) | 不稳定 | 是 | 中等规模数据、突破O(n²)的入门算法 | 增量序列选择、gap优化 |
| 堆 | O(n log n) / O(n log n) / O(n log n) | O(1) | 不稳定 | 是 | 大数据、优先队列实现、TopK问题 | 建堆O(n)、原地、不递归 |
稳定性：相同key的元素，排序前后相对位置不变 → 重要场景如多字段排序。
二、逐个拆解（原理 + 图解思路 + Python代码）
1. 冒泡排序（Bubble Sort）—— 最简单但最慢
原理：相邻比较 + 交换，不断把最大/最小“冒泡”到一端。
动画思路：像气泡上升，每轮把当前最大沉底。
def bubble_sort(arr):
n = len(arr)
for i in range(n): # 轮数
swapped = False
for j in range(0, n - i - 1): # 每轮少比一次
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped: # 优化：已有序早停
break
return arr优点：实现最简单、稳定
缺点：交换次数多（逆序时O(n²)次交换），实际最慢
2. 选择排序（Selection Sort）—— 交换次数最少
原理：每轮从未排序部分选出最小（或最大），放到已排序部分的末尾。
动画思路：像选国王，每轮找当前最小的“国王”放前面。
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i] # 只交换一次
return arr优点：交换次数固定≈n次（比冒泡/插入少得多）
缺点：不稳定（跨大距离交换导致）
3. 插入排序（Insertion Sort）—— 最实用的O(n²)
原理：构建有序序列，把新元素插入到合适位置（从后往前挪动）。
动画思路：像打扑克摸牌，摸一张插到正确位置。
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # 后移
j -= 1
arr[j + 1] = key # 插入
return arr优点：近乎有序时接近O(n)、稳定、原地
缺点：逆序时最坏O(n²)比较+移动
为什么面试常说“插入比冒泡更好”？
插入平均移动/比较次数 ≈ n²/4，冒泡 ≈ n²/2；插入对近序数据极友好。
4. 希尔排序（Shell Sort）—— 插入排序的加强版
原理：分组插入排序，先大步长（gap）分组排序，逐步缩小gap到1。
动画思路：先粗排（让数组“更接近有序”），再精排。
def shell_sort(arr):
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2 # 经典gap/2，也可用Hibbard序列等
return arr优点：突破O(n²)，实际性能很好（gap选择影响大）
缺点：不稳定、gap序列无理论最优
5. 堆排序（Heap Sort）—— 原地O(n log n)
原理：先建大顶堆（或小顶堆），然后反复把堆顶（最大）放到末尾，调整堆。
动画思路：先把数组“堆”起来（O(n)建堆！），然后像拔河一样拔最大值。
def heapify(arr, n, i): # 向下调整
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# 建堆（从最后一个非叶子节点开始）
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 排序
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
return arr优点：最坏/平均都是O(n log n)、原地、不递归
缺点：不稳定、实际常数较大（比快排慢）
三、总结一句话建议
- 小数据 / 近乎有序 / 需要稳定 → 插入排序（王者）
- 中等数据 / 想突破O(n²) → 希尔排序（性价比之王）
- 大数据 / 要保证O(n log n) → 堆排序（原地稳定选手）或快排（实际最快，但最坏O(n²)）
- 教学/面试手撕 → 插入 > 冒泡 > 选择 > 希尔 > 堆
你现在是在准备面试手撕代码，还是想深入某个算法的优化（如希尔gap序列、堆的建堆证明、插入的二分优化）？
或者想看这五个算法的动画演示链接 / 真实性能测试对比？告诉我，我继续给你针对性扩展！
