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

ivZPez8gP

8人浏览 · 2026-03-29 19:21:47

ivZPez8gP · 2026-03-29 19:21:47 发布

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

排序无处不在

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

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

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

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

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

排序算法的核心思想

分治思想

贪心思想

插入思想

交换思想

映射思想

树形结构

快速排序\n归并排序

选择排序

插入排序\n希尔排序

冒泡排序

计数排序\n基数排序\n桶排序

堆排序

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

二、排序算法全景图

排序算法分类体系

十大排序算法

比较排序\n理论下界 O(n log n)

非比较排序\n可突破 O(n log n)

交换排序

选择排序

插入排序

归并排序

冒泡排序

快速排序

选择排序

堆排序

插入排序

希尔排序

计数排序

基数排序

桶排序

排序可以分为两大类别：

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

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

三、十大排序算法详解

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

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

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

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

流程图

否

是

否

是

否

是

开始下一轮

开始

未排序区间
= [0, n-1]

区间长度 > 1 ?

排序完成

从左到右
依次比较相邻元素

前一个 > 后一个 ?

继续比较

交换

到达区间末尾 ?

缩小区间
（最大值归位）

伪代码

	`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）— 最少的交换

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

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

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

流程图

否

是

否

是

开始下一轮

开始

未排序区间 = [0, n-1]

区间长度 > 1 ?

排序完成

在未排序区间
挑选最小值

最小值是否
在当前位置 ?

交换最小值
到当前位置

无需交换

缩小未排序区间
长度 - 1

伪代码

	`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）— 扑克牌式排序

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

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

流程图

否

是

否

开始下一轮

开始

未排序区间
= [1, n-1]

区间长度 > 0 ?

排序完成

选取当前元素
作为待插入 key

前方元素
是否 > key ?

向后移动元素
为 key 腾位置

将 key 放入合适位置

未排序区间长度 - 1

伪代码

	`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张牌）把牌插入到已排好的位置，先把大块牌大致排好序，再缩小间距，一次次精细调整，最后整个牌堆就排好了。相比插入排序“每次拿一张牌插入”，希尔排序就像先粗略排，再精细排，效率更高。

流程图

否

是

否

开始下一轮

开始

初始化
gap = n / 2

gap > 0 ?

排序完成

遍历未排序区间
i = gap → n-1

取当前元素
作为待插入 key

按 gap 向前比较
前方元素是否 > key ?

向后移动元素
为 key 腾位置

将 key 插入
正确位置

处理下一个 i

gap /= 2

伪代码

	`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），把数组划分成两部分：一部分比它小，一部分比它大，然后分别对这两部分继续做同样的操作。通过不断拆分，直到每一部分都有序，整体自然就完成排序。快速排序是分治思想的体现：先把大问题拆成小问题，再逐个击破。

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

流程图

否

是

返回上一层

开始

当前区间长度 > 1 ?

选择 pivot 元素

分区操作：
小于 pivot 在左
大于 pivot 在右
返回 pivot 位置 p

递归排序左半区
quickSort(low, p-1)

递归排序右半区
quickSort(p+1, high)

伪代码

	`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）— 稳定的分治

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

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

流程图

否

是

返回上一层

开始

当前数组长度 > 1 ?

从中间二分为
左半部分 + 右半部分

递归排序左半区
mergeSort(left)

递归排序右半区
mergeSort(right)

合并两个有序子数组
返回有序数组

伪代码

	`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. 堆排序（Heap Sort）— 树形选择

算法原理：利用堆（完全二叉树）这种数据结构来排序。先把数组构建成一个大顶堆（每个父节点都大于等于子节点），然后不断取出堆顶（最大值）交换到数组末尾，并对剩余元素重新堆化处理，直到全部有序。

堆的精妙之处在于：利用的是完全二叉树的结构，用数组直接表示，父子节点关系通过索引计算完成。对于位置i的元素，其左子节点在2i+1，右子节点在2i+2，父节点在(i-1)/2，无需额外指针。

先把数组构建成大顶堆（每个父节点 ≥ 子节点）。
每次取出堆顶（最大值）放到数组末尾，然后缩小堆的范围并重新调整堆，使剩余元素依然保持大顶堆性质。
重复上述步骤，直到所有元素排序完成。

