1. 排序算法概览
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | ✅ | 教学/极小数据 |
| 选择排序 | O(n²) | O(n²) | O(1) | ❌ | 极小数据 |
| 插入排序 | O(n²) | O(n²) | O(1) | ✅ | 几乎有序的数据 |
| 希尔排序 | O(n^1.3) | 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) | ❌ | 内存敏感、Top-K |
| 计数排序 | O(n + k) | O(n + k) | O(k) | ✅ | 整数范围小 |
| 桶排序 | O(n + k) | O(n²) | O(n + k) | ✅ | 均匀分布数据 |
| 基数排序 | O(d(n + k)) | O(d(n + k)) | O(n + k) | ✅ | 固定位数整数 |
2. 简单排序 O(n²)
2.1 冒泡排序
def bubble_sort(arr):
n = len(arr)
for i in range(n):
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
2.2 插入排序
def insert_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 的
list.sort()在数据量小时使用插入排序，大数据用 Timsort（归并+插入的混合）。
3. 高效排序 O(n log n)
3.1 快速排序
分治 + 原地分区。工程中最常用的排序。
import random
def quick_sort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo < hi:
p = partition(arr, lo, hi)
quick_sort(arr, lo, p - 1)
quick_sort(arr, p + 1, hi)
return arr
def partition(arr, lo, hi):
"""Lomuto 分区方案"""
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
return i + 1
# 随机化快排（避免最坏情况）
def randomized_partition(arr, lo, hi):
idx = random.randint(lo, hi)
arr[idx], arr[hi] = arr[hi], arr[idx]
return partition(arr, lo, hi)
# 三路快排（处理大量重复元素）
def quick_sort_3way(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo >= hi:
return
# 分区为 < pivot, == pivot, > pivot
pivot = arr[lo]
lt, i, gt = lo, lo + 1, hi
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, lo, lt - 1)
quick_sort_3way(arr, gt + 1, hi)
return arr
3.2 归并排序
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_inplace(arr, start, mid, end):
"""使用临时数组的 O(n) 空间原地归并"""
left = arr[start:mid + 1]
right = arr[mid + 1:end + 1]
i = j = 0
k = start
while i < len(left) and j < len(right):
if left[i] <= right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
while j < len(right):
arr[k] = right[j]
j += 1
k += 1
归并排序是稳定排序，且最坏复杂度保证 O(n log n)，适合链表和外部排序。
3.3 堆排序
def heap_sort(arr):
"""原地建堆 + 排序，空间 O(1)"""
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
def heapify(arr, n, i):
"""调整以 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(arr, n, largest)
4. 线性排序
4.1 计数排序
def counting_sort(arr):
"""
适用于整数，范围 [min_val, max_val]
时间 O(n + k)，k = 值域大小
"""
if not arr:
return arr
min_val = min(arr)
max_val = max(arr)
count = [0] * (max_val - min_val + 1)
for x in arr:
count[x - 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
4.2 桶排序
def bucket_sort(arr, bucket_count=10):
"""
数据均匀分布在 [0, 1) 时效率最高
每个桶内部使用插入排序
"""
if not arr:
return arr
min_val, max_val = min(arr), max(arr)
buckets = [[] for _ in range(bucket_count)]
for x in arr:
idx = int((x - min_val) / (max_val - min_val) * (bucket_count - 1))
buckets[idx].append(x)
result = []
for bucket in buckets:
result.extend(sorted(bucket)) # 或 insert_sort
return result
4.3 基数排序（LSD）
def radix_sort(arr):
"""从低位到高位排序，稳定"""
if not arr:
return arr
max_val = max(arr)
exp = 1 # 当前位数（个位、十位...）
while max_val // exp > 0:
counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def counting_sort_by_digit(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10 # 0-9 十个桶
# 统计当前位数字频率
for x in arr:
digit = (x // exp) % 10
count[digit] += 1
# 前缀和成为位置索引
for i in range(1, 10):
count[i] += count[i - 1]
# 从后往前填充（保持稳定）
for i in range(n - 1, -1, -1):
digit = (arr[i] // exp) % 10
output[count[digit] - 1] = arr[i]
count[digit] -= 1
for i in range(n):
arr[i] = output[i]
5. 排序算法选择指南
数据规模小 (< 50):
→ 插入排序（常数小，且有适应性）
数据规模中等，随机分布:
→ 快速排序（平均最快）
数据规模大，需要稳定排序:
→ 归并排序 / Timsort
内存极度受限:
→ 堆排序（O(1) 额外空间）
数据是整数且范围小:
→ 计数排序（O(n + k)）
数据是固定位数整数:
→ 基数排序（O(d × n)）
数据分布均匀:
→ 桶排序（接近 O(n)）
已排序/几乎有序:
→ 插入排序（O(n)）
6. 稳定性证明示例
稳定的定义：相等元素排序后相对顺序不变。
稳定性重要的场景：对多级排序（如先按年龄排，再按性别排）。
| 算法 | 是否稳定 | 原因 |
|---|---|---|
| 冒泡 | ✅ | 相等不交换 |
| 插入 | ✅ | 相等不后移 |
| 归并 | ✅ | 合并时 left[i] <= right[j] 保证了稳定性 |
| 快排 | ❌ | 分区时跳跃式交换 |
| 堆排 | ❌ | 远距离交换破坏相对顺序 |
参考文章
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。