常见排序算法图解

1. 为什么要单独做一页图解

很多人学排序时的问题，不是代码不会写，而是“过程感”太弱。知道时间复杂度是一回事，真正看懂元素在每一轮比较、交换、划分、合并里怎样变化，是另一回事。

这一页专门解决这个问题。写法上不再强调“全量定义”，而是强调：

这个算法每一轮到底在做什么。
元素移动的方向和原因是什么。
为什么它最后一定会有序。
复杂度和稳定性是如何从过程里长出来的。

2. 先建立一张总表

算法	核心思想	平均复杂度	稳定性	原地
冒泡排序	相邻比较，大数后沉	`O(n^2)`	稳定	是
选择排序	每轮选最小值放前面	`O(n^2)`	不稳定	是
插入排序	把当前元素插入已排序区	`O(n^2)`	稳定	是
归并排序	分治拆分，再有序合并	`O(n log n)`	稳定	否
快速排序	选基准做划分	`O(n log n)`	不稳定	近似原地
堆排序	维护堆顶最值	`O(n log n)`	不稳定	是

下面的图解会分成两组：

比较排序：重点看元素之间怎样比较、交换、划分、合并。
非比较排序与改良排序：重点看怎样利用值域、位数、分桶或分组结构跳出纯比较模型。

3. 冒泡排序

3.1 它到底在做什么

冒泡排序每一轮都从左往右比较相邻元素，若顺序不对就交换。这样一趟扫完后，当前未排序区中最大的元素一定会被“冒”到最右边。

3.2 动态图

冒泡排序动画

3.3 过程理解

关键不是“它交换了很多次”，而是：

每次只做局部相邻修正。
一轮结束后，最右侧多一个确定位置。
问题规模因此不断缩小。

3.4 Go 实现

func BubbleSort(nums []int) {
    n := len(nums)
    for end := n - 1; end > 0; end-- {
        swapped := false
        for i := 0; i < end; i++ {
            if nums[i] > nums[i+1] {
                nums[i], nums[i+1] = nums[i+1], nums[i]
                swapped = true
            }
        }
        if !swapped {
            return
        }
    }
}

3.5 它为什么稳定

因为只有在前一个元素严格大于后一个元素时才交换，相等元素不会跨越彼此。

4. 选择排序

4.1 它和冒泡的本质区别

选择排序不是不断交换相邻元素，而是每一轮在未排序区里找出最小值，再把它放到当前最前面。

4.2 Go 实现

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

4.3 为什么它通常不稳定

因为最小值和当前位置交换时，可能让相等元素相对次序发生改变。

5. 插入排序

5.1 它的思维方式最像“整理手里的扑克牌”

插入排序始终维护左侧已排序区。每次从右侧取一个新元素，向左寻找插入位置，把比它大的元素整体后移，再把它插进去。

5.2 动态图

插入排序动画

5.3 过程理解

插入排序的关键不是“交换”，而是“给当前元素腾位置”。因此它在“原序列本来就接近有序”的情况下表现往往不错，因为要移动的距离很短。

5.4 Go 实现

func InsertionSort(nums []int) {
    for i := 1; i < len(nums); i++ {
        key := nums[i]
        j := i - 1
        for j >= 0 && nums[j] > key {
            nums[j+1] = nums[j]
            j--
        }
        nums[j+1] = key
    }
}

5.5 为什么它稳定

因为只有严格大于 key 的元素才后移，相等元素的先后次序不会被打乱。

6. 归并排序

6.1 它最重要的不是“拆”，而是“合并时保持有序”

归并排序把一个大问题不断拆成左右两个小问题。拆分本身不难，真正关键的是：两个子数组各自有序之后，怎样在线性时间内把它们合成一个更大的有序数组。

6.2 动态图

归并排序动画

6.3 过程理解

归并排序要抓住两层逻辑：

递归拆分保证子问题规模不断减小。
合并过程利用“两边已各自有序”这一条件，线性推进即可。

6.4 Go 实现

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

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

6.5 为什么它稳定

合并时若左右当前元素相等，先取左边，就能保持原有相对次序。

7. 快速排序

7.1 快速排序的核心不是交换，而是划分

快速排序每一轮先选一个基准值 pivot，然后把数组划成三块思路中的两块：

小于基准的放左边。
大于等于基准的放右边。

一旦基准落到最终位置，问题就被切成两个更小的同类问题。

7.2 动态图

快速排序动画

7.3 过程理解

快速排序最值得看懂的是：

基准并不是“排好整个数组”，而是先把一个元素放对。
一次划分之后，左右两侧仍未必各自有序，但它们已经满足了相对基准的关系。
递归的力量来自不断重复这种局部划分。

7.4 Go 实现

func QuickSort(nums []int) {
    var sort func(int, int)
    sort = func(left, right int) {
        if left >= right {
            return
        }
        pivot := partition(nums, left, right)
        sort(left, pivot-1)
        sort(pivot+1, right)
    }
    sort(0, len(nums)-1)
}

