排序算法研究：定义、分类、性能边界与主流语言默认实现

概览

系统研究排序算法，覆盖排序定义、稳定性、原地排序、比较排序与非比较排序、冒泡排序、插入排序、选择排序、快速排序、归并排序、TimSort、堆排序、计数排序、桶排序、基数排序、速度与空间取舍，以及 Java、Python、Go 的默认排序实现。

摘要

排序是计算机科学中最基础的数据处理操作之一，其目标是将一组数据按照预先定义的顺序重新排列。排序算法广泛应用于检索、数据库查询、分页展示、日志分析、排行榜、去重合并、调度优先级、索引构建和算法预处理等场景。不同排序算法在时间复杂度、空间复杂度、稳定性、是否原地排序、是否适合部分有序数据、是否适合固定范围整数键等方面存在差异。本文基于 NIST Dictionary of Algorithms and Data Structures、Java 官方文档、Python 官方文档和 Go 官方文档及源码，对排序的定义、常见排序算法、性能边界、空间使用以及 Java、Python、Go 默认排序实现进行系统归纳。研究结果表明，不存在对所有输入、所有数据类型和所有运行环境都最快的排序算法；排序算法选择必须结合数据规模、数据分布、键范围、稳定性要求、内存限制和语言运行时实现。

关键词： 排序算法；稳定排序；原地排序；快速排序；归并排序；TimSort；Dual-Pivot Quicksort；pdqsort

1. 引言

排序操作将数据元素按照某种比较规则或键值规则重新排列。NIST 对排序的定义是：将项目按照预先确定的顺序排列。形式化地说，排序后的输出序列必须满足两个条件：第一，元素按照指定顺序排列；第二，输出序列必须是输入序列的一个排列，即不能丢失、增加或改变元素本身。1

排序不仅用于直接生成有序列表，也经常作为其他算法和系统模块的前置步骤。例如，二分查找要求输入序列已经有序；数据库的 ORDER BY、分页展示、搜索结果排序、排行榜、归并多个有序数据流、区间统计、日志审计和任务优先级调度都依赖排序或有序结构。排序算法因此既是算法课程中的基础问题，也是工程系统中的基础组件。

2. 排序的基本概念

2.1 有序性

排序首先依赖一个确定的顺序关系。对于数值类型，常见顺序是升序或降序；对于字符串，常见顺序是字典序；对于对象，顺序通常由比较器或 key 函数定义。只要比较规则确定，排序算法的目标就是使输出序列中任意相邻元素满足该规则。

2.2 稳定性

稳定排序是指：如果两个元素的排序键相等，则排序后它们的相对顺序与排序前保持一致。NIST 将 stable 定义为排序算法在比较相等元素时保留其原始顺序。2

稳定性在多字段排序中具有实际意义。例如，若先按照姓名排序，再按照部门排序，第二次排序若是稳定排序，则同一部门内部仍保留前一次姓名排序的顺序。Python 的 list.sort() 和 sorted() 明确保证稳定性；Java 的对象数组排序和 Collections.sort 也明确要求稳定性；Go 的 sort.Sort 和 sort.Slice 默认不保证稳定性，需要显式使用 sort.Stable、sort.SliceStable 或 slices.SortStableFunc。57

2.3 原地排序与辅助空间

原地排序通常指排序过程中只使用常数级或很小的额外辅助空间。插入排序、选择排序、冒泡排序和常见快速排序实现可以原地完成。归并排序、TimSort、计数排序和基数排序通常需要额外数组、缓冲区或桶结构。空间消耗与具体实现相关，因此“最节约空间”不能脱离实现讨论。

2.4 比较排序与非比较排序

比较排序通过比较两个元素的大小关系决定顺序，典型算法包括冒泡排序、插入排序、选择排序、快速排序、堆排序、归并排序和 TimSort。非比较排序不完全依赖元素两两比较，而利用键的结构或范围，典型算法包括计数排序、桶排序和基数排序。计数排序适合不同键值数量相对于元素数量较小的场景；基数排序通过多轮分配和收集处理键的不同部分。3

3. 排序算法的应用场景

排序的应用场景可以归纳为以下几类。

第一，检索前置。二分查找、范围查询和有序集合检索通常要求输入数据已经有序。Java Collections.binarySearch 文档明确要求列表在调用前必须按对应规则升序排序，否则结果未定义。5

第二，展示排序。后台管理系统、交易流水、日志平台、搜索结果、排行榜和报表系统通常需要按照时间、分数、权重、价格、优先级或业务字段排序。

第三，数据处理。去重、归并、分组、Top-K、区间统计、批处理任务和数据清洗常需要先排序再线性扫描，从而降低后续处理复杂度。

