排序是算法世界的地基:几乎所有面试、几乎所有数据处理都绕不开它。本文把最常考的三种排序——冒泡、快排、归并——一次性讲透,包括思路、代码、复杂度,以及"面试官到底想考你什么"。
1. 为什么要学排序
排序的价值远超"把数组排整齐":有序后配合二分查找,复杂度从 O(n) 降到 O(log n);求中位数、合并区间、去重也都要先排序。更重要的是,排序是练习分治与双指针思想的绝佳素材。
2. 冒泡排序:最直观的入门
核心思想:相邻元素两两比较,大的往后冒,每一轮过后最大的元素"浮"到末尾。
def bubble_sort(arr):
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
print(bubble_sort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9]加 swapped 标志后,已有序时一轮结束,最好情况 O(n);平均与最坏仍为 O(n²)。
3. 快速排序:平均最快的通用排序
快排是分治的典型:选一个基准(pivot),小于它的放左边、大于它的放右边,再递归处理两侧。
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + mid + quick_sort(right)
print(quick_sort([3, 6, 8, 10, 1, 2, 1])) # [1, 1, 2, 3, 6, 8, 10]平均 O(n log n),空间 O(log n)(递归栈)。若基准总选到极值,最坏退化为 O(n²),工业实现常用"三数取中"规避。
4. 归并排序:稳定且复杂度稳定
归并排序先不断二分到单元素,再两两合并有序子数组。无论好坏都是 O(n log n),且是稳定排序。
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))
def merge(a, b):
i = j = 0
res = []
while i < len(a) and j < len(b):
if a[i] <= b[j]:
res.append(a[i]); i += 1
else:
res.append(b[j]); j += 1
return res + a[i:] + b[j:]
print(merge_sort([38, 27, 43, 3, 9, 82, 10])) # [3, 9, 10, 27, 38, 43, 82]代价是需要 O(n) 额外空间合并,内存极紧时不适用。
5. 三种排序一表对比
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | 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) | 稳定 |
6. 面试怎么答
- 先说思路再写代码,主动分析时间、空间、最好/最坏情况。
- 会答"为什么快排比归并快":快排缓存友好、原地操作,常数因子小。
- 工程中直接调
sorted()(Timsort),能写对原理才谈优化。
💡 学习建议:排序算法光看没用,建议用纸笔手动模拟一轮快排的交换过程,再在白板上默写三种排序,直到一次通过为止。