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

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

有必要。我们需要理解算法背后的思想——分治、贪心、空间换时间以及分桶映射等。掌握这些思想，才能更好地跟AI协作。

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

排序无处不在

信息流、搜索结果、商品列表、好友排名，背后都有排序算法在工作。从数据库的 ORDER BY，到搜索引擎排序、推荐系统的优先级队列，本质上都是排序问题。

学习算法，本质是学习解决问题的思路，帮助我们在实际场景中做出更合理的决策。

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

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

十大排序算法并不只是十个简单的程序，它们背后浓缩了计算机大师们的心血，是几种核心算法思想的具体体现：

排序算法是学习算法思想的切入点，通过它，我们可以学习到分解问题、选择策略、优化性能的思维方式。

---

二、排序算法全景图

排序算法分类体系

排序可以分为两大类别：

1. 比较排序：通过元素之间两两比较来排序。其时间复杂度存在下界 O(n log n)，无论采用多高效的比较策略，都难以突破这一限制。

2. 非比较排序：利用数据本身的特征（如数值范围、位数等）直接确定元素位置，在特定条件下可达到线性时间 O(n)。但它对数据有一定要求，例如取值范围有限、可按位分解，或能够映射到固定区间。

---

三、十大排序算法详解

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

算法原理：遍历数组，相邻元素两两比较，将较大的项交换到右侧。每一轮遍历都会把当前最大的元素"冒泡"到数组末尾，就像汽水里的气泡一样往上浮。如果某一轮没有发生交换，说明数组已经有序，可以提前结束。

它和选择排序的思路相反：选择排序是“每次选出一个最小（或最大）放到末尾”，而冒泡排序是“通过不断交换，让最大（或最小）逐步移动到末尾”。

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

流程图

伪代码

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

应用场景

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

复杂度

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

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

---

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

算法原理：遍历数组，每一轮在未排序区域中选出最小（或最大）的元素，放到已排序区域的起始位置（或末尾）。整体需要进行大量比较，但交换次数很少，每一轮最多只交换一次。

它和插入排序的思路正好相反：选择排序是“先选一个，再放过去”；而插入排序是“从未排序中取一个，按顺序插入到已排序里”。

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

流程图

伪代码

function SelectionSort(arr):
    n = length(arr)
    for i = 0 to n - 2:                     // 遍历每个位置
        minIdx = i                          // 假设当前位置是最小值
        for j = i + 1 to n - 1:             // 在未排序区间找最小值
            if arr[j] < arr[minIdx]:
                minIdx = j                  // 更新最小值位置
        if minIdx != i:
            swap(arr[i], arr[minIdx])       // 只交换一次
    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）— 扑克牌式排序

算法原理：遍历数组，把数组分为已排序和未排序两部分，每次从未排序区间取出一个元素，插入到已排序区间的合适位置，已排序中的较大元素会依次向后移动。

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

流程图

伪代码

function InsertionSort(arr):
    n = length(arr)
    for i = 1 to n - 1:                    // 从第2个元素开始
        key = arr[i]                       // 取出待插入的牌
        j = i - 1
        while j >= 0 and arr[j] > key:     // 从右往左找位置
            arr[j + 1] = arr[j]            // 比key大的元素后移
            j = j - 1
        arr[j + 1] = key                   // 插入到正确位置
    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张牌）把牌插入到已排好的位置，先把大块牌大致排好序，再缩小间距，一次次精细调整，最后整个牌堆就排好了。相比插入排序“每次拿一张牌插入”，希尔排序就像先粗略排，再精细排，效率更高。

流程图

伪代码

function ShellSort(arr):
    n = length(arr)
    gap = n / 2                             // 初始步长
    while gap > 0:                          // 逐步缩小步长
        for i = gap to n - 1:               // 对每个分组做插入排序
            key = arr[i]
            j = i - gap
            while j >= 0 and arr[j] > key:  // 组内插入排序
                arr[j + gap] = arr[j]
                j = j - gap
            arr[j + gap] = key
        gap = gap / 2                       // 步长减半
    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），把数组划分成两部分：一部分比它小，一部分比它大，然后分别对这两部分继续做同样的操作。通过不断拆分，直到每一部分都有序，整体自然就完成排序。快速排序是分治思想的体现：先把大问题拆成小问题，再逐个击破。

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