第四，系统调度。任务调度、优先级队列、限流窗口、延迟任务和缓存淘汰策略通常依赖有序结构或局部排序。

第五，算法构造。许多算法需要排序作为前置步骤，例如贪心算法、扫描线算法、最小生成树算法、区间合并、离散化和双指针算法。

4. 常见排序算法分类

4.1 简单平方级排序算法

冒泡排序通过重复比较相邻元素并交换逆序对完成排序。NIST 文档说明，冒泡排序是原地稳定排序；在任意数据上复杂度为 O(n²)，在几乎有序数据上可接近 Θ(n)。3

插入排序每次取出下一个元素，并将其插入到前面已经有序的部分中。NIST 文档说明，插入排序通常需要 O(n²) 时间，但可以原地完成。3 插入排序常作为小数组排序或混合排序中的子过程。

选择排序每轮从未排序部分选择最小元素并放到最终位置。NIST 文档说明，选择排序时间复杂度为 Θ(n²)，交换次数为 O(n)，可原地实现；基于交换的选择排序实现不稳定。3

4.2 快速排序及其变体

快速排序通过选择一个 pivot，将数据划分为小于 pivot 和大于 pivot 的两个部分，然后递归处理子序列。NIST 文档说明，快速排序通常为原地排序，最坏时间复杂度为 Θ(n²)，典型情况下为 O(n log n)。文档同时指出，经过调优的快速排序在实践中通常可以超过许多具有 O(n log n) 最坏复杂度的排序算法。3

Java 对基本类型数组使用 Dual-Pivot Quicksort。Oracle JDK 文档说明，该算法由 Vladimir Yaroslavskiy、Jon Bentley 和 Joshua Bloch 提供，在所有数据集上提供 O(n log n) 性能，并且通常快于传统单轴快速排序。4

Go 当前标准库源码中，slices.Sort 的有序元素路径使用 pdqsortOrdered，其实现包含小分区插入排序、坏 pivot 情况下堆排序兜底、模式打散和部分有序检测等逻辑。7

4.3 归并排序与 TimSort

归并排序通过递归或迭代方式将序列拆分为子序列，分别排序后再合并。归并排序通常是稳定排序，但需要额外缓冲空间。

TimSort 是一种稳定、自适应的混合排序算法，源自 Tim Peters 为 Python list sort 设计的算法。Java 对对象数组的排序文档说明，其对象数组排序实现为稳定、自适应、迭代式归并排序，并且改编自 Tim Peters 的 Python list sort。该实现对于部分有序数组可以减少比较次数；对于随机数组提供传统归并排序性能；临时空间在近似有序数组中可以小到常数级，在随机数组中可达到 n/2 个对象引用。4

Python 官方文档明确保证 list.sort() 和 sorted() 稳定；Python 官方变更说明中也指出 list.sort() 和 sorted() 使用 TimSort。6

4.4 堆排序

堆排序利用堆结构维护当前最大值或最小值，并通过反复取出堆顶元素完成排序。堆排序的典型特征是最坏时间复杂度为 O(n log n)，并且可以原地实现。它通常不稳定。Go 的 pdqsortOrdered 在坏 pivot 次数过多时回退到 heapSortOrdered，体现了在标准库实现中使用堆排序作为最坏情况兜底策略。7

4.5 计数排序、桶排序与基数排序

计数排序通过统计每个键出现次数，然后根据前缀计数确定元素位置。NIST 文档说明，计数排序适合不同键值数量相对于元素数量较小的场景。3

基数排序通过多轮分配和收集，按键的某一部分逐步完成排序。NIST 文档说明，基数排序可以从最低有效部分开始，每一轮将元素分配到桶中，然后保持顺序收集，再按照更高有效部分继续处理。3

桶排序将元素分配到多个桶中，分别对桶内元素排序后再合并。桶排序是否高效取决于数据分布、桶数量和桶内排序方式。对于整数、定长字符串、固定范围枚举值等键结构明确的数据，非比较排序可能获得低于通用比较排序的时间复杂度，但通常需要额外空间。

5. 哪种排序算法最快

不存在对所有输入、所有数据类型、所有稳定性要求和所有硬件环境都最快的排序算法。NIST 对排序算法选择因素的说明指出，算法选择取决于元素数量、可用工作内存、数据已有顺序程度、键值范围、比较代价和移动代价等因素。1

在普通比较排序中，快速排序及其变体通常具有较高实践性能。Java 基本类型数组采用 Dual-Pivot Quicksort；Go 当前 slices.Sort 源码使用 pdqsort 风格实现，并对小数组、部分有序数据和坏 pivot 情况分别处理。4

在对象排序或需要稳定性的场景中，TimSort 或稳定归并排序更常见。Java 对对象数组使用稳定、自适应、迭代式归并排序；Python 的 list.sort() 和 sorted() 使用 TimSort 并保证稳定性。4