func partition(nums []int, left, right int) int {
    pivot := nums[right]
    i := left
    for j := left; j < right; j++ {
        if nums[j] < pivot {
            nums[i], nums[j] = nums[j], nums[i]
            i++
        }
    }
    nums[i], nums[right] = nums[right], nums[i]
    return i
}

7.5 为什么它平均快，但最坏会退化

因为若每次选出的基准都能把问题切得比较均匀，递归树高度约是 log n；但若总是切得极不均匀，例如一边几乎为空，另一边几乎是全部元素，就会退化成 O(n^2)。

8. 堆排序

8.1 它的关键不是“比较”，而是“不断把堆顶最值拿出来”

堆排序先建一个大根堆。此时堆顶就是最大值：

把堆顶和数组末尾交换。
缩小堆范围。
重新下沉恢复堆序。

8.2 动态图

堆排序动画

8.3 Go 实现

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

func siftDown(nums []int, root, size int) {
    for {
        child := root*2 + 1
        if child >= size {
            return
        }
        if child+1 < size && nums[child+1] > nums[child] {
            child++
        }
        if nums[root] >= nums[child] {
            return
        }
        nums[root], nums[child] = nums[child], nums[root]
        root = child
    }
}

8.4 堆排序适合怎样理解

它不是像归并那样“拆开再合并”，也不是像快速排序那样“围绕基准划分”，而是借助一种特殊结构，让“当前最大值”始终容易拿到。

9. 希尔排序

9.1 它为什么是“改良版插入排序”

普通插入排序每次只能让元素在相邻位置间慢慢左移。希尔排序的想法更激进：先按较大的间隔 gap 分组，让元素跨较远距离提前归位；等整体更接近有序后，再逐步缩小 gap，最后退化成一次普通插入排序。

9.2 过程理解

希尔排序最重要的不是记某个固定步长序列，而是理解：

它并没有改变“插入排序”的本质。
它只是让元素能先进行长距离移动。
当后续 gap 变小时，数组通常已经比原始状态整齐得多。

9.3 Go 实现

func ShellSort(nums []int) {
    for gap := len(nums) / 2; gap > 0; gap /= 2 {
        for i := gap; i < len(nums); i++ {
            temp := nums[i]
            j := i
            for j >= gap && nums[j-gap] > temp {
                nums[j] = nums[j-gap]
                j -= gap
            }
            nums[j] = temp
        }
    }
}

9.4 适合怎么记

把它理解成“先粗排，再细排”，比死背复杂度更重要。它不是线性时间神话，而是通过提前消除远距离逆序来改善插入排序。

10. 计数排序

10.1 它为什么不靠比较

计数排序不比较两个元素谁大谁小，而是直接统计“每个值出现了多少次”。因此它不再受比较排序 O(n log n) 下界约束。

10.2 过程理解

要看懂计数排序，关键是接受一个前提：

元素必须能映射到有限值域。
我们不是在“排元素”，而是在“排值域位置”。

当值域很小时，这非常高效；当值域极大时，这会变得浪费。

10.3 Go 实现

func CountingSort(nums []int, maxVal int) []int {
    count := make([]int, maxVal+1)
    for _, x := range nums {
        count[x]++
    }

    out := make([]int, 0, len(nums))
    for value, c := range count {
        for ; c > 0; c-- {
            out = append(out, value)
        }
    }
    return out
}

10.4 什么时候适合

数据是整数。
值域小。
希望时间接近线性。

11. 桶排序

11.1 它的核心不是“排”，而是“先分布，再局部处理”

桶排序先把数据按范围分到若干桶里。若输入分布比较均匀，每个桶里只会落少量元素，此时桶内再排序的代价就会小很多。

11.2 过程理解

桶排序最重要的前提不是“我会写桶”，而是：

你得知道怎么分桶。
你得相信数据分布不会极度偏斜。

如果所有数据都落进同一个桶，它就基本退化了。

11.3 Go 实现

这里示例按 0~99 的整数分到 10 个桶中，每个桶内部用插入排序。

func BucketSort(nums []int) []int {
    if len(nums) == 0 {
        return nil
    }

    buckets := make([][]int, 10)
    for _, x := range nums {
        idx := x / 10
        if idx > 9 {
            idx = 9
        }
        buckets[idx] = append(buckets[idx], x)
    }

    out := make([]int, 0, len(nums))
    for _, bucket := range buckets {
        insertionSort(bucket)
        out = append(out, bucket...)
    }
    return out
}

func insertionSort(nums []int) {
    for i := 1; i < len(nums); i++ {
        key := nums[i]
        j := i - 1
        for j >= 0 && nums[j] > key {
            nums[j+1] = nums[j]
            j--
        }
        nums[j+1] = key
    }
}

11.4 什么时候适合

数据分布较均匀。
值域或区间能自然切分。
希望用“分而治之”的方式把大排序拆成多个小排序。

12. 基数排序

12.1 它为什么要“按位排”

基数排序把一个整数或定长键拆成多个“位”，例如个位、十位、百位，然后从低位到高位逐轮做稳定排序。

12.2 过程理解

例如 170, 45, 75, 90, 802, 24, 2, 66：

先按个位排，元素会按 0~9 的个位分布。
再按十位稳定排，保留个位轮建立起来的局部顺序。
再按百位排，最终得到整体有序。