流程图

伪代码

function QuickSort(arr, low, high):
    if low < high:
        p = Partition(arr, low, high)       // 分区，返回pivot的最终位置
        QuickSort(arr, low, p - 1)          // 递归排序左半部分
        QuickSort(arr, p + 1, high)         // 递归排序右半部分

function Partition(arr, low, high):
    pivot = arr[high]                       // 选最后一个元素作为基准
    i = low - 1                             // i 指向"小于pivot区域"的末尾
    for j = low to high - 1:
        if arr[j] <= pivot:                 // 当前元素比pivot小
            i = i + 1
            swap(arr[i], arr[j])            // 放到左边区域
    swap(arr[i + 1], arr[high])             // pivot放到中间
    return i + 1                            // 返回pivot的位置

应用场景

• 通用排序的首选：C标准库的qsort()、Java的Arrays.sort()（基本类型）都基于快排变体
• 数据库与搜索引擎：内存中的 ORDER BY、结果集排序大量使用快速排序
• 大数据 Shuffle 阶段：MapReduce、Spark 等分布式框架广泛使用快排思想
• 为什么实际最快：缓存友好（在连续内存上操作）、内层循环极其紧凑、原地排序节省内存
• 通用内存排序首选：C、C++、Java、Go 等语言标准库的默认排序均基于快排变体

复杂度

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

快速排序高效而优雅，通过不断选取基准、拆分左右区间，把复杂问题层层拆解，是开发实践中最常用的排序算法之一。看似简单的“分一分”，却蕴含着强大的力量，这也是分治思想的体现。

---

6. 归并排序（Merge Sort）— 稳定的分治

算法原理：每次将数组一分为二，递归对左右两半继续拆分，直到每个子数组只有一个元素（自然有序）。然后从最底层开始，逐层向上合并，将两个有序子数组合并为一个更大的有序数组，最终得到整体有序的结果。

生活类比：先把一筐苹果分成两篮，再每篮分成两篮……直到每篮只有一个苹果。然后从底层开始合并，每次合并按大小排序，直到所有苹果排好。

流程图

伪代码

function MergeSort(arr):
    if length(arr) <= 1:
        return arr                          // 单个元素自然有序
    mid = length(arr) / 2
    left = MergeSort(arr[0 : mid])          // 递归排序左半部分
    right = MergeSort(arr[mid : end])       // 递归排序右半部分
    return Merge(left, right)               // 合并两个有序数组

function Merge(left, right):
    result = []
    i = 0, j = 0
    while i < length(left) and j < length(right):
        if left[i] <= right[j]:             // 取出小的
            result.append(left[i])
            i++
        else:
            result.append(right[j])
            j++
    result.append(left[i:])                 // 追加剩余元素
    result.append(right[j:])
    return result

应用场景

• 需要稳定排序的场景：数据库多字段排序、UI列表渲染保持相同元素的原始顺序
• 外部排序：海量数据无法一次装入内存时，分块排序再合并，天然适合归并思想
• 链表排序：链表上做归并排序不需要额外空间（不需要随机访问），比快速排序更合适
• Python / Java标准库：Python的sorted()和Java的Collections.sort()底层均使用 Timsort（归并 + 插入）

复杂度

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

归并排序是唯一一个在最好、平均、最坏情况下都保持O(n log n)且稳定的比较排序算法，代价是需要额外空间。这就是算法设计中经典的时间-空间权衡。

---

第7-10个算法讲解挪至下一篇

请见：AI时代的算法思维：10大经典排序（第二篇）
地址：https://blog.csdn.net/jiarry/article/details/159512172

---

相关链接

• 原文地址 https://github.com/microwind/algorithms/blob/main/sorting/AI-Era-Top-10-Sorting-Algorithms.md
• 程序员必备的算法思想指南
• 程序员如何成为算法思想工程师
• 程序员如何成为Agent工程师