排序算法
本章目标：全面掌握比较类和非比较类排序算法，理解各算法的适用场景。
你将学到
- 排序的稳定性、原地性
- O(n²) 三兄弟：冒泡、选择、插入
- O(n log n) 三大将：归并、快排、堆排
- 非比较排序：计数、基数、桶排
- 各排序算法的对比与选择
1. 概念
排序是计算机科学中最基本也最重要的操作之一。理解排序算法不仅是面试基础，更能帮助理解分治、递归、堆等重要概念。
稳定性：相等元素排序后是否保持原来相对顺序。稳定排序在多关键字排序中有用（如先按年龄排，再按姓名稳定排，同龄人保持年龄排序的顺序）。
原地排序：是否只需 O(1) 额外空间。
排序算法对比
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定 | 原地 |
|---|---|---|---|---|---|
| 冒泡 | O(n²) | O(n²) | O(1) | 是 | 是 |
| 选择 | O(n²) | O(n²) | O(1) | 否 | 是 |
| 插入 | O(n²) | O(n²) | O(1) | 是 | 是 |
| 归并 | O(n log n) | O(n log n) | O(n) | 是 | 否 |
| 快排 | O(n log n) | O(n²) | O(log n) | 否 | 是 |
| 堆排 | O(n log n) | O(n log n) | O(1) | 否 | 是 |
| 计数 | O(n+k) | O(n+k) | O(k) | 是 | 否 |
| 基数 | O(d·n) | O(d·n) | O(n+d) | 是 | 否 |
| 桶排 | O(n+k) | O(n²) | O(n+k) | 是 | 否 |
2. 核心实现
冒泡排序
python
def bubble_sort(arr):
"""稳定，O(n²)，适合小规模或近乎有序数据"""
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped: # 优化：无交换说明已有序
break
return arr插入排序
python
def insertion_sort(arr):
"""稳定，O(n²)，小数据量或近乎有序时优于快排"""
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归并排序
python
def merge_sort(arr):
"""稳定，O(n log n)，需要 O(n) 额外空间"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return result快速排序
python
import random
def quick_sort(arr, lo, hi):
"""不稳定，平均 O(n log n)，原地"""
if lo >= hi:
return
pivot_idx = random.randint(lo, hi)
arr[lo], arr[pivot_idx] = arr[pivot_idx], arr[lo]
pivot = arr[lo]
i, j = lo, hi
while i < j:
while i < j and arr[j] >= pivot:
j -= 1
arr[i] = arr[j]
while i < j and arr[i] <= pivot:
i += 1
arr[j] = arr[i]
arr[i] = pivot
quick_sort(arr, lo, i - 1)
quick_sort(arr, i + 1, hi)堆排序
python
def heap_sort(arr):
"""不稳定，O(n log n)，原地"""
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)
def heapify(arr, n, i):
largest = i
left, right = 2 * i + 1, 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)计数排序
python
def counting_sort(arr, max_val):
"""稳定，O(n+k)，适合值域小的非负整数"""
count = [0] * (max_val + 1)
for num in arr:
count[num] += 1
result = []
for num in range(max_val + 1):
result.extend([num] * count[num])
return result3. 实际应用选择
- 小数据量（n < 50）：插入排序（TimSort 内部也用它）
- 通用排序：快排（Python/Java 默认对基本类型用快排变体）
- 需要稳定排序：归并排序（TimSort 是归并+插入的混合）
- 值域小：计数排序
- 大数据外部排序：归并排序（可分块读取）
Python 的 sort() 使用 TimSort（归并+插入），最坏 O(n log n)，在部分有序数据上接近 O(n)。
4. 易错点
- ⚠️ 快排选择第一个元素做 pivot 在已排序数据上退化到 O(n²)
- ⚠️ 归并排序的
merge中<=保证稳定性 - ⚠️ 计数排序只适用于非负整数（或可映射到非负）
- ⚠️ Python 递归深度限制约 1000，大规模数据快排需要手动提高限制或改为迭代
5. 推荐刷题清单
| 题号 | 题名 | 难度 | 关键 |
|---|---|---|---|
| 912 | 排序数组 | Medium | 实现各排序 |
| 169 | 多数元素 | Easy | 排序后取中间 |
| 215 | 第 K 个最大元素 | Medium | 快速选择 |
| 56 | 合并区间 | Medium | 按左端点排序 |
| 179 | 最大数 | Medium | 自定义排序 |
| 252 | 会议室 | Easy | 按开始时间排序 |
延伸阅读
- LeetCode 官方
- 代码随想录
- 《算法导论》(CLRS) 第 2、6、7、8 章