目录一、 排序算法全局图谱二、 内部排序核心指标终极对比表三、 多维度深度剖析与考点总结3.1 时间复杂度维度3.2 空间复杂度维度3.3 稳定性规律3.4 过程特征每一趟的中间结果3.5 存储结构适用性四、 真实业务场景五、 工业级实现前言在前面的文章中我们已经将插入、交换、选择、归并以及非比较类的核心排序算法逐一拆解。在掌握了各个具体算法的底层逻辑后建立全局观、学会根据不同场景进行算法选型是检验是否真正精通排序算法的唯一标准。本文将参考经典教材对内部排序算法进行终极梳理与多维度大比拼。一、 排序算法全局图谱在计算机科学中排序算法首先按照数据是否完全在内存中处理分为两大类内部排序数据量不大排序过程全部在内存中完成本系列的核心。外部排序数据量过大内存无法一次性装下排序过程需在内存与外存磁盘之间不断进行数据交换。在内部排序中根据底层驱动机制又可分为比较类排序通过比较元素之间的大小来决定先后顺序。这类算法在最坏情况下的时间复杂度下界是O ( n log ⁡ n ) O(n \log n)O(nlogn)。非比较类排序不通过比较而是利用数据的内在特征如按位分配、计数进行排序可突破O ( n log ⁡ n ) O(n \log n)O(nlogn)的下界达到线性时间O ( n ) O(n)O(n)。二、 内部排序核心指标终极对比表算法分类算法名称最好时间复杂度平均时间复杂度最坏时间复杂度空间复杂度稳定性插入类直接插入排序O ( n ) O(n)O(n)O ( n 2 ) O(n^2)O(n2)O ( n 2 ) O(n^2)O(n2)O ( 1 ) O(1)O(1)稳定折半插入排序O ( n log ⁡ n ) O(n \log n)O(nlogn)O ( n 2 ) O(n^2)O(n2)O ( n 2 ) O(n^2)O(n2)O ( 1 ) O(1)O(1)稳定希尔排序-约O ( n 1.3 ) O(n^{1.3})O(n1.3)O ( n 2 ) O(n^2)O(n2)O ( 1 ) O(1)O(1)不稳定交换类冒泡排序O ( n ) O(n)O(n)O ( n 2 ) O(n^2)O(n2)O ( n 2 ) O(n^2)O(n2)O ( 1 ) O(1)O(1)稳定快速排序O ( n log ⁡ n ) O(n \log n)O(nlogn)O ( n log ⁡ n ) O(n \log n)O(nlogn)O ( n 2 ) O(n^2)O(n2)O ( log ⁡ n ) O(\log n)O(logn)不稳定选择类简单选择排序O ( n 2 ) O(n^2)O(n2)O ( n 2 ) O(n^2)O(n2)O ( n 2 ) O(n^2)O(n2)O ( 1 ) O(1)O(1)不稳定堆排序O ( n log ⁡ n ) O(n \log n)O(nlogn)O ( n log ⁡ n ) O(n \log n)O(nlogn)O ( n log ⁡ n ) O(n \log n)O(nlogn)O ( 1 ) O(1)O(1)不稳定归并类二路归并排序O ( n log ⁡ n ) O(n \log n)O(nlogn)O ( n log ⁡ n ) O(n \log n)O(nlogn)O ( n log ⁡ n ) O(n \log n)O(nlogn)O ( n ) O(n)O(n)稳定非比较类计数排序O ( n k ) O(nk)O(nk)O ( n k ) O(nk)O(nk)O ( n k ) O(nk)O(nk)O ( n k ) O(nk)O(nk)稳定基数排序O ( d ( n r ) ) O(d(nr))O(d(nr))O ( d ( n r ) ) O(d(nr))O(d(nr))O ( d ( n r ) ) O(d(nr))O(d(nr))O ( r ) O(r)O(r)稳定(注k kk为计数范围d dd为数据位数r rr为基数)三、 多维度深度剖析与考点总结3.1 时间复杂度维度O ( n 2 ) O(n^2)O(n2)阵营简单选择排序、直接插入排序、冒泡排序。其中简单选择排序最死板无论初始状态如何都是O ( n 2 ) O(n^2)O(n2)而直接插入和冒泡带优化最聪慧在数组“基本有序”时可迅速降级为O ( n ) O(n)O(n)。O ( n log ⁡ n ) O(n \log n)O(nlogn)阵营快速排序、堆排序、归并排序。快速排序平均情况下实测最快但极其忌讳“基本有序”的数据最坏会退化到O ( n 2 ) O(n^2)O(n2)。堆排序与归并排序极其稳健最好、最坏、平均时间永远死死锁定在O ( n log ⁡ n ) O(n \log n)O(nlogn)。3.2 空间复杂度维度原地排序 (O ( 1 ) O(1)O(1))插入类、冒泡、简单选择、堆排序。快速排序 (O ( log ⁡ n ) O(\log n)O(logn))并非原地排序其空间开销来源于递归调用栈。最坏情况下单支树空间会退化到O ( n ) O(n)O(n)。归并排序 (O ( n ) O(n)O(n))典型的空间换时间需要一个与原数组等大的辅助数组用于合并。3.3 稳定性规律业务意义在多关键字排序中例如先按销量排相同的再按价格排稳定的算法能保留上一次排序的相对顺序。规律口诀“长距离、大跨步交换的算法通常不稳定相邻交换或顺次挪位的算法通常稳定。”希尔排序按 gap 跨步交换、快速排序跨越整个数组填坑、选择排序跨越无序区交换、堆排序首尾直接交换均不稳定。直接插入、冒泡、归并排序均稳定。3.4 过程特征每一趟的中间结果能确定最终位置的算法冒泡排序、简单选择排序、快速排序、堆排序。这四种算法每完成一趟处理必定能将至少一个元素放到它的最终确切位置上。不能确定最终位置的算法直接插入排序、折半插入排序。它们只是局部有序新元素的插入可能导致前面已排好的所有元素集体后移。3.5 存储结构适用性仅适用于顺序存储数组折半插入排序、希尔排序、快速排序、堆排序。它们严重依赖随机访问通过下标跳跃查找。顺序与链式存储皆可直接插入排序、冒泡排序、简单选择排序、归并排序、基数排序。如果数据节点特别大移动数据代价极高使用链表结合这些算法仅修改指针是绝佳选择。四、 真实业务场景在实际的软件工程中没有一种算法能包打天下。我们需要根据具体的数据环境进行智能选型当数据量n nn极小 (n 50 n 50n50) 时优先选择直接插入排序或简单选择排序。原因虽然理论复杂度是O ( n 2 ) O(n^2)O(n2)但在n nn极小的情况下它们没有递归调用栈的开销且常数项极小实测速度往往超过快排。当数据量n nn极大且对内存没有严格限制时首选快速排序。原因它是基于比较的排序中常数因子最小的算法缓存命中率极高综合性能制霸全场。当数据量n nn极大且要求最坏情况绝不能卡顿如航天、军工、实时系统选择堆排序或归并排序。原因快速排序在极端恶劣数据下会退化而堆排和归并能将时间严格控制在O ( n log ⁡ n ) O(n \log n)O(nlogn)。若内存极为受限选堆排序O ( 1 ) O(1)O(1)空间若要求稳定选归并排序。当数据初始状态“基本有序”时强烈推荐直接插入排序或冒泡排序。原因此时它们的比较和移动次数极少时间复杂度趋近于线性的O ( n ) O(n)O(n)比快排还要快。当数据是范围密集的整数如全省高考成绩排行直接使用计数排序或基数排序。原因降维打击直接突破O ( n log ⁡ n ) O(n \log n)O(nlogn)极限实现O ( n ) O(n)O(n)级别的神速排序。五、 工业级实现如果你去阅读 C 的std::sort或 Java/Python 的内部排序源码你会发现真实的工业界从来不单纯使用某一种单一算法。以大名鼎鼎的IntroSort内省式排序为例起手对于庞大的数据首先使用快速排序进行宏观分治追求极致速度。监控算法内部会监控递归的深度。如果发现递归深度超过了2 log ⁡ n 2 \log n2logn说明遭遇了恶劣数据有退化为O ( n 2 ) O(n^2)O(n2)的风险。切换此时算法会立刻“急刹车”停止快排切换为绝对稳健的堆排序守住O ( n log ⁡ n ) O(n \log n)O(nlogn)的底线。收尾当快排将数组划分成长度极小如小于 16的子区间时算法停止递归对整个接近有序的数组来一次直接插入排序完成最后的精修。结语与下篇预告至此我们关于内部排序的盘点已圆满收官。但是挑战并未结束——当数据规模暴涨到 GB 甚至 TB 级别连内存都无法一次性装下时我们该如何打破物理内存的枷锁下篇带你深入了解。