LeetCode-Book《图解算法数据结构》排序算法全景指南常见算法、分类方法与时空复杂度详解【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book排序是算法世界中最基础也最重要的操作之一。本文基于 LeetCode-Book 仓库中《图解算法数据结构》专栏的排序算法简介系统梳理常见排序算法的分类维度稳定性、就地性、自适应性、是否基于比较与时空复杂度总览并结合仓库内 selected_coding_interview 与 sword_for_offer 的 Python、Java、C 源码深入解读冒泡排序、快速排序、归并排序三种典型算法的实现细节与优化手段。读完本文你将掌握排序算法的完整知识地图能够根据输入数据的性质正确选型并理解排序在二分查找、双指针等高频面试题型中的前置地位。一、排序算法的应用场景为什么我们必须掌握排序排序算法用于实现列表的排序列表元素可以是整数也可以是浮点数、字符串等其他数据类型。生活与工程中有许多需要排序算法的场景典型的有整数排序对于一个整数数组我们希望将所有数字从小到大排序字符串排序对于一个姓名列表我们希望将所有单词按照字符先后排序自定义排序对于任意一个已定义比较规则的集合我们希望将其按规则排序。仓库中的实战案例印证了自定义排序的价值在 lc_179_largest_number_s1.py对应 179. 最大数中通过自定义比较规则sort_rule比较x y与y x的字典序再借助 Python 的functools.cmp_to_key完成把数组排成最小的数式排序——这正是自定义排序的经典应用。同时某些算法需要在排序算法的基础上使用即在排序数组上运行例如二分查找根据数组已排序的特性才能每轮确定排除两部分中的哪一部分。仓库中的 lc_704_binary_search.py 正是建立在有序数组这一前提之上。双指针例如合并两个排序链表根据已排序特性才能通过双指针移动在线性时间内将其合并为一个排序链表。lc_21_merge_two_sorted_lists.py 的实现即为典型以哨兵节点dum为头双指针list1、list2各指向一个有序链表每次取较小者接入结果链单次遍历即完成合并。接下来本文将从「常见排序算法」「分类方法」「时间与空间复杂度」三方面入手简要介绍排序算法。各排序算法的详细分析请见专栏后续文章7.2 冒泡排序、7.3 快速排序、7.4 归并排序。二、常见排序算法一览常见排序算法包括冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序、基数排序、桶排序。它们在不同的输入数据随机乱序、接近有序、完全倒序、少数独特下表现出不同的排序过程与性能特征。从算法思想上这八种算法可以分为几个大的流派流派算法核心思想交换类冒泡排序、快速排序通过元素交换将元素放到正确位置插入类插入排序将未排序元素逐个插入已排序区间选择类选择排序、堆排序每轮从未排序区间选出最值放到已排序区间末尾分治类归并排序、快速排序分而治之划分子问题递归求解非比较类基数排序、桶排序利用元素值的分布特性而非比较算子三、排序算法的四大分类维度排序算法主要可根据稳定性、就地性、自适应性分类此外是否基于比较也是重要的划分维度。理想的排序算法具有以下特性具有稳定性即相等元素的相对位置不变化具有就地性即不使用额外的辅助空间具有自适应性即时间复杂度受元素分布影响。特别地任意排序算法都不同时具有以上所有特性。因此排序算法的选型使用取决于具体的列表类型、元素数量、元素分布情况等应用场景特点。3.1 稳定性相等元素的相对顺序是否被改变根据相等元素在数组中的相对顺序是否被改变排序算法可分为「稳定排序」和「非稳定排序」两类稳定排序在完成排序后不改变相等元素在数组中的相对顺序。例如冒泡排序、插入排序、归并排序、基数排序、桶排序。非稳定排序在完成排序后相等元素在数组中的相对位置可能被改变。例如选择排序、快速排序、堆排序。何时需考虑排序算法的稳定性数组排序中由于元素皆为数字因此稳定和非稳定排序皆可输出相同结果此时无需考虑排序算法的稳定性。非稳定排序会改变相等元素的相对次序这在实际应用场景中可能是不能接受的。如以下代码所示非稳定排序破坏了输入列表people按姓名排序的性质# 人 (姓名, 年龄) 按姓名排序 people [ (A, 19), (B, 18), (C, 21), (D, 19), (E, 23) ] # 非稳定排序按年龄 sort_by_age(people) # 人 (姓名, 年龄) 按年龄排序 people [ (B, 18), (D, 19), # (D, 19) 和 (A, 19) 的相对位置改变输入时按姓名排序的性质丢失 (A, 19), (C, 21), (E, 23) ]在上述场景中(D, 19)与(A, 19)的原始相对次序被破坏若后续业务仍依赖姓名有序这一性质就会产生错误结果。这也是数据库、分布式系统底层排序常选用稳定排序的原因。3.2 就地性是否使用额外辅助空间根据排序过程中是否使用额外内存辅助数组排序算法可分为「原地排序」和「异地排序」两类。一般地由于不使用外部内存原地排序相比非原地排序的执行效率更高。原地排序不使用额外辅助数组例如冒泡排序、插入排序、选择排序、快速排序、堆排序。非原地排序使用额外辅助数组例如归并排序、基数排序、桶排序。3.3 自适应性时间复杂度是否受元素分布影响根据算法时间复杂度是否受待排序数组的元素分布影响排序算法可分为「自适应排序」和「非自适应排序」两类自适应排序的时间复杂度受元素分布影响。例如冒泡排序、插入排序、快速排序、桶排序。非自适应排序的时间复杂度恒定。例如选择排序、归并排序、堆排序、基数排序。3.4 是否基于比较比较类排序基于元素之间的比较算子小于、相等、大于来决定元素的相对顺序相对的非比较排序则不基于比较算子实现。基于比较排序基于元素之间的比较完成排序例如冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序。非基于比较排序不基于元素之间的比较完成排序例如基数排序、桶排序。基于比较的排序算法的平均时间复杂度最优为 $O(N \log N)$而非比较排序算法可以达到线性级别的时间复杂度。3.5 八大常见排序算法的性质汇总算法稳定原地自适应基于比较冒泡排序是是是是插入排序是是是是选择排序否是否是快速排序否是是是归并排序是否否是堆排序否是否是基数排序是否否否桶排序是否是否可以看到没有任何一种算法能同时满足稳定 原地 自适应 最优复杂度这正是排序算法的选型取决于具体场景的根本原因。四、时空复杂度总览总体上看排序算法追求时间与空间复杂度最低。而即使某些排序算法的时间复杂度相等但实际性能还受输入列表性质、元素数量、元素分布等因素影响。设输入列表元素数量为 $N$常见排序算法的「时间复杂度」和「空间复杂度」如下表所示算法最佳时间平均时间最差时间最差空间冒泡排序$\Omega(N)$$\Theta(N^2)$$O(N^2)$$O(1)$插入排序$\Omega(N)$$\Theta(N^2)$$O(N^2)$$O(1)$选择排序$\Omega(N^2)$$\Theta(N^2)$$O(N^2)$$O(1)$快速排序$\Omega(N \log N)$$\Theta(N \log N)$$O(N^2)$$O(\log N)$归并排序$\Omega(N \log N)$$\Theta(N \log N)$$O(N \log N)$$O(N)$堆排序$\Omega(N \log N)$$\Theta(N \log N)$$O(N \log N)$$O(1)$基数排序$\Omega(Nk)$$\Theta(Nk)$$O(Nk)$$O(N k)$桶排序$\Omega(N k)$$\Theta(N k)$$O(N^2)$$O(N)$对于上表需要特别注意以下几点基数排序适用于正整数、字符串、特定格式的浮点数排序$k$ 为最大数字的位数桶排序中 $k$ 为桶的数量。普通冒泡排序的最佳时间复杂度为 $O(N^2)$通过增加标志位实现提前返回可以将最佳时间复杂度降低至 $O(N)$。在输入列表完全倒序下普通快速排序的空间复杂度劣化至 $O(N)$通过尾递归优化保持算法只递归较短的子数组可以将最差递归深度降低至 $\log N$。普通快速排序总以最左或最右元素为基准数因此在输入列表有序或倒序下时间复杂度劣化至 $O(N^2)$通过随机选择基准数可极大减少此类最差情况发生尽可能地保持 $O(N \log N)$ 的时间复杂度。若输入列表是数组则归并排序的空间复杂度为 $O(N)$而若排序链表则归并排序不需要借助额外辅助空间空间复杂度可以降低至 $O(1)$。五、三种典型排序算法深度解析以下三节基于专栏后续章节7.2 冒泡排序、7.3 快速排序、7.4 归并排序展开是理解排序算法内部机制的关键。5.1 冒泡排序最直观的交换排序冒泡排序是最基础的排序算法由于其直观性经常作为首个介绍的排序算法。其原理为内循环使用相邻双指针j、j 1从左至右遍历依次比较相邻元素大小若左元素大于右元素则将它们交换遍历完成时最大元素会被交换至数组最右边。外循环不断重复「内循环」每轮将当前最大元素交换至剩余未排序数组最右边直至所有元素都被交换至正确位置时结束。首轮「内循环」后数组最大元素已被交换至数组最右边接下来只需要完成数组剩余 $N - 1$ 个元素的排序即可。同理对剩余元素反复执行「内循环」可将第二大、第三大……元素依次归位。外循环共 $N - 1$ 轮。以nums [4, 1, 3, 1, 5, 2]为例第 1 轮内循环把最大值 5 冒泡到最右第 2 轮把 4 冒泡到倒数第二……共 5 轮完成全排序。基础实现Python / Java / Cdef bubble_sort(nums): N len(nums) for i in range(N - 1): # 外循环 for j in range(N - i - 1): # 内循环 if nums[j] nums[j 1]: # 交换 nums[j], nums[j 1] nums[j], nums[j 1] nums[j 1], nums[j]void bubbleSort(int[] nums) { int N nums.length; for (int i 0; i N - 1; i) { // 外循环 for (int j 0; j N - i - 1; j) { // 内循环 if (nums[j] nums[j 1]) { // 交换 nums[j], nums[j 1] int tmp nums[j]; nums[j] nums[j 1]; nums[j 1] tmp; } } } }void bubbleSort(vectorint nums) { int N nums.size(); for (int i 0; i N - 1; i) { // 外循环 for (int j 0; j N - i - 1; j) { // 内循环 if (nums[j] nums[j 1]) { // 交换 nums[j], nums[j 1] swap(nums[j], nums[j 1]); } } } }算法特性时间复杂度 $O(N^2)$最佳 $\Omega(N)$配合标志位提前返回平均与最差均为 $O(N^2)$——外循环共 $N - 1$ 轮每轮内循环分别遍历 $N - 1, N - 2, \cdots, 2, 1$ 次平均 $\frac{N}{2}$ 次总体为 $O(N^2)$。空间复杂度 $O(1)$只需原地交换元素使用常数大小的额外空间。冒泡排序通过不断交换元素实现排序交换 2 个元素需要 3 次赋值操作因此速度较慢。原地指针变量仅使用常数大小额外空间。稳定元素值相同时不交换因此不会改变相同元素的相对位置。自适应通过增加标志位flag实现提前返回。标志位优化普通冒泡排序的时间复杂度恒为 $O(N^2)$与输入数组的元素分布无关。通过增加一个标志位flag若某轮内循环中未执行任何交换操作则说明数组已经完成排序直接返回结果即可。优化后最差和平均时间复杂度仍为 $O(N^2)$在输入数组已排序时达到最佳时间复杂度 $\Omega(N)$。def bubble_sort(nums): N len(nums) for i in range(N - 1): flag False # 初始化标志位 for j in range(N - i - 1): if nums[j] nums[j 1]: nums[j], nums[j 1] nums[j 1], nums[j] flag True # 记录交换元素 if not flag: break # 内循环未交换任何元素则跳出5.2 快速排序基于哨兵划分的高效分治快速排序算法有两个核心点分别为哨兵划分和递归。哨兵划分以数组某个元素一般选取首元素为基准数将所有小于基准数的元素移动至其左边大于基准数的元素移动至其右边。经过一轮哨兵划分可将数组排序问题拆分为两个较短数组的排序问题左/右子数组。递归对左子数组和右子数组分别递归执行哨兵划分直至子数组长度为 1 时终止递归即可完成对整个数组的排序。快速排序和二分法的原理类似都是以 $\log$ 时间复杂度实现搜索区间缩小。哨兵划分的核心技巧是双指针相向移动指针j从右向左找第一个小于基准数的元素指针i从左向右找第一个大于基准数的元素交换两者重复直至i j最后将基准数交换到i处并返回i。基础实现Python / Java / Cdef quick_sort(nums, l, r): # 子数组长度为 1 时终止递归 if l r: return # 哨兵划分操作 i partition(nums, l, r) # 递归左右子数组执行哨兵划分 quick_sort(nums, l, i - 1) quick_sort(nums, i 1, r) def partition(nums, l, r): # 以 nums[l] 作为基准数 i, j l, r while i j: while i j and nums[j] nums[l]: j - 1 while i j and nums[i] nums[l]: i 1 nums[i], nums[j] nums[j], nums[i] nums[l], nums[i] nums[i], nums[l] return i # 调用 nums [3, 4, 1, 5, 2] quick_sort(nums, 0, len(nums) - 1)int partition(vectorint nums, int l, int r) { // 以 nums[l] 作为基准数 int i l, j r; while (i j) { while (i j nums[j] nums[l]) j--; while (i j nums[i] nums[l]) i; swap(nums[i], nums[j]); } swap(nums[i], nums[l]); return i; } void quickSort(vectorint nums, int l, int r) { // 子数组长度为 1 时终止递归 if (l r) return; // 哨兵划分操作 int i partition(nums, l, r); // 递归左右子数组执行哨兵划分 quickSort(nums, l, i - 1); quickSort(nums, i 1, r); }算法特性时间复杂度最佳 $\Omega(N \log N)$每轮哨兵划分将数组划分为等长度的两个子数组划分操作线性 $O(N)$递归轮数 $O(\log N)$平均 $\Theta(N \log N)$最差 $O(N^2)$每轮划分出长度 1 与 $N - 1$ 的两个子数组递归轮数达 $N$。空间复杂度 $O(N)$递归深度最好与平均皆为 $\log N$输入数组完全倒序下达到最差递归深度 $N$。通过尾递归优化可将最差空间复杂度降低至 $O(\log N)$。虽然平均时间复杂度与归并排序和堆排序一致但在实际使用中快速排序效率更高原因在于最差情况稀疏性统计意义下 $O(N^2)$ 出现概率很低、缓存使用效率高哨兵划分时整个子数组被加载入缓存而堆排序需要跳跃式访问元素、常数系数低比较、赋值、交换三种操作的综合耗时最低。原地不用借助辅助数组的额外空间递归仅使用 $O(\log N)$ 大小的栈帧空间。非稳定哨兵划分操作可能改变相等元素的相对顺序。自适应对于极少输入数据时间复杂度可能劣化至 $O(N^2)$。算法优化一尾递归。由于普通快速排序每轮选取「子数组最左元素」作为「基准数」在输入数组完全倒序时递归深度会达到 $N$。每轮递归时仅对较短的子数组执行哨兵划分就可将最差的递归深度控制在 $O(\log N)$每轮递归的子数组长度都 $\le$ 当前数组长度 $/ 2$def quick_sort(nums, l, r): # 子数组长度为 1 时终止递归 while l r: # 哨兵划分操作 i partition(nums, l, r) # 仅递归至较短子数组控制递归深度 if i - l r - i: quick_sort(nums, l, i - 1) l i 1 else: quick_sort(nums, i 1, r) r i - 1算法优化二随机基准数。在输入数组完全有序或完全倒序时partition()每轮只划分一个元素达到最差时间复杂度 $O(N^2)$。可使用随机函数每轮在子数组中随机选择一个元素作为基准数从而极大概率避免劣化情况最差时间复杂度理论上仍为 $O(N^2)$def partition(nums, l, r): # 在闭区间 [l, r] 随机选取任意索引并与 nums[l] 交换 ra random.randrange(l, r 1) nums[l], nums[ra] nums[ra], nums[l] # 以 nums[l] 作为基准数 i, j l, r while i j: while i j and nums[j] nums[l]: j - 1 while i j and nums[i] nums[l]: i 1 nums[i], nums[j] nums[j], nums[i] nums[l], nums[i] nums[i], nums[l] return i仓库源码印证了快速排序在真实题目中的应用lc_215_kth_largest_element_in_an_array_s1.py对应 215. 数组中的第K个最大元素完整内嵌了上述quick_sort与哨兵划分partition实现先对数组全量排序后直接返回nums[-k]。可见专栏的排序算法讲解直接服务于仓库中的高频笔面试题。5.3 归并排序稳定且确定的分治排序归并排序体现了分而治之的算法思想具体为「分」不断将数组从中点位置划分开将原数组的排序问题转化为子数组的排序问题「治」划分到子数组长度为 1 时开始向上合并不断将左右两个较短排序数组合并为一个较长排序数组直至合并至原数组时完成排序。算法流程递归划分计算数组中点 $m$递归划分左子数组merge_sort(l, m)和右子数组merge_sort(m 1, r)当 $l \ge r$ 时代表子数组长度为 1 或 0此时终止划分开始合并。合并子数组暂存数组 $nums$ 闭区间 $[l, r]$ 内的元素至辅助数组 $tmp$设置双指针 $i$、$j$ 分别指向 $tmp$ 的左/右子数组的首元素循环合并当 $i m - l 1$ 时左子数组已合并完添加右子数组元素 $tmp[j]$执行 $j j 1$否则当 $j r - l 1$ 时右子数组已合并完添加左子数组元素 $tmp[i]$执行 $i i 1$否则当 $tmp[i] \le tmp[j]$ 时添加左子数组元素 $tmp[i]$执行 $i i 1$否则即 $tmp[i] tmp[j]$ 时添加右子数组元素 $tmp[j]$执行 $j j 1$。注意$nums$ 子数组的左边界、中点、右边界分别为 $l$、$m$、$r$而辅助数组 $tmp$ 中的对应索引为 $0$、$m - l$、$r - l$。代码实现为简化代码「当 $j r 1$ 时」与「当 $tmp[i] \le tmp[j]$ 时」两判断项可合并def merge_sort(nums, l, r): # 终止条件 if l r: return # 递归划分数组 m (l r) // 2 merge_sort(nums, l, m) merge_sort(nums, m 1, r) # 合并子数组 tmp nums[l:r 1] # 暂存需合并区间元素 i, j 0, m - l 1 # 两指针分别指向左/右子数组的首个元素 for k in range(l, r 1): # 遍历合并左/右子数组 if i m - l 1: nums[k] tmp[j] j 1 elif j r - l 1 or tmp[i] tmp[j]: nums[k] tmp[i] i 1 else: nums[k] tmp[j] j 1void mergeSort(vectorint nums, int l, int r) { // 终止条件 if (l r) return; // 递归划分 int m (l r) / 2; mergeSort(nums, l, m); mergeSort(nums, m 1, r); // 合并阶段 int tmp[r - l 1]; // 暂存需合并区间元素 for (int k l; k r; k) tmp[k - l] nums[k]; int i 0, j m - l 1; // 两指针分别指向左/右子数组的首个元素 for (int k l; k r; k) { // 遍历合并左/右子数组 if (i m - l 1) nums[k] tmp[j]; else if (j r - l 1 || tmp[i] tmp[j]) nums[k] tmp[i]; else { nums[k] tmp[j]; } } }算法特性时间复杂度最佳 $\Omega(N \log N)$平均 $\Theta(N \log N)$最差 $O(N \log N)$——任何输入数据下表现一致。空间复杂度 $O(N)$合并过程需要借助辅助数组 $tmp$划分的递归深度为 $\log N$使用 $O(\log N)$ 大小的栈帧空间。链表特例若输入数据是链表归并排序的空间复杂度可被优化至 $O(1)$。原因有二通过「双指针法」可在 $O(1)$ 空间下完成两个排序链表的合并省去辅助数组 $tmp$通过「迭代」代替「递归划分」可省去递归使用的栈帧空间。这一思想正是 21. 合并两个有序链表 与排序链表类题目的核心。非原地辅助数组 $tmp$ 需要使用额外空间。稳定归并排序不改变相等元素的相对顺序。非自适应对于任意输入数据归并排序的时间复杂度皆相同。六、仓库中的排序实践从理论到题解LeetCode-Book 仓库将上述排序理论直接落地为可运行的题解代码形成专栏讲解 → 源码实现 → 测试用例的完整闭环快速排序的实战应用lc_215_kth_largest_element_in_an_array_s1.py 内嵌哨兵划分与递归实现先排序后取第 $k$ 大元素Java 版本见 lc_215_kth_largest_element_in_an_array、C 版本见 lc_215_kth_largest_element_in_an_array。自定义排序的实战应用lc_179_largest_number_s1.py 通过cmp_to_key自定义比较规则完成最大数拼接对应 179. 最大数。双指针合并有序链表lc_21_merge_two_sorted_lists.py 演示了已排序性质 双指针的线性时间合并正是排序前置价值的直接体现。排序数组上的二分/双指针仓库中大量题目以有序数组为前提例如 704. 二分查找、167. 两数之和 II、15. 三数之和均依赖输入已排序这一性质来缩小搜索范围或移动指针。各题解的 Python、Java、C 实现均位于codes目录对应子目录中并附有测试用例与驱动代码可直接运行验证。七、选型建议如何根据场景选择合适的排序算法结合前文的分类维度与复杂度总览可以给出以下选型原则输入规模小$N$ 较小冒泡排序、插入排序、选择排序实现简单常数系数低适合小规模数据其中插入排序对接近有序的数据表现优异。大规模通用排序优先考虑快速排序常数系数低、缓存友好实际工程中这也是使用最广泛的选择。要求最差时间可控归并排序与堆排序的最差时间复杂度均为 $O(N \log N)$适合对最坏情况敏感的场景若还需稳定则选归并排序。要求稳定在相等元素相对次序有业务意义的场景如多关键字排序应选择冒泡、插入、归并等稳定排序。要求原地内存受限排除归并、基数、桶排序选择快速排序或堆排序。数据分布可利用如数值范围有限基数排序、桶排序可达到线性时间复杂度但受限于元素类型与分布。需要强调的是任何排序算法都不同时具有稳定、就地、自适应等全部特性选型本质上是在时间、空间、稳定性、实现复杂度之间做权衡具体取决于列表类型、元素数量与元素分布。八、小结本文围绕《图解算法数据结构》的排序算法简介展开梳理了排序的四大分类维度稳定性、就地性、自适应性、是否基于比较、八大常见算法的时空复杂度总览并结合仓库源码深入解析了冒泡排序含标志位优化、快速排序含尾递归与随机基准数优化、归并排序含链表 $O(1)$ 空间特例三种核心算法。后续专栏文章对每种算法还有更详细的图文讲解冒泡排序、快速排序、归并排序而仓库 leetbook_ioa、selected_coding_interview 与 sword_for_offer 中的题解代码则为理论提供了可直接运行、可对照验证的完整实践闭环。掌握排序算法是通往二分查找、双指针、分治等进阶算法的基础也是高效刷题的第一步。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Book《图解算法数据结构》排序算法全景指南常见算法、分类方法与时空复杂度详解【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book排序是算法世界中最基础也最重要的操作之一。本文基于 LeetCode-Book 仓库中《图解算法数据结构》专栏的排序算法简介系统梳理常见排序算法的分类维度稳定性、就地性、自适应性、是否基于比较与时空复杂度总览并结合仓库内 selected_coding_interview 与 sword_for_offer 的 Python、Java、C 源码深入解读冒泡排序、快速排序、归并排序三种典型算法的实现细节与优化手段。读完本文你将掌握排序算法的完整知识地图能够根据输入数据的性质正确选型并理解排序在二分查找、双指针等高频面试题型中的前置地位。一、排序算法的应用场景为什么我们必须掌握排序排序算法用于实现列表的排序列表元素可以是整数也可以是浮点数、字符串等其他数据类型。生活与工程中有许多需要排序算法的场景典型的有整数排序对于一个整数数组我们希望将所有数字从小到大排序字符串排序对于一个姓名列表我们希望将所有单词按照字符先后排序自定义排序对于任意一个已定义比较规则的集合我们希望将其按规则排序。仓库中的实战案例印证了自定义排序的价值在 lc_179_largest_number_s1.py对应 179. 最大数中通过自定义比较规则sort_rule比较x y与y x的字典序再借助 Python 的functools.cmp_to_key完成把数组排成最小的数式排序——这正是自定义排序的经典应用。同时某些算法需要在排序算法的基础上使用即在排序数组上运行例如二分查找根据数组已排序的特性才能每轮确定排除两部分中的哪一部分。仓库中的 lc_704_binary_search.py 正是建立在有序数组这一前提之上。双指针例如合并两个排序链表根据已排序特性才能通过双指针移动在线性时间内将其合并为一个排序链表。lc_21_merge_two_sorted_lists.py 的实现即为典型以哨兵节点dum为头双指针list1、list2各指向一个有序链表每次取较小者接入结果链单次遍历即完成合并。接下来本文将从「常见排序算法」「分类方法」「时间与空间复杂度」三方面入手简要介绍排序算法。各排序算法的详细分析请见专栏后续文章7.2 冒泡排序、7.3 快速排序、7.4 归并排序。二、常见排序算法一览常见排序算法包括冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序、基数排序、桶排序。它们在不同的输入数据随机乱序、接近有序、完全倒序、少数独特下表现出不同的排序过程与性能特征。从算法思想上这八种算法可以分为几个大的流派流派算法核心思想交换类冒泡排序、快速排序通过元素交换将元素放到正确位置插入类插入排序将未排序元素逐个插入已排序区间选择类选择排序、堆排序每轮从未排序区间选出最值放到已排序区间末尾分治类归并排序、快速排序分而治之划分子问题递归求解非比较类基数排序、桶排序利用元素值的分布特性而非比较算子三、排序算法的四大分类维度排序算法主要可根据稳定性、就地性、自适应性分类此外是否基于比较也是重要的划分维度。理想的排序算法具有以下特性具有稳定性即相等元素的相对位置不变化具有就地性即不使用额外的辅助空间具有自适应性即时间复杂度受元素分布影响。特别地任意排序算法都不同时具有以上所有特性。因此排序算法的选型使用取决于具体的列表类型、元素数量、元素分布情况等应用场景特点。3.1 稳定性相等元素的相对顺序是否被改变根据相等元素在数组中的相对顺序是否被改变排序算法可分为「稳定排序」和「非稳定排序」两类稳定排序在完成排序后不改变相等元素在数组中的相对顺序。例如冒泡排序、插入排序、归并排序、基数排序、桶排序。非稳定排序在完成排序后相等元素在数组中的相对位置可能被改变。例如选择排序、快速排序、堆排序。何时需考虑排序算法的稳定性数组排序中由于元素皆为数字因此稳定和非稳定排序皆可输出相同结果此时无需考虑排序算法的稳定性。非稳定排序会改变相等元素的相对次序这在实际应用场景中可能是不能接受的。如以下代码所示非稳定排序破坏了输入列表people按姓名排序的性质# 人 (姓名, 年龄) 按姓名排序 people [ (A, 19), (B, 18), (C, 21), (D, 19), (E, 23) ] # 非稳定排序按年龄 sort_by_age(people) # 人 (姓名, 年龄) 按年龄排序 people [ (B, 18), (D, 19), # (D, 19) 和 (A, 19) 的相对位置改变输入时按姓名排序的性质丢失 (A, 19), (C, 21), (E, 23) ]在上述场景中(D, 19)与(A, 19)的原始相对次序被破坏若后续业务仍依赖姓名有序这一性质就会产生错误结果。这也是数据库、分布式系统底层排序常选用稳定排序的原因。3.2 就地性是否使用额外辅助空间根据排序过程中是否使用额外内存辅助数组排序算法可分为「原地排序」和「异地排序」两类。一般地由于不使用外部内存原地排序相比非原地排序的执行效率更高。原地排序不使用额外辅助数组例如冒泡排序、插入排序、选择排序、快速排序、堆排序。非原地排序使用额外辅助数组例如归并排序、基数排序、桶排序。3.3 自适应性时间复杂度是否受元素分布影响根据算法时间复杂度是否受待排序数组的元素分布影响排序算法可分为「自适应排序」和「非自适应排序」两类自适应排序的时间复杂度受元素分布影响。例如冒泡排序、插入排序、快速排序、桶排序。非自适应排序的时间复杂度恒定。例如选择排序、归并排序、堆排序、基数排序。3.4 是否基于比较比较类排序基于元素之间的比较算子小于、相等、大于来决定元素的相对顺序相对的非比较排序则不基于比较算子实现。基于比较排序基于元素之间的比较完成排序例如冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序。非基于比较排序不基于元素之间的比较完成排序例如基数排序、桶排序。基于比较的排序算法的平均时间复杂度最优为 $O(N \log N)$而非比较排序算法可以达到线性级别的时间复杂度。3.5 八大常见排序算法的性质汇总算法稳定原地自适应基于比较冒泡排序是是是是插入排序是是是是选择排序否是否是快速排序否是是是归并排序是否否是堆排序否是否是基数排序是否否否桶排序是否是否可以看到没有任何一种算法能同时满足稳定 原地 自适应 最优复杂度这正是排序算法的选型取决于具体场景的根本原因。四、时空复杂度总览总体上看排序算法追求时间与空间复杂度最低。而即使某些排序算法的时间复杂度相等但实际性能还受输入列表性质、元素数量、元素分布等因素影响。设输入列表元素数量为 $N$常见排序算法的「时间复杂度」和「空间复杂度」如下表所示算法最佳时间平均时间最差时间最差空间冒泡排序$\Omega(N)$$\Theta(N^2)$$O(N^2)$$O(1)$插入排序$\Omega(N)$$\Theta(N^2)$$O(N^2)$$O(1)$选择排序$\Omega(N^2)$$\Theta(N^2)$$O(N^2)$$O(1)$快速排序$\Omega(N \log N)$$\Theta(N \log N)$$O(N^2)$$O(\log N)$归并排序$\Omega(N \log N)$$\Theta(N \log N)$$O(N \log N)$$O(N)$堆排序$\Omega(N \log N)$$\Theta(N \log N)$$O(N \log N)$$O(1)$基数排序$\Omega(Nk)$$\Theta(Nk)$$O(Nk)$$O(N k)$桶排序$\Omega(N k)$$\Theta(N k)$$O(N^2)$$O(N)$对于上表需要特别注意以下几点基数排序适用于正整数、字符串、特定格式的浮点数排序$k$ 为最大数字的位数桶排序中 $k$ 为桶的数量。普通冒泡排序的最佳时间复杂度为 $O(N^2)$通过增加标志位实现提前返回可以将最佳时间复杂度降低至 $O(N)$。在输入列表完全倒序下普通快速排序的空间复杂度劣化至 $O(N)$通过尾递归优化保持算法只递归较短的子数组可以将最差递归深度降低至 $\log N$。普通快速排序总以最左或最右元素为基准数因此在输入列表有序或倒序下时间复杂度劣化至 $O(N^2)$通过随机选择基准数可极大减少此类最差情况发生尽可能地保持 $O(N \log N)$ 的时间复杂度。若输入列表是数组则归并排序的空间复杂度为 $O(N)$而若排序链表则归并排序不需要借助额外辅助空间空间复杂度可以降低至 $O(1)$。五、三种典型排序算法深度解析以下三节基于专栏后续章节7.2 冒泡排序、7.3 快速排序、7.4 归并排序展开是理解排序算法内部机制的关键。5.1 冒泡排序最直观的交换排序冒泡排序是最基础的排序算法由于其直观性经常作为首个介绍的排序算法。其原理为内循环使用相邻双指针j、j 1从左至右遍历依次比较相邻元素大小若左元素大于右元素则将它们交换遍历完成时最大元素会被交换至数组最右边。外循环不断重复「内循环」每轮将当前最大元素交换至剩余未排序数组最右边直至所有元素都被交换至正确位置时结束。首轮「内循环」后数组最大元素已被交换至数组最右边接下来只需要完成数组剩余 $N - 1$ 个元素的排序即可。同理对剩余元素反复执行「内循环」可将第二大、第三大……元素依次归位。外循环共 $N - 1$ 轮。以nums [4, 1, 3, 1, 5, 2]为例第 1 轮内循环把最大值 5 冒泡到最右第 2 轮把 4 冒泡到倒数第二……共 5 轮完成全排序。基础实现Python / Java / Cdef bubble_sort(nums): N len(nums) for i in range(N - 1): # 外循环 for j in range(N - i - 1): # 内循环 if nums[j] nums[j 1]: # 交换 nums[j], nums[j 1] nums[j], nums[j 1] nums[j 1], nums[j]void bubbleSort(int[] nums) { int N nums.length; for (int i 0; i N - 1; i) { // 外循环 for (int j 0; j N - i - 1; j) { // 内循环 if (nums[j] nums[j 1]) { // 交换 nums[j], nums[j 1] int tmp nums[j]; nums[j] nums[j 1]; nums[j 1] tmp; } } } }void bubbleSort(vectorint nums) { int N nums.size(); for (int i 0; i N - 1; i) { // 外循环 for (int j 0; j N - i - 1; j) { // 内循环 if (nums[j] nums[j 1]) { // 交换 nums[j], nums[j 1] swap(nums[j], nums[j 1]); } } } }算法特性时间复杂度 $O(N^2)$最佳 $\Omega(N)$配合标志位提前返回平均与最差均为 $O(N^2)$——外循环共 $N - 1$ 轮每轮内循环分别遍历 $N - 1, N - 2, \cdots, 2, 1$ 次平均 $\frac{N}{2}$ 次总体为 $O(N^2)$。空间复杂度 $O(1)$只需原地交换元素使用常数大小的额外空间。冒泡排序通过不断交换元素实现排序交换 2 个元素需要 3 次赋值操作因此速度较慢。原地指针变量仅使用常数大小额外空间。稳定元素值相同时不交换因此不会改变相同元素的相对位置。自适应通过增加标志位flag实现提前返回。标志位优化普通冒泡排序的时间复杂度恒为 $O(N^2)$与输入数组的元素分布无关。通过增加一个标志位flag若某轮内循环中未执行任何交换操作则说明数组已经完成排序直接返回结果即可。优化后最差和平均时间复杂度仍为 $O(N^2)$在输入数组已排序时达到最佳时间复杂度 $\Omega(N)$。def bubble_sort(nums): N len(nums) for i in range(N - 1): flag False # 初始化标志位 for j in range(N - i - 1): if nums[j] nums[j 1]: nums[j], nums[j 1] nums[j 1], nums[j] flag True # 记录交换元素 if not flag: break # 内循环未交换任何元素则跳出5.2 快速排序基于哨兵划分的高效分治快速排序算法有两个核心点分别为哨兵划分和递归。哨兵划分以数组某个元素一般选取首元素为基准数将所有小于基准数的元素移动至其左边大于基准数的元素移动至其右边。经过一轮哨兵划分可将数组排序问题拆分为两个较短数组的排序问题左/右子数组。递归对左子数组和右子数组分别递归执行哨兵划分直至子数组长度为 1 时终止递归即可完成对整个数组的排序。快速排序和二分法的原理类似都是以 $\log$ 时间复杂度实现搜索区间缩小。哨兵划分的核心技巧是双指针相向移动指针j从右向左找第一个小于基准数的元素指针i从左向右找第一个大于基准数的元素交换两者重复直至i j最后将基准数交换到i处并返回i。基础实现Python / Java / Cdef quick_sort(nums, l, r): # 子数组长度为 1 时终止递归 if l r: return # 哨兵划分操作 i partition(nums, l, r) # 递归左右子数组执行哨兵划分 quick_sort(nums, l, i - 1) quick_sort(nums, i 1, r) def partition(nums, l, r): # 以 nums[l] 作为基准数 i, j l, r while i j: while i j and nums[j] nums[l]: j - 1 while i j and nums[i] nums[l]: i 1 nums[i], nums[j] nums[j], nums[i] nums[l], nums[i] nums[i], nums[l] return i # 调用 nums [3, 4, 1, 5, 2] quick_sort(nums, 0, len(nums) - 1)int partition(vectorint nums, int l, int r) { // 以 nums[l] 作为基准数 int i l, j r; while (i j) { while (i j nums[j] nums[l]) j--; while (i j nums[i] nums[l]) i; swap(nums[i], nums[j]); } swap(nums[i], nums[l]); return i; } void quickSort(vectorint nums, int l, int r) { // 子数组长度为 1 时终止递归 if (l r) return; // 哨兵划分操作 int i partition(nums, l, r); // 递归左右子数组执行哨兵划分 quickSort(nums, l, i - 1); quickSort(nums, i 1, r); }算法特性时间复杂度最佳 $\Omega(N \log N)$每轮哨兵划分将数组划分为等长度的两个子数组划分操作线性 $O(N)$递归轮数 $O(\log N)$平均 $\Theta(N \log N)$最差 $O(N^2)$每轮划分出长度 1 与 $N - 1$ 的两个子数组递归轮数达 $N$。空间复杂度 $O(N)$递归深度最好与平均皆为 $\log N$输入数组完全倒序下达到最差递归深度 $N$。通过尾递归优化可将最差空间复杂度降低至 $O(\log N)$。虽然平均时间复杂度与归并排序和堆排序一致但在实际使用中快速排序效率更高原因在于最差情况稀疏性统计意义下 $O(N^2)$ 出现概率很低、缓存使用效率高哨兵划分时整个子数组被加载入缓存而堆排序需要跳跃式访问元素、常数系数低比较、赋值、交换三种操作的综合耗时最低。原地不用借助辅助数组的额外空间递归仅使用 $O(\log N)$ 大小的栈帧空间。非稳定哨兵划分操作可能改变相等元素的相对顺序。自适应对于极少输入数据时间复杂度可能劣化至 $O(N^2)$。算法优化一尾递归。由于普通快速排序每轮选取「子数组最左元素」作为「基准数」在输入数组完全倒序时递归深度会达到 $N$。每轮递归时仅对较短的子数组执行哨兵划分就可将最差的递归深度控制在 $O(\log N)$每轮递归的子数组长度都 $\le$ 当前数组长度 $/ 2$def quick_sort(nums, l, r): # 子数组长度为 1 时终止递归 while l r: # 哨兵划分操作 i partition(nums, l, r) # 仅递归至较短子数组控制递归深度 if i - l r - i: quick_sort(nums, l, i - 1) l i 1 else: quick_sort(nums, i 1, r) r i - 1算法优化二随机基准数。在输入数组完全有序或完全倒序时partition()每轮只划分一个元素达到最差时间复杂度 $O(N^2)$。可使用随机函数每轮在子数组中随机选择一个元素作为基准数从而极大概率避免劣化情况最差时间复杂度理论上仍为 $O(N^2)$def partition(nums, l, r): # 在闭区间 [l, r] 随机选取任意索引并与 nums[l] 交换 ra random.randrange(l, r 1) nums[l], nums[ra] nums[ra], nums[l] # 以 nums[l] 作为基准数 i, j l, r while i j: while i j and nums[j] nums[l]: j - 1 while i j and nums[i] nums[l]: i 1 nums[i], nums[j] nums[j], nums[i] nums[l], nums[i] nums[i], nums[l] return i仓库源码印证了快速排序在真实题目中的应用lc_215_kth_largest_element_in_an_array_s1.py对应 215. 数组中的第K个最大元素完整内嵌了上述quick_sort与哨兵划分partition实现先对数组全量排序后直接返回nums[-k]。可见专栏的排序算法讲解直接服务于仓库中的高频笔面试题。5.3 归并排序稳定且确定的分治排序归并排序体现了分而治之的算法思想具体为「分」不断将数组从中点位置划分开将原数组的排序问题转化为子数组的排序问题「治」划分到子数组长度为 1 时开始向上合并不断将左右两个较短排序数组合并为一个较长排序数组直至合并至原数组时完成排序。算法流程递归划分计算数组中点 $m$递归划分左子数组merge_sort(l, m)和右子数组merge_sort(m 1, r)当 $l \ge r$ 时代表子数组长度为 1 或 0此时终止划分开始合并。合并子数组暂存数组 $nums$ 闭区间 $[l, r]$ 内的元素至辅助数组 $tmp$设置双指针 $i$、$j$ 分别指向 $tmp$ 的左/右子数组的首元素循环合并当 $i m - l 1$ 时左子数组已合并完添加右子数组元素 $tmp[j]$执行 $j j 1$否则当 $j r - l 1$ 时右子数组已合并完添加左子数组元素 $tmp[i]$执行 $i i 1$否则当 $tmp[i] \le tmp[j]$ 时添加左子数组元素 $tmp[i]$执行 $i i 1$否则即 $tmp[i] tmp[j]$ 时添加右子数组元素 $tmp[j]$执行 $j j 1$。注意$nums$ 子数组的左边界、中点、右边界分别为 $l$、$m$、$r$而辅助数组 $tmp$ 中的对应索引为 $0$、$m - l$、$r - l$。代码实现为简化代码「当 $j r 1$ 时」与「当 $tmp[i] \le tmp[j]$ 时」两判断项可合并def merge_sort(nums, l, r): # 终止条件 if l r: return # 递归划分数组 m (l r) // 2 merge_sort(nums, l, m) merge_sort(nums, m 1, r) # 合并子数组 tmp nums[l:r 1] # 暂存需合并区间元素 i, j 0, m - l 1 # 两指针分别指向左/右子数组的首个元素 for k in range(l, r 1): # 遍历合并左/右子数组 if i m - l 1: nums[k] tmp[j] j 1 elif j r - l 1 or tmp[i] tmp[j]: nums[k] tmp[i] i 1 else: nums[k] tmp[j] j 1void mergeSort(vectorint nums, int l, int r) { // 终止条件 if (l r) return; // 递归划分 int m (l r) / 2; mergeSort(nums, l, m); mergeSort(nums, m 1, r); // 合并阶段 int tmp[r - l 1]; // 暂存需合并区间元素 for (int k l; k r; k) tmp[k - l] nums[k]; int i 0, j m - l 1; // 两指针分别指向左/右子数组的首个元素 for (int k l; k r; k) { // 遍历合并左/右子数组 if (i m - l 1) nums[k] tmp[j]; else if (j r - l 1 || tmp[i] tmp[j]) nums[k] tmp[i]; else { nums[k] tmp[j]; } } }算法特性时间复杂度最佳 $\Omega(N \log N)$平均 $\Theta(N \log N)$最差 $O(N \log N)$——任何输入数据下表现一致。空间复杂度 $O(N)$合并过程需要借助辅助数组 $tmp$划分的递归深度为 $\log N$使用 $O(\log N)$ 大小的栈帧空间。链表特例若输入数据是链表归并排序的空间复杂度可被优化至 $O(1)$。原因有二通过「双指针法」可在 $O(1)$ 空间下完成两个排序链表的合并省去辅助数组 $tmp$通过「迭代」代替「递归划分」可省去递归使用的栈帧空间。这一思想正是 21. 合并两个有序链表 与排序链表类题目的核心。非原地辅助数组 $tmp$ 需要使用额外空间。稳定归并排序不改变相等元素的相对顺序。非自适应对于任意输入数据归并排序的时间复杂度皆相同。六、仓库中的排序实践从理论到题解LeetCode-Book 仓库将上述排序理论直接落地为可运行的题解代码形成专栏讲解 → 源码实现 → 测试用例的完整闭环快速排序的实战应用lc_215_kth_largest_element_in_an_array_s1.py 内嵌哨兵划分与递归实现先排序后取第 $k$ 大元素Java 版本见 lc_215_kth_largest_element_in_an_array、C 版本见 lc_215_kth_largest_element_in_an_array。自定义排序的实战应用lc_179_largest_number_s1.py 通过cmp_to_key自定义比较规则完成最大数拼接对应 179. 最大数。双指针合并有序链表lc_21_merge_two_sorted_lists.py 演示了已排序性质 双指针的线性时间合并正是排序前置价值的直接体现。排序数组上的二分/双指针仓库中大量题目以有序数组为前提例如 704. 二分查找、167. 两数之和 II、15. 三数之和均依赖输入已排序这一性质来缩小搜索范围或移动指针。各题解的 Python、Java、C 实现均位于codes目录对应子目录中并附有测试用例与驱动代码可直接运行验证。七、选型建议如何根据场景选择合适的排序算法结合前文的分类维度与复杂度总览可以给出以下选型原则输入规模小$N$ 较小冒泡排序、插入排序、选择排序实现简单常数系数低适合小规模数据其中插入排序对接近有序的数据表现优异。大规模通用排序优先考虑快速排序常数系数低、缓存友好实际工程中这也是使用最广泛的选择。要求最差时间可控归并排序与堆排序的最差时间复杂度均为 $O(N \log N)$适合对最坏情况敏感的场景若还需稳定则选归并排序。要求稳定在相等元素相对次序有业务意义的场景如多关键字排序应选择冒泡、插入、归并等稳定排序。要求原地内存受限排除归并、基数、桶排序选择快速排序或堆排序。数据分布可利用如数值范围有限基数排序、桶排序可达到线性时间复杂度但受限于元素类型与分布。需要强调的是任何排序算法都不同时具有稳定、就地、自适应等全部特性选型本质上是在时间、空间、稳定性、实现复杂度之间做权衡具体取决于列表类型、元素数量与元素分布。八、小结本文围绕《图解算法数据结构》的排序算法简介展开梳理了排序的四大分类维度稳定性、就地性、自适应性、是否基于比较、八大常见算法的时空复杂度总览并结合仓库源码深入解析了冒泡排序含标志位优化、快速排序含尾递归与随机基准数优化、归并排序含链表 $O(1)$ 空间特例三种核心算法。后续专栏文章对每种算法还有更详细的图文讲解冒泡排序、快速排序、归并排序而仓库 leetbook_ioa、selected_coding_interview 与 sword_for_offer 中的题解代码则为理论提供了可直接运行、可对照验证的完整实践闭环。掌握排序算法是通往二分查找、双指针、分治等进阶算法的基础也是高效刷题的第一步。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
