排序算法：快排、归并、堆排序与计数排序
排序是算法面试中最基础也最常考的知识点。理解各种排序的原理、复杂度和适用场景，是算法能力的基石。
一、排序算法总览
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 | 核心思想 |
|---|---|---|---|---|---|
| 选择排序 | O(n²) | O(n²) | O(1) | ✗ | 每次选最小放前面 |
| 插入排序 | O(n²) | O(n²) | O(1) | ✓ | 构建有序序列逐个插入 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | ✗ | 分治 + 分区 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | ✓ | 分治 + 合并 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | ✗ | 建堆 + 堆化 |
| 计数排序 | O(n + k) | O(n + k) | O(k) | ✓ | 统计数组映射 |
稳定性：相等元素排序后相对顺序是否保持不变。
二、基础排序
1. 选择排序（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(n-1)/2 次
- 特点：交换次数最少（最多 n-1 次），适合写操作昂贵的场景
2. 插入排序（Insertion Sort）
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 < 20）非常高效，常作为快排的 fallback
三、高级排序
3. 快速排序（Quick Sort）⭐
面试最常考的排序算法。
import random
def quick_sort(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
pivot_idx = partition(arr, low, high)
quick_sort(arr, low, pivot_idx - 1)
quick_sort(arr, pivot_idx + 1, high)
return arr
def partition(arr, low, high):
# 随机选择 pivot，避免最坏情况
pivot_idx = random.randint(low, high)
arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
关键点：
- 分区（Partition）是核心操作
- 随机 pivot 可避免有序数组退化成 O(n²)
- 尾递归优化可减少栈深度
三路快排（处理大量重复元素）：
def quick_sort_3way(arr, low, high):
if low >= high:
return
pivot = arr[low]
lt, gt = low, high
i = low + 1
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1
i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1
else:
i += 1
quick_sort_3way(arr, low, lt - 1)
quick_sort_3way(arr, gt + 1, high)
4. 归并排序（Merge Sort）
稳定排序的首选。
def merge_sort(arr):
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
迭代版本（非递归，空间更优）：
def merge_sort_iterative(arr):
n = len(arr)
width = 1
while width < n:
for i in range(0, n, 2 * width):
left = arr[i:i + width]
right = arr[i + width:i + 2 * width]
merged = merge(left, right)
arr[i:i + len(merged)] = merged
width *= 2
return arr
应用：求逆序对数量（LeetCode 493）。
5. 堆排序
原地排序，空间 O(1)。
def heap_sort(arr):
n = len(arr)
# 建堆（从最后一个非叶节点向下调整）
for i in range(n // 2 - 1, -1, -1):
heapify_down(arr, n, i)
# 每次将堆顶（最大值）放到末尾
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify_down(arr, i, 0)
return arr
def heapify_down(arr, n, i):
largest = i
left = 2 * i + 1
right = 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_down(arr, n, largest)
建堆复杂度 O(n)：
- 高度为 h 的节点最多有 ⌈n / 2^(h+1)⌉ 个
- 每个节点下沉时间为 O(h)
- Σ(h=0 to log n) ⌈n / 2^(h+1)⌉ · O(h) = O(n)
四、线性时间排序
6. 计数排序（Counting Sort）
适用于数据范围 k 不大的整数排序。
def counting_sort(arr):
if not arr:
return arr
min_val, max_val = min(arr), max(arr)
count = [0] * (max_val - min_val + 1)
for num in arr:
count[num - min_val] += 1
idx = 0
for i, c in enumerate(count):
while c > 0:
arr[idx] = i + min_val
idx += 1
c -= 1
return arr
扩展：
- 基数排序：多轮计数排序，按位处理，O(d × (n + k))
- 桶排序：数据分桶后各自排序，适合均匀分布
五、稳定性与面试要点
为什么稳定性重要？
场景：先按「分数」排序，再按「年级」稳定排序 → 同年级内按分数有序。
快排 vs 归并
| 维度 | 快排 | 归并 |
|---|---|---|
| 常数因子 | 较小（原地操作） | 较大（额外数组） |
| 稳定性 | 不稳定 | 稳定 |
| 空间 | O(log n) 栈 | O(n) |
| 最坏情况 | O(n²)，需随机 pivot | 始终 O(n log n) |
| Java 实现 | Arrays.sort() 对象用归并 | Arrays.sort() 基本类型用快排 |
面试常见问题
Q: 如何实现一个 O(n) 时间、O(1) 空间的排序？
这是不可能的一般情况（比较排序下限 Ω(n log n)）。但如果数据有特定约束（如 0/1 只有两种值、数据范围小），可用计数排序或荷兰国旗问题解法。
Q: 100 万个数中找 Top 10？
维护大小为 10 的小根堆，O(n log 10) ≈ O(n)。比全排序 O(n log n) 快。
Q: 对链表排序用什么算法？
归并排序，因为：
- 快排需要随机访问，链表效率低
- 归并排序适合顺序访问，且空间可优化到 O(1)（迭代合并）
相关文章：
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。