生活类比：就像整理一堆水果，把最大的放在顶上，每次取出最顶上的水果放到盘子里，然后让剩下的水果重新“自动堆成一座山”，下一次再取最大的。不断重复，最终就把所有水果从大到小排好。

流程图

否

是

开始

构建大顶堆\n从最后一个非叶节点\n到根逐个下沉

未排序部分\n长度 > 1 ?

排序完成

交换堆顶与\n未排序部分末尾

未排序范围 - 1

对堆顶执行下沉\nsift down

伪代码

	`function HeapSort(arr):`
	`n = length(arr)`
	`// 建堆：从最后一个非叶节点开始，自底向上堆化`
	`for i = n/2 - 1 downto 0:`
	`SiftDown(arr, i, n)`

	`// 排序：反复取堆顶放到末尾`
	`for i = n - 1 downto 1:`
	`swap(arr[0], arr[i]) // 堆顶（最大值）放到末尾`
	`SiftDown(arr, 0, i) // 对剩余元素重新堆化`

	`function SiftDown(arr, parent, size):`
	`while 2 * parent + 1 < size: // 还有子节点`
	`child = 2 * parent + 1 // 左子节点`
	`if child + 1 < size and arr[child + 1] > arr[child]:`
	`child = child + 1 // 选较大的子节点`
	`if arr[parent] >= arr[child]:`
	`break // 父节点已经最大，停止`
	`swap(arr[parent], arr[child]) // 下沉`
	`parent = child`

应用场景

优先队列调度：操作系统进程调度、网络包调度底层均基于堆结构
大规模 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 分依次输出，每个分数出现几次就写几次，这样就得到排序好的成绩单。

流程图

开始

找到最大值 max\n创建计数数组 count[0..max]

遍历数组\n统计每个元素出现次数

对 count 做前缀和\n确定每个元素的位置

反向遍历原数组\n按 count 放入输出数组

排序完成

伪代码

	`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[i]变为"<=i的元素总数"`
	`count[i] = count[i] + count[i - 1]`

	`output = array of length(arr)`
	`for i = length(arr) - 1 downto 0: // 反向遍历保证稳定性`
	`output[count[arr[i]] - 1] = arr[i]`
	`count[arr[i]] = count[arr[i]] - 1`

	`return output`

应用场景

年龄排序：范围 0–150 固定且集中，计数排序可实现极致线性效率
考试成绩排序：分数 0–100 范围有限，无需比较即可完成排序与统计
字符频率统计：ASCII 字符集 0–127，非常适合计数排序
基数排序的子过程：基数排序每一位的稳定排序通常由计数排序实现

复杂度

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

计数排序高效、直接，不依赖比较，尤其适合数值范围有限的数据，就像统计考试分数一样，是一种巧妙且实用的排序方法。

9. 基数排序（Radix Sort）— 逐位排序

算法原理：不直接比较数字大小，而是按个位、十位、百位……逐位处理。每一位使用稳定排序（通常是计数排序），保证低位顺序在高位处理时不被破坏，最终得到完整有序的序列。属于非比较排序，适合整数且位数有限的数组。

生活类比：就像整理邮政编码的信件，先按最后一位数字分堆，再按倒数第二位分堆……逐位处理，直到按完整邮编顺序排列好所有信件。

流程图

否

是

处理下一位

开始

计算数组
最大位数 d

digit = 1\n从最低位开始

digit ≤ d ?
(最低位 → 最高位)

排序完成

对数组 a[0..n-1]\n按 digit 位进行稳定排序\n（计数排序）

digit++

伪代码

	`function RadixSort(arr):`
	`max_val = max(arr)`
	`d = number_of_digits(max_val) // 最大位数`

	`exp = 1 // 当前位的权重：1, 10, 100, ...`
	`for digit = 1 to d:`
	`CountingSortByDigit(arr, exp) // 按当前位做稳定排序`
	`exp = exp * 10`

	`function CountingSortByDigit(arr, exp):`
	`count = array of 10 zeros // 0-9 十个桶`
	`output = array of length(arr)`

	`for x in arr:`
	`digit = (x / exp) % 10 // 取出当前位`
	`count[digit]++`

	`for i = 1 to 9:`
	`count[i] += count[i - 1] // 前缀和`

	`for i = length(arr) - 1 downto 0: // 反向遍历保证稳定性`
	`digit = (arr[i] / exp) % 10`
	`output[count[digit] - 1] = arr[i]`
	`count[digit]--`

	`copy output to arr`

