 的底层密码)
目录一、 归并排序 (Merge Sort)1.1 算法思想1.2 代码实现1.3 运行推演1.4 复杂度分析二、 计数排序 (Counting Sort)2.1 算法思想2.2 具体步骤推演2.3 复杂度分析三、 基数排序 (Radix Sort)3.1 算法思想3.2 LSD 基数排序步骤推演以十进制为例3.3 复杂度分析前言 在之前的三篇文章中我们拆解了插入、交换、选择三大类共八种基于比较的排序算法。它们共同遵循一条铁律任何基于比较的排序时间复杂度下界为 O(n log n)。然而现实世界中存在某些数据凭借其内在结构可以绕过这个理论极限直接冲击线性时间。本文将聚焦三种特殊的排序算法归并排序比较类中的分治典范稳定且能处理海量数据、计数排序与基数排序非比较类双雄在特定场景下可达 O(n)。我们将从算法思想、代码实现、单步推演到复杂度分析逐一揭穿它们的高效秘密。一、 归并排序 (Merge Sort)1.1 算法思想归并排序是“分而治之”思想的教科书级演绎。其核心分为两步分 (Divide)将当前序列从中间位置一分为二并递归地对左右子序列继续切分直到每个子序列只剩下一个元素天然有序。治 (Merge)将两个已经有序的子序列合并成一个更大的有序序列。关键在于“合并”想象桌面上有两叠正面朝上的扑克牌每叠都已经从小到大排好。你每次只能看到最上面的一张比较两张牌将较小的那张抽出放入结果队列重复直到某一叠空掉再将另一叠剩余的所有牌直接接在末尾。归并排序的合并过程正是用双指针在辅助数组上完成这个“二路归一”的动作。1.2 代码实现以下为归并排序的核心 C 语言实现包括合并函数Merge与递归控制函数MergeSort。代码中使用全局变量n表示数组长度并动态分配了与原始数组等长的辅助数组b。// n为全局变量 static int n; n sizeof(a) / sizeof(DataType);DataType*b(DataType*)malloc((n1)*sizeof(DataType));voidMerge(DataType a[],intlow,intmid,inthigh){intilow,jmid1,k;for(klow;khigh;k)b[k]a[k];ki;while(imidjhigh){if(b[i]b[j])a[k]b[j];elsea[k]b[i];}while(imid)a[k]b[i];while(jhigh)a[k]b[j];}voidMergeSort(DataType a[],intlow,inthigh){if(lowhigh){intmidlow(high-low)/2;MergeSort(a,low,mid);MergeSort(a,mid1,high);Merge(a,low,mid,high);}}代码深度解析辅助数组b由于合并两个有序段时不能原地完成直接覆盖会丢失数据所以需要一块等长的临时空间。Merge的第一步是将待合并区间[low, high]整体拷贝到b之后在b上做双指针比较结果直接写回原数组a。双指针合并指针i扫描左半段[low, mid]指针j扫描右半段[mid1, high]。while循环每次挑选b[i]和b[j]中较小者放入a[k]同时推进对应指针。注意条件if (b[i] b[j])是“大于时才选右”当元素相等时会走else分支放入左元素这是保证归并排序稳定性的关键。收尾退出主循环后要么左半段有剩余要么右半段有剩余直接用两个while将剩余元素依次填入a。由于剩余部分本身已经有序直接追加即可。递归控制MergeSort采用标准的二分递归mid low (high - low) / 2的写法可防止(low high)溢出。递归到底层low high后开始回溯合并属于典型的后序遍历模式。1.3 运行推演以初始数组4 6 3 2 8 0 1 10 5 4为例完整跟踪归并排序的合并过程。以下为程序输出的合并日志清晰展示了长度由小到大的归并片段如何最终覆盖整个数组初始数组:46328011054合并[0~0]和[1~1]后:46328011054合并[0~1]和[2~2]后:34628011054合并[3~3]和[4~4]后:34628011054合并[5~5]和[6~6]后:23468011054合并[8~8]和[9~9]后:23468011045合并[0~2]和[3~4]后:23468011054合并[5~6]和[7~7]后:23468011054合并[5~7]和[8~9]后:23468014510合并[0~4]和[5~9]后:0123445681001234456810步骤详解最底层合并数组被逐层拆分最先合并的是相邻的单个元素对如[0~0]的4与[1~1]的6合并后依然为4 6。注意[8~8]和[9~9]5和4合并后变为4 5局部有序。中间层合并长度为 2 的有序段再合并成长度为 4 的段。例如[0~2](3 4 6) 与[3~4](2 8) 合并得到2 3 4 6 8。右半区也同步进行类似操作。顶层收束最终[0~4]的2 3 4 6 8与[5~9]的0 1 4 5 10合并完整有序序列诞生。整个过程如同一棵倒置的二叉树叶子长出有序片段根结点汇成最终结果。1.4 复杂度分析时间复杂度任何情况下均为 O(n log n)。归并排序的递归深度为 log n每一层需要对所有 n 个元素进行一次合并总操作次数严格稳定。无论数据有序与否分割与合并的动作都不会减少。这种“不挑食”的特性使它特别适合外部排序。空间复杂度O(n)。辅助数组b占据了与原始数组同等规模的空间。递归调用栈的深度为 O(log n)可忽略不计。因此归并排序不是原地排序算法内存开销是其唯一明显的短板。稳定性稳定。在Merge函数中当b[i] b[j]时我们会优先放置左半段的元素即b[i]这保证了相等元素的原始相对顺序不会在合并过程中被破坏。二、 计数排序 (Counting Sort)2.1 算法思想计数排序彻底抛弃了元素之间的两两比较。它假设输入数据是落在某个已知范围[min, max]内的整数或者可以映射为整数的对象核心思想是统计每个可能的值出现了多少次然后按照值的顺序依次“复制”出相应数量的元素直接构建有序序列。想象一场按年龄分组的排队你已知所有人的年龄都在 0~120 岁之间于是可以提前准备好 121 个空桶每遇到一个人就往对应年龄的桶里投一枚代币。投完后从 0 岁到 120 岁逐个清点桶里的代币数每清点一个年龄就让该数量的该年龄的人出列最终队伍必然按年龄有序。计数排序正是这样的非比较排序。2.2 具体步骤推演设原始数组A [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]已知所有元素取值范围在 1~9 之间或更宽但确定为 0~9。执行过程如下确定范围找到最小值min 1最大值max 9则计数数组长度为max - min 1 9。初始化计数数组开辟长度为 9 的数组count并全部初始化为 0。统计频次遍历A对每个元素x执行count[x - min]。遍历后值 1出现 2 次值 2出现 1 次值 3出现 2 次值 4出现 1 次值 5出现 2 次值 6出现 1 次值 9出现 1 次 其余为 0累加计数为稳定排序做准备对count数组进行前缀和操作count[i] count[i-1]。累加后count表示每个值在最终有序数组中的“最后一个位置的下一位置”值 1→2值 2→3值 3→5值 4→6值 5→8值 6→9值 9→10。反向填充输出数组开辟与A等长的输出数组output。为确保稳定性从A的末尾向前遍历取A[9] 3count[3-1]为 5将 3 放入output[5-1] output[4]count[3-1]减 1 变为 4。取A[8] 5count[5-1]为 8放入output[7]计数减为 7。依此类推最终output [1,1,2,3,3,4,5,5,6,9]。回写原数组如果需要原地效果将output拷贝回A。2.3 复杂度分析时间复杂度O(n k)其中 k 是取值范围的宽度max-min1。统计、累加、反向填充均只需常数趟线性扫描没有元素间的比较。当 k 与 n 处于同一数量级或更小时计数排序接近 O(n)但若 k 极大例如取值范围遍布整个 32 位整数复杂度将退化到不可接受。空间复杂度O(n k)。需要计数数组大小 k和输出数组大小 n。原地计数排序存在但会破坏稳定性且实现复杂。稳定性稳定前提是上述反向填充的实现方式。正向填充也能正确排序但会破坏稳定性。局限性仅适用于整数或可离散映射的数据要求数据范围不能过大否则空间和时间都不可控。三、 基数排序 (Radix Sort)3.1 算法思想基数排序同样不是基于比较它利用数字的基数表示如十进制、二进制来排序。核心思想是从最低有效位LSD到最高有效位MSD依次对每一位进行稳定排序。由于稳定排序的性质高位排序不会打乱低位已经排好的顺序最终实现全局有序。LSD 基数排序的过程可以类比为一副按花色和点数分类的扑克牌先按点数低位分成 13 摞然后把各摞按顺序收集起来再按花色高位分成 4 摞收集后整副牌就变成按花色优先、点数有序的序列。用于每一位的稳定排序通常采用计数排序或桶排序因为每一位的取值空间很小十进制为 0~9二进制为 0~1。3.2 LSD 基数排序步骤推演以十进制为例待排序数组[329, 457, 657, 839, 436, 720, 355]。所有数字均为三位十进制整数位数不足可高位补零统一视之。第一趟按个位数排序使用计数排序等稳定排序个位9,7,7,9,6,0,5排序后数组变为[720, 355, 436, 457, 657, 329, 839]个位 0,5,6,7,7,9,9第二趟按十位数排序基于上一步的结果十位2,5,3,5,5,2,3排序后[720, 329, 436, 839, 355, 457, 657]十位 2,2,3,3,5,5,5第三趟按百位数排序百位7,3,4,8,3,4,6排序后[329, 355, 436, 457, 657, 720, 839]百位 3,3,4,4,6,7,8最终得到完全有序的数组。注意每一步都必须使用稳定排序否则低位的有序性会被高位排序破坏。3.3 复杂度分析时间复杂度O(d × (n k))其中 d 是最大数字的位数k 是每位可能的取值基数如十进制 k10。若 k 相对 n 为常数通常如此且 d 也是常数或近似 O(1)则基数排序可达到 O(n) 的线性时间。实际中在 d 很大时可以通过扩大基数如以 65536 为基来减少趟数这也是一种常见的工程优化。空间复杂度O(n k)主要是每趟计数排序所需的计数数组和输出数组。稳定性稳定LSB 基数排序因为每一趟稳定排序确保了全局顺序的正确构建。适用范围适用于整数、定长字符串等可分解为“位”的数据。对于浮点数可通过 IEEE 754 的位表示进行基数排序但需注意符号位和阶码的处理。与比较排序的关系基数排序能够突破 O(n log n) 下界正是因为它没有使用元素之间的比较而是利用了值的位级结构信息。这也意味着它对数据的假设更强应用范围自然受限。