这里“稳定”是关键。
如果每一轮子排序不稳定，前一轮已经建立好的低位顺序就会被破坏。

12.3 Go 实现

func RadixSort(nums []int) []int {
    if len(nums) == 0 {
        return nil
    }

    out := make([]int, len(nums))
    copy(out, nums)

    maxVal := out[0]
    for _, x := range out {
        if x > maxVal {
            maxVal = x
        }
    }

    for exp := 1; maxVal/exp > 0; exp *= 10 {
        out = countingSortByDigit(out, exp)
    }
    return out
}

func countingSortByDigit(nums []int, exp int) []int {
    count := make([]int, 10)
    out := make([]int, len(nums))

    for _, x := range nums {
        digit := (x / exp) % 10
        count[digit]++
    }

    for i := 1; i < 10; i++ {
        count[i] += count[i-1]
    }

    for i := len(nums) - 1; i >= 0; i-- {
        digit := (nums[i] / exp) % 10
        out[count[digit]-1] = nums[i]
        count[digit]--
    }
    return out
}

12.4 什么时候适合

数据是整数或可拆位键。
位数 d 不大。
希望避开比较排序下界。

13. 什么时候该选哪一种

教学入门、理解交换与稳定性：先看冒泡、选择、插入。
需要稳定的 O(n log n)：归并排序。
工程里平均性能很强、缓存友好：快速排序。
想要最坏时间上界稳定在 O(n log n) 且原地：堆排序。
输入本来就接近有序、小规模排序：插入排序常常很好用。

14. 最容易混淆的几组区别

10.1 冒泡 vs 选择

冒泡是一轮轮把最大值送到末尾。
选择是一轮轮把最小值拉到开头。

10.2 插入 vs 选择

插入排序维护的是左侧整体有序区。
选择排序只保证每轮确定一个最小值的位置。

10.3 归并 vs 快速

归并的核心是“拆分后合并”。
快速的核心是“划分后递归”。

10.4 快速 vs 堆

快速排序靠划分递归推进。
堆排序靠堆顶最值不断出列。

15. 学这一页时应达到的标准

看完之后，最好不是只记住“谁是 O(n log n)”，而是能回答：

这个算法每一轮在确定什么。
哪些元素已经处在正确位置。
哪些元素还只是局部有序。
为什么这个过程最终会收敛到全局有序。

如果这几件事都能讲清楚，排序这一块就不再只是模板题，而是真正理解了。

16. 对比版补充

如果你想把整个排序家族横向放到一张大表里比较，包括希尔排序、计数排序、桶排序、基数排序这些没有在本页逐个动画展开的算法，可以继续看：

十大经典排序算法对比

常见排序算法图解 ​

1. 为什么要单独做一页图解 ​

2. 先建立一张总表 ​

3. 冒泡排序 ​

3.1 它到底在做什么 ​

3.2 动态图 ​

3.3 过程理解 ​

3.4 Go 实现 ​

3.5 它为什么稳定 ​

4. 选择排序 ​

4.1 它和冒泡的本质区别 ​

4.2 Go 实现 ​

4.3 为什么它通常不稳定 ​

5. 插入排序 ​

5.1 它的思维方式最像“整理手里的扑克牌” ​

5.2 动态图 ​

5.3 过程理解 ​

5.4 Go 实现 ​

5.5 为什么它稳定 ​

6. 归并排序 ​

6.1 它最重要的不是“拆”，而是“合并时保持有序” ​

6.2 动态图 ​

6.3 过程理解 ​

6.4 Go 实现 ​

6.5 为什么它稳定 ​

7. 快速排序 ​

7.1 快速排序的核心不是交换，而是划分 ​

7.2 动态图 ​

7.3 过程理解 ​

7.4 Go 实现 ​

7.5 为什么它平均快，但最坏会退化 ​

8. 堆排序 ​

8.1 它的关键不是“比较”，而是“不断把堆顶最值拿出来” ​

8.2 动态图 ​

8.3 Go 实现 ​

8.4 堆排序适合怎样理解 ​

9. 希尔排序 ​

9.1 它为什么是“改良版插入排序” ​

9.2 过程理解 ​

9.3 Go 实现 ​

9.4 适合怎么记 ​

10. 计数排序 ​

10.1 它为什么不靠比较 ​

10.2 过程理解 ​

10.3 Go 实现 ​

10.4 什么时候适合 ​

11. 桶排序 ​

11.1 它的核心不是“排”，而是“先分布，再局部处理” ​

11.2 过程理解 ​

11.3 Go 实现 ​

11.4 什么时候适合 ​

12. 基数排序 ​

12.1 它为什么要“按位排” ​

12.2 过程理解 ​

12.3 Go 实现 ​

12.4 什么时候适合 ​

13. 什么时候该选哪一种 ​

14. 最容易混淆的几组区别 ​

10.1 冒泡 vs 选择 ​

10.2 插入 vs 选择 ​

10.3 归并 vs 快速 ​

10.4 快速 vs 堆 ​

15. 学这一页时应达到的标准 ​

16. 对比版补充 ​