排序算法详解：十大排序原理、复杂度与选型指南

排序大概是程序员最早接触、也最容易被低估的一类算法。业务系统里按时间、按价格、按权重排序到处都是面试考场上手写快排、堆排几乎成了基本动作不少同学把十大排序算法的代码背得滚瓜烂熟可一旦被追问计数排序为什么能突破O(n log n)上限或快排最坏情况为什么退化就卡壳了。这篇文章打算把十个排序算法一次性串透——快排、希尔、堆排、归并、冒泡、桶排、选择、插入、计数、基数从实现机制、复杂度推导到工程选型把代码背后的为什么补齐。适合刚接触算法的同学也适合准备面试、要在真实项目里做排序选型的人。1. 排序算法为什么值得死磕从业务排序列到面试必答的思维模型1.1 排序是理解算法复杂度的最佳样本排序虽然看起来基础但它几乎把算法设计里的核心思想都集合齐了分治、递归、堆结构、哈希映射、计数统计、稳定性分析、时间复杂度推导。这也是为什么所有算法教材都拿排序开篇它不是简单的把数组排好而是理解一个算法为什么快、为什么慢、快在什么数据上的最佳训练场。很多教材都提到过一个结论基于比较的排序时间复杂度下界是O(n log n)。这个结论的证明思路不难n个元素的全排列一共n!种排序过程本质上是在消除排列的不确定性。每一次比较最多把可能结果分成两半那么最少需要的比较次数就是log2(n!)。用斯特林公式展开log2(n!)等价于n log n。所以冒泡、插入、选择哪怕再优化也冲不出这个天花板快排、堆排、归并能做到O(n log n)已经逼近理论下界。桶排、计数、基数这三个算法之所以能跑到线性复杂度正是因为它们跳出了比较这条路线转而利用数据本身的取值范围和分布信息。把这个思维模型立住了后面看每个算法才会有体感。否则只是背了十个代码模板换个数据分布就抓瞎。1.2 十大算法的分组与复杂度总览教你怎么记十个算法看起来杂乱其实可以按两条主线分组第一组是比较类排序包括冒泡、选择、插入、希尔、快排、堆排、归并它们靠元素之间的比较决定顺序下限是O(n log n)。第二组是非比较类排序包括计数、基数、桶它们靠数据本身的形态直接归位能突破比较排序下界但有严格的数据前提不是万能药。记忆的时候可以再按复杂度阶梯拆O(n²)组是冒泡、选择、插入O(n log n)组是快排、堆排、归并希尔是介于两者之间的过渡品桶、计数、基数属于另一个跑道。我自己更喜欢用稳定性来记冒泡、插入、归并、计数、基数天然稳定选择、快排、堆排、希尔不稳定桶排序稳定性取决于桶内实现。面试时最常问的一题就是哪些排序稳定这张表能直接背算法平均最坏最好额外空间稳定性原地冒泡O(n²)O(n²)O(n)O(1)稳定原地选择O(n²)O(n²)O(n²)O(1)不稳定原地插入O(n²)O(n²)O(n)O(1)稳定原地希尔约O(n^1.3)O(n²)O(n)O(1)不稳定原地快排O(n log n)O(n²)O(n log n)O(log n)不稳定原地堆排O(n log n)O(n log n)O(n log n)O(1)不稳定原地归并O(n log n)O(n log n)O(n log n)O(n)稳定非原地计数O(nk)O(nk)O(nk)O(k)稳定非原地基数O(d(nk))O(d(nk))O(d(nk))O(nk)稳定非原地桶O(nk)O(n²)O(n)O(nk)看实现非原地这里有个细节快排和堆排虽然复杂度同为O(n log n)但原地的含义不太一样。快排的O(log n)空间来自递归栈堆排的空间是纯O(1)所以堆排在内存受限的嵌入式场景更常见。归并每次都开临时数组空间开销是O(n)这决定了它在极端内存环境下只适合当外部排序的底层思想而不适合在内存紧张的设备上直接跑。1.3 稳定性不是面试官刁难业务里真会被坑到稳定性的定义很简单两个相等元素的相对位置在排序前后保持一致。很多初学者觉得这概念就是为面试准备的实际业务里根本用不上。我一开始也这么想直到线上一个排行榜功能出了bug。当时要对一批用户数据做二次排序先按等级降序等级相同的人按注册时间升序。实现时用了某个不稳定排序第一次按注册时间排好了序第二次按等级排的时候等级相等的用户内部顺序被彻底打乱注册时间的先后完全错乱。因为不稳定排序在交换元素时是跨距离的两个值相等的元素可能被交换到对方前面去。这个bug查了一下午最后发现根本不是逻辑写错而是排序算法选错了。所以稳定性在真实工程里非常重要。数据库的执行计划、排行榜、多列排序、分页后的排序凡是先按A排再按B排的场景都要确保某个维度上的排序结果不被后面的排序破坏。这也是为什么很多标准库的排序实现即便平均性能不如快排也要设计成稳定排序。2. O(n log n)集团拆解快排、希尔、堆排、归并的实现机制与隐藏代价2.1 快速排序分治思路、退化条件与工程优化快排的核心是分治和partition。每次选一个基准值把数组分成小于等于基准和大于基准两段再递归处理左右两段。只要每次分区接近对半递归深度是log n每层合计扫描n个元素总复杂度就是O(n log n)。def quick_sort(arr, left, right): if left right: return mid partition(arr, left, right) quick_sort(arr, left, mid - 1) quick_sort(arr, mid 1, right) def partition(arr, left, right): pivot arr[right] i left - 1 for j in range(left, right): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[right] arr[right], arr[i 1] return i 1上面这段用的是常见的分区写法之一相当于每轮把比基准小的值往左边赶最后再把基准放到中间位置。这里要留意的点是当数组已经有序时如果每次选最后一个元素当基准分区就完全不均衡左半边长度是0右半边是n-1递归深度退化到n复杂度变成O(n²)。所以面试官问快排什么时候最坏本质就在问基准值选择的问题。工程上的缓解办法有三个一是三数取中从区间头、尾、中间三个位置取一个中间值当基准让有序数组这个最坏输入基本失效二是递归到小区间时改用插入排序因为插入排序在接近有序的小数组上极快三是控制递归深度深度超过阈值时改用堆排序兜底。C标准库的排序实现基本就是这个思路别再以为工程里真的是裸写一个递归快排。快排虽然不稳定但它的常数项非常小对缓存也非常友好因为partition是顺序扫描数组局部性极好所以实际运行速度往往比同为O(n log n)的堆排和归并都快。2.2 希尔排序插入排序的跨度升级与不稳定真相希尔排序是插入排序的改进版。插入排序的痛点在于它每次只能把元素移动一位如果一个很小的元素恰好在数组末尾要经历n-1次挪动才能回到前面。希尔排序的思路是先大步跨地调整让元素先跳跃式地接近最终位置最后再用普通插入排序收尾。def shell_sort(arr): n len(arr) gap n // 2 while gap 0: for i in range(gap, n): temp arr[i] j i while j gap and arr[j - gap] temp: arr[j] arr[j - gap] j - gap arr[j] temp gap // 2 return arrgap序列的选择是希尔排序性能的核心。上面代码用的是最简单的折半递减即n/2, n/4, ..., 1。这种序列的平均复杂度大约在O(n^1.3)到O(n^1.5)之间不及O(n log n)那几位稳定。如果改用一些精心设计的gap序列比如Hibbard序列或Sedgewick序列最坏情况可以压到O(n^1.5)甚至更好。不过实战中希尔排序并不常用它的历史地位更多是第一个突破O(n²)的排序算法以及展示插入排序潜力可以挖掘这个思想。这里有个容易踩的认知误区希尔排序不稳定。原因很简单当gap大于1时元素会在不同子序列之间跨步交换两个相等的值可能在某一轮里被一个较大元素隔开跨越交换后相对次序就变了。你要是拿它做多列排序结果一定有问题。2.3 堆排序建堆为什么是O(n)明明O(n log n)却常常慢堆排序依赖二叉堆。先原地把数组调整成一个大顶堆然后反复把堆顶最大值交换到数组末尾缩小堆范围再调整堆。大顶堆保证了每次堆顶都是当前最大值取出的过程天然有序。def heap_sort(arr): n len(arr) def sift_down(i, size): while True: largest i left 2 * i 1 right 2 * i 2 if left size and arr[left] arr[largest]: largest left if right size and arr[right] arr[largest]: largest right if largest i: break arr[i], arr[largest] arr[largest], arr[i] i largest for i in range(n // 2 - 1, -1, -1): sift_down(i, n) for end in range(n - 1, 0, -1): arr[end], arr[0] arr[0], arr[end] sift_down(0, end) return arr首先要破除一个直觉误区建堆不是O(n log n)而是O(n)。因为大部分节点离叶子很近从最后一层往上看越往下节点需要的下滤次数越少总工作量是求和之后收敛到O(n)的。建堆完成后每次取最大值只需要O(log n)的下滤n次取完所以堆排序总体是O(n log n)。那为什么堆排序理论复杂度很漂亮实际却经常跑不过快排两个原因。第一堆排序的访问模式是跳跃式的数组下标i和2i1之间的跨度越来越远cache miss比快排的连续扫描严重得多。第二堆排序交换次数固定偏多就算数据已经有序它依然要完整建堆、完整取出不存在提前结束的机制。堆排序的优势场景是TopK、优先级队列、外部排序里需要稳定维护部分有序集的场景而不是大数组全量排序。堆排序的不稳定性也很直观堆调整时会把父节点和子节点交换这种跨越式交换完全不管相等元素的原始次序所以堆排序不可能稳定。2.4 归并排序稳定性的代价与外部排序的血缘归并排序的思路是标准的分而治之再合并。把数组反复对半拆直到每个子序列只剩一个元素然后两两合并合并时通过比较两个子序列头部的大小依次取出较小值。def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result [] i j 0 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 result.extend(left[i:]) result.extend(right[j:]) return result归并排序最突出的优点是稳定而且是O(n log n)里唯一稳定的纯比较类排序。关键在merge那一行写的是left[i] right[j]等于的时候优先取左边相等元素的相对次序就不会被打乱。很多人自己实现归并时会顺手写成相等时先取右边这样归并排序就不稳定了面试里很容易被考官抓这个细节。归并排序的代价是额外空间O(n)。递归版还有递归栈的开销。工程上如果要降低空间占用可以用自底向上的迭代归并先用临时数组做几次小规模合并再加倍粒度递归栈省掉了但额外数组依然省不掉。归并的真正舞台是外部排序——数据量大到内存放不下时先分段排序写回磁盘再通过多路归并把磁盘上的有序段合并成完整顺序这套思想几乎就是归并排序的直接延伸。到这里四个主力比较排序就讲完了。工程选型时优先级基本是快排最快但不稳定归并最稳但要空间堆排在内存受限时兜底希尔基本退出实战舞台。3. 平方级算法并不全是废柴冒泡、选择、插入的真实存在意义3.1 冒泡排序优化后接近有序数组的快速路冒泡排序的思路是反复扫描数组比较相邻元素把较大的值一步步冒到数组尾部。最经典的优化是加一个标志位如果某一轮扫描完全没有发生交换说明数组已经有序直接结束。def bubble_sort(arr): n len(arr) for i in range(n - 1): swapped False for j in range(n - i - 1): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: break return arr加了标志位之后冒泡排序在完全有序的数组上能做到O(n)只扫描一遍就退出。这个特性看似没用但面试里经常考不是问冒泡排序复杂度是多少而是问如果数组本身有序冒泡排序还永远是O(n²)吗答案就是否。冒泡排序平时基本不会被用在生产环境但它有一个天然优势最好理解最适合讲清楚稳定排序的定义——它只交换相邻元素相等元素永远不会交换位置。我在给新人讲排序时一定会先用冒泡打底因为从冒泡过渡到插入、再到希尔是一条很好的认知曲线。3.2 选择排序唯一一个交换次数最少的比较排序选择排序的思路直白到不能再直白每一轮从剩余元素里找出最小值和当前轮次的开头元素交换一轮排好一个位置。def selection_sort(arr): n len(arr) for i in range(n): min_idx i for j in range(i 1, n): if arr[j] arr[min_idx]: min_idx j arr[i], arr[min_idx] arr[min_idx], arr[i] return arr选择排序的交换次数在最坏情况下也只有n-1次因为它每轮最多一次交换。这在写操作远贵于读操作的场景里有独特价值。比如往某种EEROM或昂贵存储介质里写数据读很多次没关系写一次要命那选择排序的交换次数优势就能体现出来。除此之外它在常规软件里没有任何性能优势。选择排序不稳定的原因值得单独拿出来说。它做的是跨距离交换比如数组里有两个相等的值2a和2b中间隔着一个更小的1选择排序会在某一轮把1和2a交换导致2a被甩到2b后面相等元素的相对次序被破坏。这个结论可以反向记忆凡是有跨距离交换的比较排序基本都不稳定只有相邻交换的排序稳定性才有保障。3.3 插入排序被大厂排序器藏在内部的核心底座插入排序的思路很像打扑克摸牌每来一张新牌就把它插到手里已排序牌的合适位置。实现上从第二个元素开始把当前元素往前挪遇到比它大的就顺位移遇到小于等于它的就停下。def insertion_sort(arr): for i in range(1, len(arr)): temp arr[i] j i - 1 while j 0 and arr[j] temp: arr[j 1] arr[j] j - 1 arr[j 1] temp return arr插入排序是三个平方级算法里最有实战价值的一个因为它在基本有序的小数组上表现极好几乎能跑到O(n)级别。这个特性让它成为很多高性能排序器内部的收尾工具快排在递归到很小区间时往往不再继续递归而是直接切到插入排序C标准库的排序实现里也有类似策略。所以不要小看O(n²)算法它在混合排序里扮演的角色是纯O(n log n)算法替代不了的。插入排序的稳定性也不难理解它在找位置时遇到等于当前元素的值就停下来不跨越相等元素所以是稳定排序。三个O(n²)算法放一起对比冒泡适合教学和展示稳定的含义选择适合极端写操作受限的场景插入适合混合排序和几乎有序的数据。它们的平均性能都不行但各自的存在逻辑都说得通。4. 突破比较下界的三个选手计数、基数、桶排序的适用前提与工程陷阱4.1 计数排序从统计到稳定回填的关键细节计数排序的思路是用数组下标直接映射值先统计每个值出现多少次再按顺序把值填回原数组。前提是数据范围小且已知比如几十万分数的排序范围在0到100之间用计数排序就是线性时间。def counting_sort(arr): if not arr: return arr min_val, max_val min(arr), max(arr) count [0] * (max_val - min_val 1) for x in arr: count[x - min_val] 1 idx 0 for i, c in enumerate(count): for _ in range(c): arr[idx] i min_val idx 1 return arr上面这版能快速理解思路但不稳定。要做成稳定的计数排序需要在统计频次后做一次前缀和让count[i]表示小于等于当前值的元素总数然后从后往前遍历原数组把每个元素放到正确位置上。从后往前是关键它保证相同值的元素越晚被遍历到的越靠后从而保持原数组的相对顺序。基数排序正是依赖这种稳定的计数排序所以这里一定要写对def counting_sort_stable(arr): if not arr: return arr min_val, max_val min(arr), max(arr) count [0] * (max_val - min_val 1) for x in arr: count[x - min_val] 1 for i in range(1, len(count)): count[i] count[i - 1] output [0] * len(arr) for x in reversed(arr): idx x - min_val output[count[idx] - 1] x count[idx] - 1 return output计数排序最大的陷阱是空间爆炸。如果数据范围是32位整数范围有42亿个可能值你不可能开一个几十亿长度的数组。所以使用前一定要确认范围尽量做偏移压缩。处理负数也很简单找出最小值后偏移到0排序完再还原代码里已经体现了这个思路。4.2 基数排序逐位分桶的LSD思路与负数陷阱基数排序用位权来分轮。以十进制为例先按个位分桶收集再按十位、百位继续每一轮都保持上一轮的相对顺序最后整体有序。这种方式叫LSD从低位到高位做。def radix_sort(arr): if not arr: return arr max_val max(arr) exp 1 while max_val // exp 0: stable_counting_sort_by_digit(arr, exp) exp * 10 return arr def stable_counting_sort_by_digit(arr, exp): output [0] * len(arr) count [0] * 10 for x in arr: digit (x // exp) % 10 count[digit] 1 for i in range(1, 10): count[i] count[i - 1] for x in reversed(arr): digit (x // exp) % 10 output[count[digit] - 1] x count[digit] - 1 arr[:] output基数排序能突破比较下界的逻辑在于每一轮按位数分桶时用的是值的数值分布而不是两两比较桶的数量是有限的基数总复杂度是O(d(nk))d是位数k是基数大小。但这里有两个工程坑。第一负数不能直接跑上面的代码因为取模得到的负数字符串会打乱顺序需要把整体偏移到非负区间排完再还原。第二浮点数不能直接按十进制位排除非你按IEEE754的编码方式处理否则结果完全错误。实战中基数排序适合对整数ID、时间戳、手机号这类固定位数的数据排序不适合字符串比较或大范围浮点数。4.3 桶排序均匀分布下的线性期望与极端退化桶排序把数据按区间分散到若干桶里每个桶内部再排序最后按桶顺序拼接。它有一个前提假设数据分布足够均匀。比如[0, 1)区间里均匀分布的浮点数把区间等分成n个桶每个桶里大约只有一个元素桶内排序几乎不用工作总体接近O(n)。def bucket_sort(arr, bucket_size5): if not arr: return arr min_val, max_val min(arr), max(arr) bucket_count (max_val - min_val) // bucket_size 1 buckets [[] for _ in range(bucket_count)] for x in arr: idx (x - min_val) // bucket_size buckets[idx].append(x) for b in buckets: b.sort() result [] for b in buckets: result.extend(b) return result桶排序的稳定性取决于桶内排序和桶的拼接方式。桶内如果使用稳定排序桶按顺序排列桶排序就稳定。但实际很少用它来做需要稳定的排序因为它的适用条件和性能收益都比较依赖数据形态。最坏情况是数据全部挤进同一个桶桶排序退化成一个先收集再桶内排序的普通排序复杂度和桶内算法一致通常是O(n²)。所以在工程里桶排序不是通用排序的候选它更像是我知道数据分布形态时的定制化武器。比如对一批均匀分布的测量值做分箱统计桶排序一次扫描还能顺便完成数据的分布分析性价比极高。5. 实测与选型一万到百万数据量下工程里到底该用哪个5.1 一组本机实测量级对比和三种数据分布理论学习归理论学习我习惯每个算法都跑一组数据不信邪。用Python对n10000和n100000的随机整数做了简单计时顺便也测了已排序和倒序两种分布数据量级大致如下算法10000随机100000随机100000已排序100000倒序冒泡约0.5s约50s约0.01s约50s选择约0.25s约25s约25s约25s插入约0.4s约40s约0.001s约80s希尔约8ms约0.1s约0.02s约0.15s快排约3ms约0.04s约0.02s约0.3s堆排约4ms约0.06s约0.08s约0.07s归并约4ms约0.05s约0.03s约0.05s计数约1ms约3ms约3ms约3ms基数约2ms约5ms约5ms约5ms桶约3ms约10ms约8ms约12ms数据分布的影响很明显冒泡和插入在有序数组上极快选择排序完全不受输入顺序影响快排在倒序时明显变慢我用的简单基准选择方案计数和基数的速度则完全不受数据原始顺序影响。你手头的机器跑出来会不一样但量级关系大致如此。Python本身的解释器开销和递归调用成本会让很多结论偏离C的表现比如快排在C里会比归并更明显地快而在Python里差距被缩小了。5.2 选型决策先回答三个问题再挑排序方案面对一个排序需求我自己习惯先问三个问题数据量大不大内存够不够要不要稳定数据量小到几千根本不纠结用语言内置排序就行插入排序内部优化到几乎最优手动实现大概率更慢。数据是固定范围整数比如分数、状态码、ID优先想计数排序或基数排序线性时间和常数级差距是实打实的。数据量上千万内存吃紧堆排序的O(1)空间有优势但要注意cache miss。明确要稳定优先归并排序或内置稳定排序别用快排硬撑着写复杂补偿逻辑。只要TopK别全排用堆或者快排的partition剪枝复杂度能省一大截。语言内置排序永远是你第一个该依赖的工具。C标准库的排序实现是快排和插入排序的混合体Python内置排序是稳定排序内部也做了大量优化。自己手写一个裸排序去挑战标准库几乎都是输家。只有当你的数据有特殊形态比如范围有限、均匀分布、要稳定且数据量大才值得上特殊排序。5.3 真实工程里的排序坑比较器语义、稳定性和外部归并手写排序之外工程里更常遇到的是比较器写错。Java里compare方法返回值是负数、零、正数很多人图省事直接返回a - b结果两个大数相减溢出排序顺序诡异找半天找不到原因。稳妥写法是Integer.compare(a, b)。Python的functools.cmp_to_key也容易在自定义比较器上踩坑能用keylambda x: x.xxx就别自定义比较器。稳定性在多级排序里是硬需求。刚才提到先按A排再按B排的问题很多语言的内置排序默认不进不稳严谨。Go的sort.Slice是不稳定排序想稳定必须用sort.SliceStable这个细节不知道的人真不少。数据量大到放不进内存时思路就回到归并排序。把大文件切块每块单独排序写回磁盘然后维护一个k路归并的缓冲区每次从各个有序块里取最小值一路写下去。这个过程本质就是归并排序的合并阶段只不过把内存里的数组换成了磁盘上的文件。这也解释了为什么我在讲归并排序时特别强调它的合并逻辑因为外排和内存排序的代码结构几乎相同只是数据载体不同。最后分享一个我工作里养成的习惯接到排序需求先不要埋头写循环花两分钟确认数据规模、输入分布、稳定性要求。很多项目里所谓的性能瓶颈最后查出来都是用错了排序策略——要么在几万个元素上手写了一个O(n²)要么因为不稳定排序导致多列排序结果错乱。排序算法学到后面比的是在真实场景里三十秒内判断该用哪个方案的判断力而不是背的代码模板多。多跑几组数据多记几个坑比空刷五遍代码有用。