排序算法大全：从基础到进阶，掌握核心排序思想

排序是算法学习的基石，也是编程面试中的高频考点。面对纷繁的排序算法，初学者往往不知从何下手。本文将以快速排序与归并排序为双核心，深度剖析其原理、性能与稳定性，并横向对比其他经典排序算法，帮你构建完整的排序知识体系。

为什么你要理解排序算法？

排序不仅是“把数据排整齐”这么简单，它背后蕴含着分治、递归、原地操作、时空权衡等重要算法思想。掌握排序，你将：

• 提升对递归与时间复杂度的理解
• 学会如何根据数据特征选择最优算法
• 为学习更复杂的数据结构与算法打下基础
• 轻松应对技术面试中的手写排序环节

以下内容将从最易理解的算法起步，逐步深入到工业级实现的核心。

基础排序算法：建立排序的直观感受

在接触高效排序之前，先看两个简单但经典的算法，它们能帮助你理解排序的基本操作——比较与交换。

冒泡排序（Bubble Sort）

冒泡排序重复走访要排序的数列，一次比较两个元素，如果顺序错误就交换它们。每一轮遍历都会让当前未排序部分的最大值“浮”到末尾。

步骤拆解：

1. 比较相邻元素，如果前一个比后一个大，则交换。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。此时最后的元素会是最大的。
3. 针对所有元素重复以上步骤，除了已经排定的最后几个。
4. 持续重复，直到没有需要交换的元素。

代码关键点（概念描述）： 双重循环，外层控制轮数，内层进行相邻比较与交换。经过优化，如果在一轮中没有发生交换，可提前终止。

复杂度：

• 时间：最坏/平均 O(n²)，最好 O(n)（已排序且带提前终止）
• 空间：O(1)，原地排序
• 稳定：是（相等元素不交换）

冒泡排序虽然简单，但性能差，几乎只用于教学。

选择排序（Selection Sort）

选择排序的核心是每次从未排序部分选择最小（或最大）元素，放到已排序序列的末尾。

算法流程：

1. 在未排序序列中找到最小元素。
2. 将其与未排序序列的起始位置元素交换。
3. 将起始位置后移一位，重复上述过程。

复杂度：

• 时间：O(n²)（所有情况）
• 空间：O(1)
• 稳定：否（交换可能破坏稳定性）

选择排序的交换次数最少（n-1次），但比较次数固定，适用于对写操作敏感的场景。

高效排序算法：分治思想的典范

接下来进入两大重点算法：快速排序和归并排序。它们都基于分治思想，但实现方式截然不同。

快速排序（Quick Sort）：平均最快的通用排序

快速排序以其平均 O(n log n) 的实际表现，成为许多编程语言内置排序的核心。它通过选取一个“枢轴”（pivot），将数组划分为左右两部分，左边元素小于等于枢轴，右边元素大于等于枢轴，然后递归排序左右子数组。

算法三步走：

1. 选择枢轴：通常选第一个、最后一个或随机元素。
2. 分区（Partition）：重排数组，使所有小于枢轴的元素放在枢轴之前，大于枢轴的放在之后。最终枢轴落在正确位置。
3. 递归：对左右分区重复上述过程。

分区操作的详解（Lomuto 方案简化版）：

• 选择最右侧元素为 pivot。
• 维护一个索引 i，指向小于 pivot 区域的最后一个位置。
• 遍历数组，当遇到元素小于 pivot 时，i 前移并交换。
• 最后将 pivot 与 i+1 位置交换，使 pivot 居中。

初始: [3,1,4,2] pivot=2
i = -1
j=0: 3>2 不操作
j=1: 1<2, i=0, 交换3和1 -> [1,3,4,2]
j=2: 4>2 不操作
最后: 交换 pivot(2) 与 i+1(元素3) -> [1,2,4,3]
pivot位置=1, 左边[1] 右边[4,3]

性能分析：

• 最好情况：每次分区平衡，递归树深度 log n，时间复杂度 O(n log n)。
• 最坏情况：数组已排序且每次选最左/右元素为枢轴，分区极度不平衡（每次只减少一个元素），时间复杂度退化到 O(n²)。随机化枢轴或使用三数取中可避免。
• 平均：O(n log n)，常数系数小。
• 空间：O(log n)（递归栈深度），可通过尾递归优化。
• 稳定性：否。分区过程中的交换可能将相等元素自身的先后顺序改变。

快速排序的变体： 三路快速排序针对大量重复元素优化，将数组分为小于、等于、大于 pivot 三部分，相等部分无需再排序。

归并排序（Merge Sort）：稳定而优雅的分治

归并排序是稳定排序的代表，它自顶向下（或自底向上）地将数组分成两半，分别排序，然后合并两个有序子数组。

核心步骤：

