AI时代，重温10大经典排序算法

AI时代，重温10大经典排序算法

AI可以轻松生成任何排序算法代码，那么我们还有必要学习算法吗？

AI时代，不需要人工手写排序算法了，但我们需要理解算法背后的思想——分治、贪心、空间换时间以及分桶映射等。掌握这些思想，有利于我们与AI协作时给出正确的决策和指导。

一、为什么还要学排序算法？

排序无处不在

信息流、搜索结果、商品列表、好友排名，背后都有排序算法在工作。数据库的 ORDER BY、搜索引擎的结果排序、推荐系统的优先级队列——排序是计算世界中最基础、最常见的计算。
实现排序算法并非难事，难的是遇到实际场景时能做出合理的判断和决策：

• 100万条订单数据，应该用快速排序还是归并排序？为什么？
  
• 用户ID是纯数字且范围有限，能不能用计数排序把O(n log n)优化到O(n)？
  
• 排序结果传递给下游做二次排序好还是提前排好再给下游？性能和稳定性哪个更重要？
  

排序算法是算法思想的缩影

十大排序算法并不只是十个简单的程序，它们背后浓缩了计算机大师们的心血，是几种核心算法思想的具体体现：
%%{init: {'flowchart': {'nodeSpacing': 50, 'rankSpacing': 30, 'padding': 20}}}%%graph TD    ROOT(["排序算法的核心思想"]):::root    ROOT --> A["分治思想"]    ROOT --> B["贪心思想"]    ROOT --> C["插入思想"]    ROOT --> D["交换思想"]    ROOT --> E["映射思想"]    ROOT --> F["树形结构"]    A --> A1["快速排序\n归并排序"]    B --> B1["选择排序"]    C --> C1["插入排序\n希尔排序"]    D --> D1["冒泡排序"]    E --> E1["计数排序\n基数排序\n桶排序"]    F --> F1["堆排序"]    %% root更突出    classDef root fill:#111827,color:#ffffff,stroke:#000000,stroke-width:2px,rx:12,ry:12    %% 分类层    style A fill:#11908A,stroke:#0F6E56,color:#ffffff,rx:10,ry:10    style B fill:#534AB7,stroke:#3C3489,color:#ffffff,rx:10,ry:10    style C fill:#D85A30,stroke:#993C1D,color:#ffffff,rx:10,ry:10    style D fill:#BA7517,stroke:#854F0B,color:#ffffff,rx:10,ry:10    style E fill:#185FA5,stroke:#0C447C,color:#ffffff,rx:10,ry:10    style F fill:#993556,stroke:#72243E,color:#ffffff,rx:10,ry:10    %% 叶子层    style A1 fill:#11908A,stroke:#0F6E56,color:#ffffff,rx:10,ry:10    style B1 fill:#534AB7,stroke:#3C3489,color:#ffffff,rx:10,ry:10    style C1 fill:#D85A30,stroke:#993C1D,color:#ffffff,rx:10,ry:10    style D1 fill:#BA7517,stroke:#854F0B,color:#ffffff,rx:10,ry:10    style E1 fill:#185FA5,stroke:#0C447C,color:#ffffff,rx:10,ry:10    style F1 fill:#993556,stroke:#72243E,color:#ffffff,rx:10,ry:10学会这些思想，我们面对的就不仅仅是排序问题——而是所有需要"分解、组合、选择、映射"的工程问题。
二、排序算法全景图

排序算法分类体系

%%{init: {'flowchart': {'nodeSpacing': 15, 'rankSpacing': 25, 'padding': 20}}}%%graph TD    ROOT(["十大排序算法"])    ROOT --> CMP("比较排序\n理论下界 O(n log n)")    ROOT --> NCMP("非比较排序\n可突破 O(n log n)")    CMP --> SWAP["交换排序"]    CMP --> SEL["选择排序"]    CMP --> INS["插入排序"]    CMP --> MRG["归并排序"]    SWAP --> BUB["冒泡排序"]    SWAP --> QCK["快速排序"]    SEL --> SSEL["选择排序"]    SEL --> HEAP["堆排序"]    INS --> DINS["插入排序"]    INS --> SHELL["希尔排序"]    NCMP --> CNT["计数排序"]    NCMP --> RDX["基数排序"]    NCMP --> BKT["桶排序"]    classDef root fill:#111827,stroke:#2C2C2A,color:#fff    classDef cat fill:#11908A,color:#fff,stroke:#0a2647    classDef sub fill:#533483,color:#fff,stroke:#2c1654    classDef leaf fill:#e94560,color:#fff,stroke:#c81e45    class ROOT root    class CMP,NCMP cat    class SWAP,SEL,INS,MRG sub    class BUB,QCK,SSEL,HEAP,DINS,SHELL,CNT,RDX,BKT leaf排序可以分为两大类别：
1. 比较排序：通过元素之间两两比较来排顺序。它的时间复杂度有个下限是 O(n log n)，不管用多聪明的比较方法，都很难突破这个极限。
2. 非比较排序：是利用数据本身的特点（比如数字范围、位数这些）直接确定位置，它可以做到线性时间 O(n)。不过它对数据有一些要求，比如数值范围不能太大、能拆分，或者能映射到固定的区间。
三、十大排序算法详解

