Go 排序算法实战：从冒泡到 TimSort 的复杂度与工程取舍

排序是算法的基石，也是面试和日常开发里出现频率最高的主题之一。本文用 Go 语言把九种经典排序算法的实现、复杂度、稳定性与适用场景讲透，最后剖析 Go 标准库 sort 包背后的工程级排序思路，帮你从"会写"进阶到"会选、会优化"。

一、先从复杂度说起

排序算法的核心评价维度有三个：时间复杂度、空间复杂度、稳定性。

| 算法 | 平均 | 最好 | 最坏 | 空间 | 稳定 | | --- | --- | --- | --- | --- | --- | | 冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 | | 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | | 插入排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 | | 希尔排序 | O(n^1.3) | O(n) | O(n²) | O(1) | 不稳定 | | 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | | 快速排序 | O(nlogn) | O(nlogn) | O(n²) | O(logn) | 不稳定 | | 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | | 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | 稳定 | | 桶排序 | O(n+k) | O(n+k) | O(n²) | O(n+k) | 稳定 |

"稳定性"指相同键值的元素排序后相对顺序是否保持不变。当一次排序需要按多个字段依次比较时（比如先按成绩、再按姓名），稳定性就非常关键——稳定排序可以安全地"从次要键往主要键逐层排"。

二、三个 O(n²) 的入门算法

1. 冒泡排序

每轮把最大的元素"冒"到末尾，通过相邻交换实现：

func BubbleSort(a []int) {
    n := len(a)
    for i := 0; i < n-1; i++ {
        swapped := false
        for j := 0; j < n-1-i; j++ {
            if a[j] > a[j+1] {
                a[j], a[j+1] = a[j+1], a[j]
                swapped = true
            }
        }
        if !swapped { // 提前终止：已经有序
            break
        }
    }
}

加了 swapped 标记后，最好情况（已有序）退化为 O(n)，这也是优化冒泡的经典手段。

2. 选择排序

每轮从剩余区间选出最小值，放到已排序区间的末尾：

func SelectSort(a []int) {
    n := len(a)
    for i := 0; i < n-1; i++ {
        minIdx := i
        for j := i + 1; j < n; j++ {
            if a[j] < a[minIdx] {
                minIdx = j
            }
        }
        a[i], a[minIdx] = a[minIdx], a[i]
    }
}

注意：选择排序无论数据有序与否都要跑满两层循环，所以最好情况也是 O(n²)。它的交换次数是 O(n)，比冒泡的 O(n²) 少，适合"交换成本高"的场景。

3. 插入排序

像打牌时理牌一样，把新元素插入到左侧已排序区间的正确位置：

func InsertSort(a []int) {
    for i := 1; i < len(a); i++ {
        cur := a[i]
        j := i - 1
        for j >= 0 && a[j] > cur {
            a[j+1] = a[j]
            j--
        }
        a[j+1] = cur
    }
}

插入排序对"几乎有序"的数据非常友好（最好 O(n)），且常数极小，是工程上最常用的小数组兜底算法——Go 标准库对小切片就采用插入排序。

三、三个 O(nlogn) 的进阶算法

4. 归并排序

分治思想的代表：先递归地把数组对半分，再合并两个有序子数组。合并时需要额外 O(n) 空间，换来的是稳定和最坏也是 O(nlogn)：

func MergeSort(a []int) []int {
    if len(a) <= 1 {
        return a
    }
    mid := len(a) / 2
    left := MergeSort(a[:mid])
    right := MergeSort(a[mid:])
    return merge(left, right)
}

func merge(l, r []int) []int {
    res := make([]int, 0, len(l)+len(r))
    i, j := 0, 0
    for i < len(l) && j < len(r) {
        if l[i] <= r[j] {
            res = append(res, l[i])
            i++
        } else {
            res = append(res, r[j])
            j++
        }
    }
    res = append(res, l[i:]...)
    res = append(res, r[j:]...)
    return res
}

归并排序还天然支持外部排序——数据大到内存放不下时，可以用多路归并把磁盘上的分片合并成有序大文件，这是 Hadoop/数据库底层排序的基础。

5. 快速排序

平均性能最好的通用排序，核心是"分区"：选定基准值 pivot，把小于它的放左边、大于它的放右边，然后递归两边：

func QuickSort(a []int, lo, hi int) {
    if lo >= hi {
        return
    }
    p := partition(a, lo, hi)
    QuickSort(a, lo, p-1)
    QuickSort(a, p+1, hi)
}