应用场景

手机号排序：11 位定长数字，效率 O (11n)，远快于 O (n log n)
IP 地址排序：4 段固定格式数字，天然适合逐段排序
身份证号排序：定长数字编码，规则统一，可实现线性时间排序
大规模整数 / 定长字符串：位数固定时，O (dn) 接近线性，海量数据下优势巨大

复杂度

最好	平均	最坏	空间	稳定性
O(n × d)	O(n × d)	O(n × d)	O(n + k)	稳定

基数排序不依赖比较，高效处理大规模整数或固定长度字符串，就像邮局分拣信件一样，是实践中验证过的排序智慧。

10. 桶排序（Bucket Sort）— 分桶映射

算法原理：将数据按数值区间划分成若干桶，每个桶内部单独排序（通常用插入排序），然后按桶的顺序依次合并。效率依赖于数据均匀分布，每个桶元素较少时，总体性能最佳。属于非比较排序，适合分布较均匀的数值数组。

生活类比：就像收集水果，把苹果按大小或颜色放到不同的篮子里，每个篮子里再整理一下，最后按篮子顺序排列所有苹果，就得到整齐的果堆。

流程图

是，处理下一桶

否

开始

创建 k 个空桶\n确定值域范围

遍历数组\n将每个元素
分配到对应桶

对每个非空桶\n内部排序

按桶顺序\n依次拼接所有元素

还有未处理的桶 ?

排序完成

伪代码

	`function BucketSort(arr):`
	`n = length(arr)`
	`min_val = min(arr)`
	`max_val = max(arr)`
	`bucket_count = n // 桶数量通常取n`
	`bucket_size = (max_val - min_val + 1) / bucket_count`

	`buckets = array of bucket_count empty lists`

	`for x in arr: // 将元素分配到桶中`
	`idx = (x - min_val) / bucket_size`
	`buckets[idx].append(x)`

	`for each bucket in buckets: // 桶内排序（通常用插入排序）`
	`InsertionSort(bucket)`

	`result = concatenate all buckets // 按桶顺序拼接`
	`return result`

应用场景

均匀分布浮点数排序：如 0～1 随机浮点数，分桶后接近线性时间
分段统计排序：成绩分段、商品价格区间、用户年龄段归类等业务场景
图像颜色直方图：按像素值分桶统计，是图像处理经典应用
请求负载均衡：按特征值分桶分发流量，实现均匀调度与分流

复杂度

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

桶排序适合均匀分布的数据，高效且直观，就像按篮子整理水果一样，是实践中处理特定场景的稳定排序方法。

四、10大排序算法特点回顾

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性	说明
冒泡排序	O(n²)	O(n²)	O(1)	稳定	相邻元素两两比较，最大或最小元素逐轮“冒”到最后
选择排序	O(n²)	O(n²)	O(1)	不稳定	每轮选择未排序里最小（或最大）元素放到已排序末尾
插入排序	O(n²)	O(n²)	O(1)	稳定	类似打扑克，从未排序中取元素插入到已排序序列中
快速排序	O(n log n)	O(n²)	O(log n)	不稳定	分治+分区，选基准元素将数组拆分，递归排序左右区间
归并排序	O(n log n)	O(n log n)	O(n)	稳定	递归拆分数组到单个元素，再不断向上合并两个有序子数组
堆排序	O(n log n)	O(n log n)	O(1)	不稳定	利用大顶堆选择最大元素放到末尾，原地排序
希尔排序	O(n^1.3)	O(n²)	O(1)	不稳定	分组式插入排序，先大步长分组排序再逐步缩小步长
计数排序	O(n + k)	O(n + k)	O(n + k)	稳定	不比较元素大小，统计每个值出现的次数并直接输出
基数排序	O(n × d)	O(n × d)	O(n + k)	稳定	按位从低到高分别排序，最后从高到低合并数据
桶排序	O(n + k)	O(n²)	O(n + k)	稳定	将数据分成若干桶，桶内排序后再将全部桶合并