在键范围较小或键结构明确的场景中，计数排序、桶排序和基数排序可能比比较排序更快。其前提是键值范围、桶数量或位数结构使额外空间和多轮分配成本低于比较排序成本。3

在大数组并且有多核资源时，Java Arrays.parallelSort 使用并行排序-归并算法，将数组拆分为子数组分别排序再合并，但需要不超过原数组大小的工作空间。4

因此，“最快排序算法”只能在约束条件下定义：如果是 Java 基本类型数组，官方默认实现是 Dual-Pivot Quicksort；如果是 Python list，官方实现使用 TimSort；如果是 Go 当前 slices 排序路径，源码使用 pdqsort 风格实现；如果是小范围整数键，计数排序或基数排序可能更适合。工程中应以语言标准库默认排序作为基准，再基于真实数据分布和性能测试决定是否替换。

6. 哪种排序算法最节约空间

如果只考虑辅助空间，原地排序算法最节约空间。插入排序、选择排序和冒泡排序都可以原地实现，但它们在一般输入上的时间复杂度通常为 O(n²)，不适合作为大规模通用排序的默认选择。3

在通用比较排序中，如果同时关注最坏 O(n log n) 时间复杂度和低辅助空间，堆排序是典型代表。快速排序通常也是原地排序，但递归调用会产生栈空间，且未做保护的实现存在最坏 O(n²) 时间复杂度。归并排序和 TimSort通常需要额外缓冲空间；Java 对对象数组排序的官方文档说明，其临时空间可能从较小常数增长到 n/2 个对象引用。4

计数排序、桶排序和基数排序依赖计数数组、桶或辅助数组，空间消耗与键范围、桶数量、位数和实现方式有关。因此，它们不属于最节约辅助空间的排序类别，但在合适数据条件下可以换取更低时间成本。

因此，若问题只问“最节约辅助空间”，答案是原地排序类别；若要求同时满足大规模通用排序和稳定 O(n log n) 级时间，则堆排序是典型低空间比较排序；若使用语言标准库，应以该语言官方排序实现为准，因为标准库通常在速度、稳定性、空间和输入分布之间做了综合实现。

7. Java、Python、Go 默认排序实现

7.1 Java

Java 标准库中存在多类排序入口。

第一，Arrays.sort 对基本类型数组使用 Dual-Pivot Quicksort。Oracle 官方文档明确说明，该算法由 Vladimir Yaroslavskiy、Jon Bentley 和 Joshua Bloch 提供，在所有数据集上提供 O(n log n) 性能，并通常快于传统单轴快速排序。4

第二，Arrays.sort(Object[]) 对对象数组要求稳定。Oracle 官方文档说明，其实现是稳定、自适应、迭代式归并排序，并且改编自 Tim Peters 的 Python list sort。该实现对于部分有序输入会减少比较次数，随机输入上提供传统归并排序性能。4

第三，Collections.sort(List) 明确保证稳定性，并且当前文档说明其实现会委托给 List.sort(null)；带比较器版本会委托给 List.sort(c)。5

第四，Arrays.parallelSort 使用并行排序-归并算法，将数组拆分为子数组排序后再合并；其工作空间不超过原数组或指定范围大小。4

需要注意的是，Oracle 文档同时说明，文档中的“实现说明”不是规范的一部分，只要满足规范要求，实现可以替换算法。例如，对象数组排序不必须永远使用某个具体归并排序实现，但必须满足稳定性要求。4

7.2 Python

Python 提供两个主要排序入口：list.sort() 和内置函数 sorted()。list.sort() 原地修改列表；sorted() 接收任意 iterable 并返回新的排序列表。Python 官方文档明确说明，这两个排序都是稳定排序。6

Python 官方文档还指出，Python 的排序实现使用 TimSort。TimSort 通过识别已有有序片段并进行归并，适合包含部分有序结构的实际数据。由于 Python 对排序稳定性作出文档保证，因此多关键字排序可以通过多次稳定排序或 key 函数完成。6

7.3 Go

Go 提供 sort 包和较新的 slices 包。

sort.Sort 文档说明，它会执行 O(n log n) 次 Less 与 Swap 调用，并且不保证稳定性。sort.Slice 同样不保证稳定性；若需要稳定排序，需要使用 sort.Stable 或 sort.SliceStable。sort.Stable 保持相等元素原有顺序。7

Go 1.22 起，sort.Ints、sort.Float64s 和 sort.Strings 等函数会调用 slices.Sort。slices.Sort 用于有序类型切片；slices.SortFunc 不保证稳定性；slices.SortStableFunc 保证相等元素保持原始顺序。7