1. 分割：递归地将数组从中间分为左右两半，直到子数组长度为1（自然有序）。
2. 合并：合并两个有序子数组，生成一个新的更长有序数组。合并时，使用两个指针分别扫描左右半边，每次取较小的元素放入临时数组，某个半边用完后直接追加另一半。

合并操作示例：

左: [2,5,7]  右: [1,3,6]
比较 2和1 -> 取1, 右指针右移
比较 2和3 -> 取2, 左指针右移
比较 5和3 -> 取3, ...
得到 [1,2,3,5,6,7]

复杂度：

• 时间：严格 O(n log n) 所有情况。递归树深度 log n，每层合并总耗时 O(n)。
• 空间：O(n)，需要额外的临时数组用于合并，非原地排序。
• 稳定性：是。合并时若元素相等，优先取左半边的元素，保持原有相对顺序。

优化技巧：

• 对小规模子数组改用插入排序，减少递归开销。
• 检测若左半边最大值 <= 右半边最小值，则无需合并。
• 使用迭代方式自底向上归并，避免递归栈。

快速排序 vs 归并排序：选哪个？

二者同为 O(n log n)，但适用场景差异显著：

实战建议：

• 对于基本类型（如 int）排序，稳定性不重要，快排通常是首选，因其常数因子小且原地操作节省内存。
• 对于对象排序，若需保持相等元素的原始顺序，必须用稳定的归并排序。Java 的 Arrays.sort() 针对对象数组使用改进的归并排序 (TimSort)，而对基础类型使用双轴快排。
• 链表排序时，归并排序可以 O(1) 空间实现，且仍然是 O(n log n)，比快排更适合（链表随机访问慢）。

更进一步的稳定排序：插入排序与 Timsort

插入排序（Insertion Sort）

插入排序将元素逐个插入到已排序部分的正确位置，类似于打扑克牌时理牌。

算法描述： 从第二个元素开始，依次将当前元素与前面已排序元素比较，如果小于则交换或移动，直到找到合适位置。通常采用从后向前扫描并移动元素的方式实现。

性能：

• 时间：最好 O(n)（已排序），平均/最坏 O(n²)
• 空间：O(1)
• 稳定：是。

虽然插入排序复杂度高，但它对小规模数据（如 n<20）的表现极佳，常数因子极小，因此常作为高效排序（快排、归并）递归到底层时的优化手段。

Timsort：工业级混合稳定排序

Timsort 结合了归并排序与插入排序，并利用数据中已有的顺序（称为runs），是 Python 和 Java（对象数组）默认的排序算法。其核心思想：

• 扫描数组，识别自然有序的子序列（runs）。
• 如果 run 过小，用插入排序扩展至最小长度（如32或64）。
• 用类似归并的合并方式堆叠这些 runs，确保平衡。

Timsort 在部分有序数据上接近 O(n)，且稳定、自适应，是目前最优秀的全场景排序算法之一。

非比较排序：突破 O(n log n) 的限制

当数据满足特定条件时，非比较排序能在线性时间内完成。

计数排序（Counting Sort）

适用于整数且范围 k 不大的场景。统计每个值出现的次数，然后按顺序输出。

• 时间：O(n + k)
• 空间：O(k)
• 稳定：可实现（通过累加计数确定位置）
• 局限：范围大则浪费空间，仅限整数。

基数排序（Radix Sort）

按低位到高位（LSD）或高位到低位（MSD）依次对每一位进行排序。每位使用的稳定排序（通常为计数排序或桶排序）。

• 时间：O(d*(n+b))，d 为数字位数，b 为基数。
• 空间：O(n+b)
• 稳定：取决于内部算法。

桶排序（Bucket Sort）

将数据分到多个有序桶里，桶内用其他排序（如插入排序），最后按桶顺序输出。适用于均匀分布的数据，期望时间 O(n)。

排序算法选择速查表

动手实践：实现你学到的排序

理论需要代码落地。建议你按以下顺序手动实现：

1. 冒泡排序与选择排序（建立循环与比较的体感）
2. 插入排序（体会“局部插入”与稳定性）
3. 归并排序（重点练习递归分割与合并函数）
4. 快速排序（写出 Lomuto 或 Hoare 分区方案）

当你能手写这些算法并分析其时间空间复杂度时，排序思想就已经内化为你算法能力的基础模块。

总结

排序算法虽有十余种，但核心脉络清晰：从暴力到分治，从比较到非比较，从时间优化到空间优化，从稳定性到适应性。重点吃透快速排序与归并排序这对“分治双雄”，理解它们的实现细节与稳定性差异，你便掌握了排序的任督二脉。其他算法则作为特定场景的利器，按需取用。

排序之路无捷径，多写、多调试、多比较其优劣，方能融会贯通。