1. 冒泡排序（Bubble Sort）— 最朴素的交换

算法原理：遍历数组，相邻元素两两比较，将大的项交换到右侧。每一轮遍历都会把当前最大的元素"冒泡"到数组末尾，就像汽水里的气泡一样往上浮。如果某一轮没有发生交换，说明数组已经有序，可以提前结束。
它和选择排序的思路正好相反：选择排序是“每次选出一个最小（或最大）放到末尾”，而冒泡排序是“逐步交换，让最大（或最小）冒到末尾”。

生活类比：体育课排队，让相邻两人比身高，矮的站前面，高的站后面。一轮下来，最高的人一定到了队尾。

流程图

%%{init: {'flowchart': {'nodeSpacing': 20, 'rankSpacing': 25, 'padding': 15}}}%%graph LR    S(["开始"]) --> INIT["未排序区间
= [0, n-1]"]    INIT --> OUTER{"区间长度 > 1 ?"}    OUTER -->|"否"| END(["排序完成"])    OUTER -->|"是"| LOOP["从左到右
依次比较相邻元素"]    LOOP --> CMP{"前一个 > 后一个 ?"}    CMP -->|"否"| NEXT["继续比较"]    CMP -->|"是"| SWAP["交换"]    SWAP --> NEXT    NEXT --> CHECK{"到达区间末尾 ?"}    CHECK -->|"否"| LOOP    CHECK -->|"是"| SHRINK["缩小区间
（最大值归位）"]    SHRINK --> |"开始下一轮"| OUTER    %% 样式    classDef start fill:#FF6253,color:#fff,stroke:#c94c4c,stroke-width:2px    classDef decision fill:#6a5acd,color:#fff,stroke:#483d8b,stroke-width:2px    classDef process fill:#11908A,color:#fff,stroke:#008080,stroke-width:2px    class S,END start    class OUTER,CMP,CHECK decision    class INIT,LOOP,NEXT,SWAP,SHRINK process伪代码

1. function BubbleSort(arr):
2.     n = length(arr)
3.     for i = 0 to n - 2:                     // 外层循环：共 n-1 轮
4.         swapped = false                     // 优化点：设置已交换标志
5.         for j = 0 to n - 2 - i:             // 内层循环：每轮减少一个
6.             if arr[j] > arr[j + 1]:         // 相邻比较
7.                 swap(arr[j], arr[j + 1])    // 逆序则交换
8.                 swapped = true
9.         if not swapped:                     // 本轮无交换，已有序，跳过
10.             break
11.     return arr

复制代码

应用场景

• 算法入门教学：逻辑最简单、最直观，是所有算法教材的首选入门排序
  
• 近乎有序的小规模数据：加入提前终止优化后，对基本有序的数据可达到 O (n) 效率
  
• 嵌入式与极简环境：代码极短、占用空间极小，适合资源受限设备
  

复杂度

最好平均最坏空间稳定性O(n)O(n²)O(n²)O(1)稳定

冒泡排序非常好理解，性能也很稳定，虽然现实中使用不多，但是因为很简单、很形象，所以通常是学习排序算法的第一课。

2. 选择排序（Selection Sort）— 最少的交换

算法原理：遍历数组，每一轮在未排序区域中选出最小（或最大）的元素，放到已排序区域的末尾。整体需要进行大量比较，但交换次数很少，每一轮最多只交换一次。
它和插入排序的思路正好相反：选择排序是“先选一个，再放过去”；而插入排序是“从未排序中取一个，按顺序插入到已排序里”。

生活类比：就像从一堆没有次序的苹果里，每次都挑出最小（或最大）的一个，放到一边按大小排好。每次只挑一个，慢慢就把所有苹果按顺序排好了。

流程图

%%{init: {'flowchart': {'nodeSpacing': 20, 'rankSpacing': 25, 'padding': 15}}}%%graph LR    S(["开始"]) --> INIT["未排序区间 = [0, n-1]"]    INIT --> OUTER{"区间长度 > 1 ?"}    OUTER -->|"否"| END(["排序完成"])    OUTER -->|"是"| FIND["在未排序区间
挑选最小值"]    FIND --> DOSWAP{"最小值是否
在当前位置 ?"}    DOSWAP -->|"否"| SWAP["交换最小值
到当前位置"]    DOSWAP -->|"是"| NEXT["无需交换"]    SWAP --> NEXT    NEXT --> SHRINK["缩小未排序区间
长度 - 1"]    SHRINK --> |"开始下一轮"| OUTER    %% 样式    classDef start fill:#FF6253,color:#fff,stroke:#c94c4c,stroke-width:2px    classDef decision fill:#6a5acd,color:#fff,stroke:#483d8b,stroke-width:2px    classDef process fill:#11908A,color:#fff,stroke:#008080,stroke-width:2px    class S,END start    class OUTER,DOSWAP decision    class INIT,FIND,SWAP,NEXT,SHRINK process伪代码

1. function SelectionSort(arr):
2.     n = length(arr)
3.     for i = 0 to n - 2:                     // 遍历每个位置
4.         minIdx = i                          // 假设当前位置是最小值
5.         for j = i + 1 to n - 1:             // 在未排序区间找最小值
6.             if arr[j] < arr[minIdx]:
7.                 minIdx = j                  // 更新最小值位置
8.         if minIdx != i:
9.             swap(arr[i], arr[minIdx])       // 只交换一次
10.     return arr

复制代码

应用场景

• 写入敏感的存储设备：如 Flash、ROM 等，选择排序交换次数最少，能显著降低写入损耗
  
• 小规模数据排序：实现简单、逻辑清晰，数据量小时性能差异不明显
  
• 朴素 Top‑K 问题：只需执行 K 轮即可选出前 K 大 / 前 K 小元素，无需完整排序
  

复杂度

最好平均最坏空间稳定性O(n²)O(n²)O(n²)O(1)不稳定

选择排序不太稳定，因为交换时可能把原本顺序相同的元素颠倒掉。比如 [5, 5, 4]，第一轮把4和第一个5交换，第一个5就跑到最后面了。选择排序也是非常好理解的方式，每次从剩下的一堆里把最大或最小的挑出来，放到已排序里面去。

3. 插入排序（Insertion Sort）— 扑克牌式排序

算法原理：遍历数组，把数组分为已排序和未排序两部分，每次从未排序中取出一个元素，插入到已排序部分的合适位置，已排序元素右移腾出位置。

生活类比：就像打扑克牌一样，把牌分成两堆——已排好序的牌和未排的牌。一开始，第一张牌算作已排序部分，其余都是未排序部分。然后每次从未排序中拿一张牌，插入到已排序中的正确位置，已排序的牌往右移一位，未排序的牌则减少一张。

流程图

%%{init: {'flowchart': {'nodeSpacing': 20, 'rankSpacing': 25, 'padding': 15}}}%%graph LR    S(["开始"]) --> INIT["未排序区间
= [1, n-1]"]    INIT --> OUTER{"区间长度 > 0 ?"}    OUTER -->|"否"| END(["排序完成"])    OUTER -->|"是"| KEY["选取当前元素
作为待插入 key"]    KEY --> INNER{"前方元素
是否 > key ?"}    INNER -->|"是"| SHIFT["向后移动元素
为 key 腾位置"]     SHIFT --> INNER    INNER -->|"否"| PLACE["将 key 放入合适位置"]    PLACE --> SHRINK["未排序区间长度 - 1"]    SHRINK --> |"开始下一轮"| OUTER    %% 样式    classDef start fill:#FF6253,color:#fff,stroke:#c94c4c,stroke-width:2px    classDef decision fill:#6a5acd,color:#fff,stroke:#483d8b,stroke-width:2px    classDef process fill:#11908A,color:#fff,stroke:#008080,stroke-width:2px    class S,END start    class OUTER,INNER decision    class INIT,KEY,SHIFT,PLACE,SHRINK process伪代码

1. function InsertionSort(arr):
2.     n = length(arr)
3.     for i = 1 to n - 1:                    // 从第2个元素开始
4.         key = arr[i]                       // 取出待插入的牌
5.         j = i - 1
6.         while j >= 0 and arr[j] > key:     // 从右往左找位置
7.             arr[j + 1] = arr[j]            // 比key大的元素后移
8.             j = j - 1
9.         arr[j + 1] = key                   // 插入到正确位置
10.     return arr

复制代码

应用场景

• 小规模数据排序：n < 50时，插入排序的常数因子极小，实际速度往往最快
  
• Timsort的子过程：Python的sorted()和Java的Collections.sort()底层都用插入排序处理小分区
  
• 在线流式排序：数据逐个到达时，可随时插入到正确位置，无需重排整体
  
• 近乎有序的数据：最优情况可达到 O (n)，是简单排序中效率最高的一种
  

复杂度

最好平均最坏空间稳定性O(n)O(n²)O(n²)O(1)稳定

插入排序稳定、直观，对小规模或几乎有序的数据特别高效，就像整理扑克牌一样，这是我们大家都会的方式，是经过实践检验的经典算法。

4. 希尔排序（Shell Sort）— 跳跃式插入

算法原理：希尔排序是插入排序的改进版，先用较大的步长（gap）将数组分成若干组，对每组分别进行插入排序，然后逐步缩小gap，最终gap=1完成整体排序。通过先对间隔较大的子序列排序，可以显著减少元素移动次数，从而提高排序效率，尤其是对于较大或无序的数据序列。

生活类比：就像整理扑克牌，如果手里有很多牌，一次只按相隔一定间距（比如每隔10张牌）把牌插入到已排好的位置，先把大块牌大致排好序，再缩小间距，一次次精细调整，最后整个牌堆就排好了。相比插入排序“每次拿一张牌插入”，希尔排序就像先粗略排，再精细排，效率更高。

流程图

%%{init: {'flowchart': {'nodeSpacing': 20, 'rankSpacing': 25, 'padding': 15}}}%%graph LR    S(["开始"]) --> GAP["初始化
gap = n / 2"]    GAP --> GCHK{"gap > 0 ?"}    GCHK -->|"否"| END(["排序完成"])    GCHK -->|"是"| OUTER["遍历未排序区间
i = gap → n-1"]    OUTER --> KEY["取当前元素
作为待插入 key"]    KEY --> INNER{"按 gap 向前比较
前方元素是否 > key ?"}    INNER -->|"是"| SHIFT["向后移动元素
为 key 腾位置"]    SHIFT --> INNER    INNER -->|"否"| PLACE["将 key 插入
正确位置"]    PLACE --> NEXT["处理下一个 i"]    NEXT --> OUTER    OUTER --> GSHR["gap /= 2"]    GSHR --> |"开始下一轮"| GCHK    %% 样式    classDef start fill:#FF6253,color:#fff,stroke:#c94c4c,stroke-width:2px    classDef decision fill:#6a5acd,color:#fff,stroke:#483d8b,stroke-width:2px    classDef process fill:#11908A,color:#fff,stroke:#008080,stroke-width:2px    class S,END start    class GCHK,INNER decision    class GAP,OUTER,KEY,SHIFT,PLACE,NEXT,GSHR process伪代码

1. function ShellSort(arr):
2.     n = length(arr)
3.     gap = n / 2                             // 初始步长
4.     while gap > 0:                          // 逐步缩小步长
5.         for i = gap to n - 1:               // 对每个分组做插入排序
6.             key = arr[i]
7.             j = i - gap
8.             while j >= 0 and arr[j] > key:  // 组内插入排序
9.                 arr[j + gap] = arr[j]
10.                 j = j - gap
11.             arr[j + gap] = key
12.         gap = gap / 2                       // 步长减半
13.     return arr

复制代码

应用场景

• 中等规模数据（100～10000 条）：效率远超 O (n²) 算法，又不需要快排的递归栈空间
  
• 嵌入式与小型系统：原地排序、代码简洁，性能稳定
  
• Linux 内核等底层场景：部分版本使用希尔排序处理中等规模数据排序
  

复杂度

最好平均最坏空间稳定性O(n log n)O(n^1.3)O(n²)O(1)不稳定

希尔排序的时间复杂度取决于步长（gap）的选择。希尔建议的初始步长是 N/2，即每次把数组分成两半进行排序。这种取法在大多数情况下比直接插入排序效率高，但也并不是最优选择。希尔排序给我们的启迪是将大量数据拆分成小组来处理。

5. 快速排序（Quick Sort）— 分治的经典

算法原理：选一个基准元素（pivot），把数组划分成两部分：一部分比它小，一部分比它大，然后分别对这两部分继续做同样的操作。通过不断拆分，直到每一部分都有序，整体自然就排好序了。快速排序时分治思想的体现：先把大问题拆成小问题，再逐个击破。

生活类比：就像给一群人排队，先选一个人当“基准”，比他矮的站左边，比他高的站右边，然后左右两边也重复这个过程。随着不断分组，每一小组都会越来越有序，直到每组只剩下一个人时，整个队伍就排好了。

流程图

%%{init: {'flowchart': {'nodeSpacing': 20, 'rankSpacing': 25, 'padding': 15}}}%%graph LR    S(["开始"]) --> CHK["当前区间长度 > 1 ?"]    CHK -->|"否"| END(["返回"])    CHK -->|"是"| PIVOT["选择 pivot 元素"]    PIVOT --> PART["分区操作：
小于 pivot 在左
大于 pivot 在右
返回 pivot 位置 p"]    PART --> LEFT["递归排序左半区
quickSort(low, p-1)"]    LEFT --> RIGHT["递归排序右半区
quickSort(p+1, high)"]    RIGHT --> |"返回上一层"| CHK    %% 节点样式    classDef start fill:#FF6253,color:#fff,stroke:#c94c4c,stroke-width:2px    classDef decision fill:#6a5acd,color:#fff,stroke:#483d8b,stroke-width:2px    classDef pivot fill:#ffb703,color:#000,stroke:#e09f00,stroke-width:2px    classDef partition fill:#A3F1B5,color:#003d2e,stroke:#04a777,stroke-width:2px    classDef recurse fill:#11908A,color:#fff,stroke:#0b5f7a,stroke-width:2px    %% 应用样式    class S,END start    class CHK decision    class PIVOT pivot    class PART partition    class LEFT,RIGHT recurse伪代码

1. function QuickSort(arr, low, high):
2.     if low < high:
3.         p = Partition(arr, low, high)       // 分区，返回pivot的最终位置
4.         QuickSort(arr, low, p - 1)          // 递归排序左半部分
5.         QuickSort(arr, p + 1, high)         // 递归排序右半部分
7. function Partition(arr, low, high):
8.     pivot = arr[high]                       // 选最后一个元素作为基准
9.     i = low - 1                             // i 指向"小于pivot区域"的末尾
10.     for j = low to high - 1:
11.         if arr[j] <= pivot:                 // 当前元素比pivot小
12.             i = i + 1
13.             swap(arr[i], arr[j])            // 放到左边区域
14.     swap(arr[i + 1], arr[high])             // pivot放到中间
15.     return i + 1                            // 返回pivot的位置

复制代码

应用场景

• 优先队列调度：操作系统进程调度、网络包调度底层均基于堆结构
  
• 大规模 Top‑K 问题：从10亿级数据中取前K个值，只需维护大小为K的小顶堆，复杂度 O (n log k)
  
• 内存受限环境：原地排序 O (1) 空间，最坏复杂度稳定 O (n log n)
  
• 高性能定时器：Nginx、Go Runtime、Redis 均使用堆管理定时器
  

复杂度

最好平均最坏空间稳定性O(n log n)O(n log n)O(n log n)O(1)不稳定

堆排序理论上非常理想——原地排序且时间复杂度稳定为 O(n log n)，但在实际应用中通常比快速排序慢。原因在于堆化操作需要在数组中频繁跳跃访问父子节点，父节点和子节点在内存中相距较远，CPU 缓存命中率低，导致效率下降。

8. 计数排序（Counting Sort）— 用空间换时间

算法原理：统计每个元素出现的次数，用额外数组记录到对应下标，再按顺序输出实现排序，不进行元素比较。适合元素范围不大、为整数的数组，时间复杂度 O(n + k)。

生活类比： 就像统计考试分数：准备一个 0–100 的计数表，遍历所有试卷，把每个分数出现的次数加 1。最后从 0 分到 100 分依次输出，每个分数出现几次就写几次，这样就得到排序好的成绩单。

流程图

%%{init: {'flowchart': {'nodeSpacing': 10, 'rankSpacing': 20, 'padding': 15}}}%%graph LR    S(["开始"]) --> RANGE["找到最大值 max\n创建计数数组 count[0..max]"]    RANGE --> COUNT["遍历数组\n统计每个元素出现次数"]    COUNT --> PREFIX["对 count 做前缀和\n确定每个元素的位置"]    PREFIX --> FILL["反向遍历原数组\n按 count 放入输出数组"]    FILL --> END(["排序完成"])    classDef start fill:#FF6253,color:#fff,stroke:#c94c4c,stroke-width:2px    classDef process fill:#11908A,color:#fff,stroke:#008080,stroke-width:2px    class S,END start    class RANGE,COUNT,PREFIX,FILL process伪代码

[code]function CountingSort(arr):    max_val = max(arr)                      // 找到最大值    count = array of (max_val + 1) zeros    // 创建计数数组    for x in arr:                           // 统计每个值的出现次数        count[x] = count[x] + 1    for i = 1 to max_val:                   // 前缀和：count变为"