从当前 Go 标准库源码看，slices.Sort 的有序类型排序路径调用 pdqsortOrdered。该实现对小规模分区使用插入排序，在坏 pivot 过多时回退到堆排序，并对可能已经有序的数据执行部分插入排序检测。因此，Go 当前默认非稳定排序实现属于 pdqsort 风格的混合排序实现。7

8. 对比总结

维度	客观结论
排序定义	将元素按照预定顺序排列，输出必须有序且是输入的排列
常见算法	冒泡、插入、选择、快速、堆、归并、TimSort、计数、桶、基数等
是否存在全局最快算法	不存在；取决于数据规模、分布、键范围、稳定性、内存和实现
通用实践速度常见候选	快速排序变体、TimSort、pdqsort、并行排序、计数/基数排序
最节约空间	原地排序最节约辅助空间；若兼顾通用 O(n log n) 最坏时间，堆排序是典型代表
Java 默认排序	基本类型数组：Dual-Pivot Quicksort；对象数组/List：稳定自适应归并排序/TimSort 风格；parallelSort：并行排序-归并
Python 默认排序	list.sort() 与 sorted() 使用 TimSort，并保证稳定性
Go 默认排序	sort.Sort、sort.Slice 不稳定；稳定排序需显式调用；当前 slices.Sort 源码路径使用 pdqsort 风格实现

9. 工程使用原则

第一，普通业务开发应优先使用语言标准库排序。Java、Python 和 Go 标准库已经根据数据类型、稳定性和运行时特征选择了默认实现。

第二，需要稳定性时必须显式确认 API 语义。Python 默认稳定；Java 对象数组和 List 排序稳定；Go 默认 sort.Sort 与 sort.Slice 不稳定，必须使用稳定排序 API。

第三，数据规模较小或数据近似有序时，插入排序或混合排序中的插入排序阶段具有实际意义，但普通业务不应单独手写替代标准库。

第四，键范围较小且类型明确时，可以考虑计数排序、桶排序或基数排序；这类算法通过额外空间换取更低时间成本。

第五，内存限制严格时，应关注排序实现的辅助空间。归并排序、TimSort、计数排序和基数排序通常需要额外空间；原地排序更节约空间。

第六，大规模数据排序如果超出内存容量，应使用外部排序、数据库排序、搜索引擎排序或分布式计算框架，而不是直接在单进程内存中排序。

10. 结论

排序算法不存在单一最优解。排序算法的选择由数据规模、数据分布、键空间、稳定性要求、空间限制和语言运行时实现共同决定。快速排序及其变体在通用内存排序中具有较高实践性能；TimSort 适合对象排序和部分有序数据，并提供稳定性；计数排序和基数排序适合键范围或键结构受限的数据；堆排序在低辅助空间和最坏 O(n log n) 时间方面具有代表性。

在主流语言实现中，Java 对基本类型数组采用 Dual-Pivot Quicksort，对对象数组和 List 提供稳定排序；Python 的 list.sort() 与 sorted() 使用稳定 TimSort；Go 的默认非稳定排序在当前源码中使用 pdqsort 风格实现，并提供显式稳定排序 API。工程实践中，标准库排序应作为默认选择；只有在稳定性、空间、键范围或数据规模提出特殊要求时，才需要选择专门排序算法或替换默认实现。

参考资料

1 NIST Dictionary of Algorithms and Data Structures 对 sort 的定义、形式化条件、算法清单和排序算法选择因素的说明。(XLinux)

2 NIST 对 stable 的定义：稳定排序在相等键元素之间保持原始相对顺序。(XLinux)

3 NIST 对 quicksort、insertion sort、selection sort、bubble sort、counting sort 和 radix sort 的定义、复杂度或适用条件说明。(XLinux)

4 Oracle Java Arrays 官方文档：基本类型数组使用 Dual-Pivot Quicksort；对象数组排序稳定、自适应、迭代式归并排序并改编自 Tim Peters 的 Python list sort；parallelSort 使用并行排序-归并；实现说明不是规范本身。(Oracle 文档)

5 Oracle Java Collections.sort 官方文档：排序稳定，并委托给 List.sort；binarySearch 要求列表已按对应规则升序排序。(Oracle 文档)

6 Python 官方文档：list.sort() 原地排序，sorted() 返回新列表；二者保证稳定性；Python 排序实现使用 TimSort。(Python documentation)

7 Go 官方 sort 与 slices 文档及源码：sort.Sort、sort.Slice 不保证稳定；稳定排序需使用 Stable 系列 API；Go 1.22 起部分 sort 函数调用 slices.Sort；当前源码中有序类型排序路径使用 pdqsortOrdered，并包含插入排序和堆排序兜底。(pkg.go.dev)