func partition(a []int, lo, hi int) int {
    pivot := a[hi]
    i := lo
    for j := lo; j < hi; j++ {
        if a[j] < pivot {
            a[i], a[j] = a[j], a[i]
            i++
        }
    }
    a[i], a[hi] = a[hi], a[i]
    return i
}

快排的隐患是最坏情况 O(n²)：当数据已经有序且每次都选到端点作 pivot 时，递归深度退化为 n。工程解法是：

• 三数取中：取 lo、mid、hi 三个位置的中位数做 pivot，避免极端序；
• 随机化 pivot：让最坏情况变成概率事件；
• 小区间用插入排序：当子区间长度小于 16 左右时，插入排序常数更小。

6. 堆排序

利用二叉堆（大顶堆）反复取出最大值完成排序，空间 O(1)，但不稳定：

func HeapSort(a []int) {
    n := len(a)
    for i := n/2 - 1; i >= 0; i-- {
        siftDown(a, i, n)
    }
    for i := n - 1; i > 0; i-- {
        a[0], a[i] = a[i], a[0]
        siftDown(a, 0, i)
    }
}

func siftDown(a []int, i, n int) {
    for {
        largest := i
        l, r := 2*i+1, 2*i+2
        if l < n && a[l] > a[largest] {
            largest = l
        }
        if r < n && a[r] > a[largest] {
            largest = r
        }
        if largest == i {
            return
        }
        a[i], a[largest] = a[largest], a[i]
        i = largest
    }
}

堆排序最实用的变体是 TopK 问题：找海量数据里最大的 K 个，用一个大小为 K 的小顶堆，每来一个新元素与堆顶比较，比堆顶大就替换并下沉。这样空间只有 O(K)，时间 O(nlogK)，是流式处理的标准解法。

四、三个线性时间排序

当数据有明确范围时，可以突破 O(nlogn) 的下界。

7. 计数排序

针对"取值范围已知且密集"的整数（如成绩 0~100、年龄 0~120）：

func CountSort(a []int, maxVal int) []int {
    count := make([]int, maxVal+1)
    for _, v := range a {
        count[v]++
    }
    idx := 0
    for v, c := range count {
        for c > 0 {
            a[idx] = v
            idx++
            c--
        }
    }
    return a
}

8. 桶排序

把元素按区间分到若干"桶"里，桶内用快排/插入排序，再依次收集。适合"数据分布均匀"的场景，比如 0~1 之间均匀分布的浮点数。

9. 基数排序

按位数从低位到高位依次做稳定排序（通常配计数排序做内层），适合固定位数的整数或短字符串，时间复杂度 O(d×n)。

五、Go 标准库 sort 的工程级设计

真实的工程排序远比"单算法"复杂。Go 的 sort.Slice 底层使用了一种混合排序策略：

• 切片长度 ≤ 12 时直接用插入排序（常数极小）；
• 长度 > 12 时用改进版快速排序：以 12 为阈值递归分治，递归深度超过 2×log2(n) 时降级为堆排序，从而保证最坏情况 O(nlogn)；
• 当快排的 partition 把数组切成"几乎有序"的状态时（检测到连续逆序对很少），切换为插入排序收尾。

这套组合就是 introsort（内省排序）+ insertion sort 的策略，和 C++ STL 的 std::sort 同源。它解决了三个单一算法各自的痛点：快排最坏退化、插入排序太慢、堆排序常数大。这正是"工程取舍"的教科书案例——没有银弹，只有针对数据特征组合出最优解。

此外 sort.Search（二分查找）、sort.SliceStable（稳定排序）、sort.Reverse（逆序）等工具也都是高频实用 API，面试造轮子、工作用标准库，是 Go 社区公认的准则。

六、实战建议总结

• 几乎有序的小数组：插入排序（工程默认首选）；
• 通用大数组：introsort（直接用 sort.Slice）；
• 需要稳定排序：归并排序（Go 的 SliceStable）；
• 内存受限：堆排序（O(1) 空间）；
• 海量 TopK：小顶堆；
• 值域小的整数：计数排序；
• 超大文件外部排序：多路归并。

排序不只是背代码，理解每种算法背后的交换次数、缓存局部性、递归深度这些工程指标，才能在真实系统里做出正确取舍。面试时能讲清楚"为什么 Go 的 sort 在长度 12 时切换算法"，比默写出十种排序更能体现水平。