第五章：排序算法

本章目标

本章比较常见排序算法，重点理解稳定排序、分治和原地划分，而不是死记代码。

你会知道插入排序为什么适合小规模或近乎有序数据，归并排序为什么稳定，快速排序为什么平均很快。

核心概念

插入排序把左侧维护为有序区，每次把新元素插入正确位置。归并排序先递归拆分，再合并两个有序数组。

快速排序选择 pivot，把小于 pivot 和大于 pivot 的元素分开。Python 内置 sorted 支持 key，并且是稳定排序。

Python 示例

插入排序写法短，但最坏时间复杂度是 O(n^2)。

def insertion_sort(nums):
    arr = nums[:]
    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

归并排序通过合并两个有序子数组实现 O(n log n)，快速排序依赖 partition 把问题分成两边。

复杂度与常见误区

冒泡和插入排序通常是 O(n^2)，归并排序是 O(n log n) 且需要 O(n) 额外空间，快速排序平均 O(n log n)、最坏 O(n^2)。

常见误区是认为所有 O(n log n) 排序都一样。稳定性、额外空间、数据分布、是否需要 key，都会影响选择。

本章要点

排序不仅是把数字排好，更是很多算法的预处理步骤。排序后可以使用双指针、二分查找和贪心策略。

Python 实战优先使用 sorted 或 list.sort；学习手写排序是为了理解复杂度和分治思想。