常见排序算法

排序是把无序序列变成有序序列的经典问题，也是面试手写代码的重灾区。冒泡、选择、插入三种 O(n²) 入门算法，归并、快排、堆排三种 O(n log n) 主流算法，加上稳定性的概念，需要成体系地掌握。

复杂度与稳定性总览

稳定性指：值相等的元素排序后，相对顺序保持不变。先记住总表再逐一下钻：

算法	平均	最坏	空间	稳定
冒泡排序	O(n²)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n²)	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)	不稳定

冒泡排序

每轮从左到右比较相邻元素，逆序就交换，最大的元素像气泡一样「浮」到最后，共需 n-1 轮：

def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]   # 交换
                swapped = True
        if not swapped:      # 本轮无交换说明已有序
            break
    return a
print(bubble_sort([5, 3, 8, 1]))   # 输出：[1, 3, 5, 8]

选择排序与插入排序

选择排序每轮从未排序部分选出最小值放到前面；插入排序把当前元素插入到已排序部分的正确位置，像理扑克牌：

def insertion_sort(a):
    for i in range(1, len(a)):
        cur = a[i]
        j = i - 1
        while j >= 0 and a[j] > cur:   # 已排序部分向右挪出空位
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = cur                 # 插入当前位置
    return a
print(insertion_sort([5, 3, 8, 1]))   # 输出：[1, 3, 5, 8]

插入排序对「近乎有序」的数据非常快（接近 O(n)），工程实现里常作为快排小数组的兜底。

归并排序与快速排序

归并排序采用分治：先拆到只剩一个元素，再两两合并有序子数组，需要 O(n) 辅助空间；快速排序选一个基准值 pivot，把比它小的放左边、大的放右边，再递归两侧，分区时元素就到位了：

归并: [5,3,8,1] → 拆 → [5] [3] [8] [1] → 合并 → [3,5] [1,8] → [1,3,5,8]
快排: pivot=5 → [3,1] 5 [8] → 递归 → [1,3] 5 [8] → [1,3,5,8]

def quick_sort(a):
    if len(a) <= 1:
        return a
    pivot = a[0]                       # 取首元素为基准
    left = [x for x in a[1:] if x <= pivot]
    right = [x for x in a[1:] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)
print(quick_sort([5, 3, 8, 1, 9]))     # 输出：[1, 3, 5, 8, 9]

工程内建排序

生产环境直接用语言内置排序：Python 的 sorted/list.sort 是 Timsort（稳定），Java 的 Arrays.sort 对基础类型用双轴快排、对象用 Timsort，Go 的 sort.Slice 基于 pdqsort。面试重点是手写快排与归并并分析复杂度；工程上几乎不需要自己实现。

面试要点

• 高频题：手写快排并分析最坏情况、数组第 K 大元素（快排分区思想）、合并两个有序数组。
• 记忆锚点：快排平均最快但有序输入可能退化 O(n²)，归并稳定但占 O(n) 空间，堆排最坏也是 O(n log n) 但不稳定。
• 回答排序题先问数据规模与是否要求稳定、原地，再选算法，能体现工程思维。

小结：掌握冒泡/选择/插入理清基础，吃透快排与归并的分治思想，再背熟稳定性与复杂度总表，排序题就稳了。