**冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序。** 下面按你这组顺序，逐个用最简洁的方式过一遍。 --- ## 1. 冒泡排序（Bubble Sort） **思想**：相邻两个比较，逆序就交换，每一轮把最大的“冒”到最后。 **例子**：`[5, 3, 8, 1]` - 5 和 3 比 → 交换 → `[3, 5, 8, 1]` - 5 和 8 比 → 不换 - 8 和 1 比 → 交换 → `[3, 5, 1, 8]` - 第一轮结束，8 到位 - 继续下一轮…… **复杂度**：平均 O(n²)，最坏 O(n²)，最好 O(n)（已有序+提前退出） **空间**：O(1) **稳定性**：稳定 --- ## 2. 选择排序（Selection Sort） **思想**：每一轮从未排序区间里选最小的，放到已排序区间末尾。 **例子**：`[5, 3, 8, 1]` - 找最小 1，和 5 交换 → `[1, 3, 8, 5]` - 剩下 `[3, 8, 5]` 找最小 3，已在位 - 剩下 `[8, 5]` 找最小 5，和 8 交换 → `[1, 3, 5, 8]` **复杂度**：平均/最坏/最好都是 O(n²) **空间**：O(1) **稳定性**：不稳定 --- ## 3. 插入排序（Insertion Sort） **思想**：像打扑克摸牌，把新牌插入到前面已排好的合适位置。 **例子**：`[5, 3, 8, 1]` - 3 插入到 5 前面 → `[3, 5, 8, 1]` - 8 不动 → `[3, 5, 8, 1]` - 1 插入到最前 → `[1, 3, 5, 8]` **复杂度**：平均/最坏 O(n²)，最好 O(n) **空间**：O(1) **稳定性**：稳定 --- ## 4. 希尔排序（Shell Sort） **思想**：插入排序的改进版。先按较大间隔分组做插入排序，再逐步缩小间隔，最后间隔为 1。 **例子**：`[5, 3, 8, 1, 9, 2]` 先按 gap=3 分组： - `[5, 1]`、`[3, 9]`、`[8, 2]` - 组内插入排序后 → `[1, 3, 2, 5, 9, 8]` 再 gap=1 做插入排序 → 最终有序。 **复杂度**：平均约 O(n^1.3)，最坏 O(n²)，取决于增量序列 **空间**：O(1) **稳定性**：不稳定 --- ## 5. 归并排序（Merge Sort） **思想**：分治。不断二分，直到每组一个元素，再两两合并成有序。 **例子**：`[5, 3, 8, 1]` - 分：`[5, 3]` 和 `[8, 1]` - 再分：`[5] [3] [8] [1]` - 合：`[3, 5]` 和 `[1, 8]` - 再合：`[1, 3, 5, 8]` **复杂度**：平均/最坏/最好都是 O(n log n) **空间**：O(n) **稳定性**：稳定 --- ## 6. 快速排序（Quick Sort） **思想**：选一个基准 pivot，把比它小的放左边，大的放右边，再对左右递归。 **例子**：`[5, 3, 8, 1]`，选 5 为 pivot - 小于 5：`[3, 1]` - 大于 5：`[8]` - 合并：`[3, 1] + [5] + [8]` - 再对 `[3, 1]` 递归 → `[1, 3]` - 最终 `[1, 3, 5, 8]` **复杂度**：平均 O(n log n)，最坏 O(n²) **空间**：O(log n)（递归栈） **稳定性**：不稳定 **优化**：随机化 pivot、三数取中 --- ## 7. 堆排序（Heap Sort） **思想**：先把数组建成大顶堆，然后每次把堆顶（最大值）和末尾交换，再调整堆。 **例子**：`[5, 3, 8, 1]` - 建大顶堆 → `[8, 5, 3, 1]` - 8 和 1 交换 → `[1, 5, 3, 8]`，调整堆 → `[5, 1, 3, 8]` - 5 和 3 交换 → `[3, 1, 5, 8]`，调整 → `[3, 1, 5, 8]` - 最终 `[1, 3, 5, 8]` **复杂度**：平均/最坏/最好都是 O(n log n) **空间**：O(1) **稳定性**：不稳定 --- ## 8. 计数排序（Counting Sort） **思想**：不是比较排序。统计每个值出现次数，再按值从小到大输出。 **例子**：`[5, 3, 8, 1]`，假设范围 0~9 - 统计：1 出现 1 次，3 出现 1 次，5 出现 1 次，8 出现 1 次 - 按顺序输出：`[1, 3, 5, 8]` **复杂度**：O(n + k)，k 是数值范围 **空间**：O(n + k) **稳定性**：稳定 **限制**：只适合整数、范围不大的场景 --- ## 八大排序速查表 |排序|平均|最坏|最好|空间|稳定| |---|---|---|---|---|---| |冒泡|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(n log n)|O(n log n)|O(n log n)|O(n)|稳定| |快速|O(n log n)|O(n²)|O(n log n)|O(log n)|不稳定| |堆|O(n log n)|O(n log n)|O(n log n)|O(1)|不稳定| |计数|O(n+k)|O(n+k)|O(n+k)|O(n+k)|稳定| --- ## 一句话记忆 - **O(n²) 三兄弟**：冒泡、选择、插入 - **插入改进**：希尔 - **O(n log n) 三巨头**：归并、快速、堆 - **非比较排序**：计数（还有桶排序、基数排序） 1. 比较排序（主流八大里的大部分） 冒泡、选择、插入、希尔、归并、快速、堆 它们靠元素之间比较来决定顺序。 2. 非比较排序 计数排序、桶排序、基数排序 它们不比较元素大小，而是利用数值本身的信息来排序。 ## 二、桶排序和基数排序到底是什么？ ### 1. 桶排序（Bucket Sort） **思想**： 把数据分到若干个“桶”里，每个桶内部再排序，最后按桶顺序合并。 **例子**： 数据范围 0~99，分成 10 个桶： - 0~9 一个桶 - 10~19 一个桶 - … - 90~99 一个桶 每个桶内部可以用插入排序，最后依次倒出来。 **复杂度**： - 平均：O(n + k) - 最坏：O(n²)（数据全挤一个桶） - 空间：O(n + k) **稳定**：取决于桶内排序算法，通常可以做到稳定。 **适用**：数据分布均匀、范围已知。 --- ### 2. 基数排序（Radix Sort） **思想**： 按位排序，从最低位到最高位（LSD）或反过来（MSD），每一位用计数排序或桶排序。 **例子**： `[170, 45, 75, 90, 802, 24, 2, 66]` - 按个位排 → `[170, 90, 802, 2, 24, 45, 75, 66]` - 按十位排 → `[802, 2, 24, 45, 66, 170, 75, 90]` - 按百位排 → `[2, 24, 45, 66, 75, 90, 170, 802]` **复杂度**： - O(d × (n + k))，d 是位数，k 是每位范围 - 空间：O(n + k) **稳定**：稳定。 **适用**：整数、定长字符串、位数不多的场景。