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)。除了算法本身，我还会结合业务排序测试，比如列表升降序、相同值排序规则、空值、多字段排序和分页全局排序。

十一、练习清单

手写冒泡排序；
手写选择排序；
手写插入排序；
讲清快速排序；
讲清归并排序；
理解稳定排序；
总结复杂度；
测业务升序降序；
测分页排序；
准备排序面试回答。

排序算法准备到“能手写基础、能讲复杂度、能结合业务测试”就足够覆盖多数测试岗面试。

配套刷题：

手撕代码