8. 排序算法怎么准备
排序算法是手撕代码中非常基础的内容。测试岗一般不会要求你把所有排序算法都手写到极致，但冒泡排序、选择排序、插入排序、快速排序思想、归并排序思想，以及排序稳定性和时间复杂度，要能说清楚。排序题常常用来考察循环、交换、边界和复杂度。
对测试工程师来说，排序不仅是算法题，也和日常测试有关。接口返回列表是否按时间倒序，商品价格是否升序，排行榜是否正确，分页排序是否稳定，这些都是排序思维的业务应用。
一、排序题要掌握什么
建议重点掌握：
- 冒泡排序能手写；
- 选择排序能说明；
- 插入排序能理解；
- 快速排序能讲思路；
- 归并排序能讲思路；
- 知道稳定排序含义；
- 知道常见复杂度；
- 能结合业务排序测试。
测试岗面试手写最多的是冒泡排序和快速排序基础版。
二、冒泡排序
冒泡排序每轮把最大的元素交换到末尾。
def bubble_sort(nums):
n = len(nums)
for i in range(n):
for j in range(0, n - 1 - i):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums
复杂度：时间 O(n²)，空间 O(1)。
边界：空数组、单元素、已排序、逆序、重复元素。
三、选择排序
每轮选择最小值放到当前位置。
def selection_sort(nums):
n = len(nums)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if nums[j] < nums[min_idx]:
min_idx = j
nums[i], nums[min_idx] = nums[min_idx], nums[i]
return nums
选择排序也通常是 O(n²)。
四、插入排序
类似打牌，把当前元素插入到前面已经有序的部分。
def insertion_sort(nums):
for i in range(1, len(nums)):
key = nums[i]
j = i - 1
while j >= 0 and nums[j] > key:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = key
return nums
对基本有序数组较友好。
五、快速排序思想
快速排序选择一个基准值，把数组分成小于基准和大于基准两部分，再递归排序。
def quick_sort(nums):
if len(nums) <= 1:
return nums
pivot = nums[0]
left = [x for x in nums[1:] if x <= pivot]
right = [x for x in nums[1:] if x > pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
平均时间复杂度 O(n log n)，最坏 O(n²)。
面试中如果不要求原地快排，这个版本更容易写清楚。
六、归并排序思想
归并排序先拆分，再合并有序数组。
核心是“分治”：
拆成两半 -> 分别排序 -> 合并两个有序数组
归并排序时间复杂度 O(n log n)，需要额外空间。
七、稳定排序怎么理解
稳定排序指相等元素排序后相对顺序不变。
比如两个订单金额相同，原来 A 在 B 前面，排序后仍然 A 在 B 前面，就是稳定。
稳定性在业务排序中有意义，比如按分数排序后，同分按创建时间保持原顺序。
常见稳定排序：冒泡、插入、归并。
常见不稳定排序：选择、快速排序通常不稳定。
八、业务排序测试怎么做
排序不仅是算法题，也要会测业务：
- 升序是否正确；
- 降序是否正确；
- 相同值排序规则；
- 空值排序；
- 多字段排序；
- 分页后排序是否全局正确；
- 前端排序还是后端排序；
- 大数据量排序性能。
例如订单列表按创建时间倒序，要验证第一页和第二页之间也符合全局倒序，而不是每页内部排序。
九、常见错误
- 冒泡内层边界写错；
- 快排递归终止条件漏写；
- 重复元素处理不当；
- 忘记空数组；
- 混淆稳定性；
- 业务排序只看第一页。
十、面试回答模板
如果面试官问“排序算法怎么准备”，可以这样回答：
测试岗排序题我会重点准备冒泡排序、选择排序、插入排序、快速排序和归并排序思想。冒泡排序可以手写，核心是每轮把最大值交换到末尾；快速排序用分治思想，选基准后分成左右两部分递归排序。复杂度上，冒泡、选择、插入通常是 O(n²)，快排和归并平均是 O(n log n)。除了算法本身，我还会结合业务排序测试，比如列表升降序、相同值排序规则、空值、多字段排序和分页全局排序。
十一、练习清单
- 手写冒泡排序；
- 手写选择排序；
- 手写插入排序；
- 讲清快速排序；
- 讲清归并排序；
- 理解稳定排序；
- 总结复杂度；
- 测业务升序降序；
- 测分页排序；
- 准备排序面试回答。
排序算法准备到“能手写基础、能讲复杂度、能结合业务测试”就足够覆盖多数测试岗面试。
配套刷题：
