4 排序排序问题给定数组A[1..n]A[1..n]A[1..n]输出升序排列的数组B[1..n]B[1..n]B[1..n]。排序的用处远超 把数据排整齐 ——排好序之后二分搜索、去重、找中位数、找最近对等操作都变得简单。数据压缩也依赖排序来发现重复项。比较排序一、插入排序Insertion Sort思想维护一个已排序的前缀A[1..j−1]A[1..j-1]A[1..j−1]每次将A[j]A[j]A[j]通过逐对交换 下沉 到正确位置。INSERTION-SORT(A, n) for j ← 2 to n key A[j] i j - 1 while i 0 and A[i] key A[i1] A[i] i i - 1 A[i1] key示例对[8, 2, 4, 9, 3, 6]排序轮次操作数组状态j2插入 2[2, 8, 4, 9, 3, 6]j3插入 4[2, 4, 8, 9, 3, 6]j4插入 9[2, 4, 8, 9, 3, 6]j5插入 3[2, 3, 4, 8, 9, 6]j6插入 6[2, 3, 4, 6, 8, 9]最好情况已排序O(n)O(n)O(n)内层循环不执行最坏情况逆序O(n2)O(n^2)O(n2)每个元素都要交换到最前面二分插入排序用二分搜索找到插入位置比较次数降到O(log⁡n)O(\log n)O(logn)但元素移动仍然是O(n)O(n)O(n)。总体O(nlog⁡n)O(n \log n)O(nlogn)次比较O(n2)O(n^2)O(n2)次交换。二、归并排序Merge Sort分治策略如果n1n 1n1直接返回递归排序A[1..n/2]A[1..n/2]A[1..n/2]和A[n/21..n]A[n/21..n]A[n/21..n]合并两个已排序的子数组合并过程两个指针分别指向两个子数组的开头每次取较小的元素放入输出数组指针前移。合并两个长度为nnn的有序数组需要O(n)O(n)O(n)时间。复杂度分析递归树法T(n)2T(n/2)cnT(n) 2T(n/2) cnT(n)2T(n/2)cn递归树每层的总代价都是cncncn第 1 层cncncn第 2 层2×cn/2cn2 \times cn/2 cn2×cn/2cn第 3 层4×cn/4cn4 \times cn/4 cn4×cn/4cn……。树高1log⁡n1 \log n1logn层叶子节点共nnn个。T(n)cn⋅(1log⁡n)O(n)O(nlog⁡n)T(n) cn \cdot (1 \log n) O(n) O(n \log n)T(n)cn⋅(1logn)O(n)O(nlogn)三、快速排序Quicksort分治策略但和归并排序的分工方向相反——归并排序 分简单、合复杂 快速排序 分复杂、合简单 。划分Partition选择枢轴元素xA[r]x A[r]xA[r]将数组分成两部分使得左边 ≤xxx右边 ≥xxx。PARTITION(A, p, r) x A[r] // 枢轴 i p - 1 for j p to r-1 if A[j] ≤ x i i 1 swap A[i], A[j] swap A[i1], A[r] return i 1划分代价O(n)O(n)O(n)。复杂度分析最好情况每次均匀划分T(n)2T(n/2)Θ(n)Θ(nlog⁡n)T(n) 2T(n/2) \Theta(n) \Theta(n \log n)T(n)2T(n/2)Θ(n)Θ(nlogn)最坏情况每次极端不平衡如已排序数组 固定取末尾做枢轴T(n)T(n−1)Θ(n)Θ(n2)T(n) T(n-1) \Theta(n) \Theta(n^2)T(n)T(n−1)Θ(n)Θ(n2)1:9 划分T(n)T(n/10)T(9n/10)O(n)T(n) T(n/10) T(9n/10) O(n)T(n)T(n/10)T(9n/10)O(n)。递归树中每层代价 ≤cncncn树高log⁡10/9n\log_{10/9} nlog10/9​n仍然是O(nlog⁡n)O(n \log n)O(nlogn)交替最好最坏最好B(n)2W(n/2)Θ(n)B(n) 2W(n/2) \Theta(n)B(n)2W(n/2)Θ(n)最坏W(n)B(n−1)Θ(n)W(n) B(n-1) \Theta(n)W(n)B(n−1)Θ(n)展开后B(n)2B(n/2−1)Θ(n)O(nlog⁡n)B(n) 2B(n/2-1) \Theta(n) O(n \log n)B(n)2B(n/2−1)Θ(n)O(nlogn)随机化快速排序随机选择枢轴使运行时间不依赖输入的初始顺序。期望时间O(nlog⁡n)O(n \log n)O(nlogn)。分析思路定义指示随机变量XkX_kXk​表示是否产生k:(n−k−1)k : (n-k-1)k:(n−k−1)的划分。E[Xk]1/nE[X_k] 1/nE[Xk​]1/n。代入期望递推式展开利用调和级数∑1/kO(log⁡n)\sum 1/k O(\log n)∑1/kO(logn)得到E[T(n)]O(nlog⁡n)E[T(n)] O(n \log n)E[T(n)]O(nlogn)。四、比较排序的下界定理任何基于比较的排序算法最坏情况下至少需要Ω(nlog⁡n)\Omega(n \log n)Ω(nlogn)次比较。证明决策树模型任何比较排序的执行过程可以画成一棵二叉决策树。每个内部节点是一次比较ai:aja_i : a_jai​:aj​左右分支对应比较结果叶节点对应一种排列结果。必须有 ≥n!n!n!个叶节点每种排列至少对应一个叶节点高度为hhh的二叉树最多有2h2^h2h个叶节点所以2h≥n!2^h \geq n!2h≥n!即h≥log⁡(n!)≥log⁡(ne)nnlog⁡n−nlog⁡eΩ(nlog⁡n)h \geq \log(n!) \geq \log\left(\frac{n}{e}\right)^n n \log n - n \log e \Omega(n \log n)h≥log(n!)≥log(en​)nnlogn−nlogeΩ(nlogn)这意味着O(nlog⁡n)O(n \log n)O(nlogn)是比较排序能做到的最好情况。归并排序和随机化快速排序都达到了这个下界。线性时间排序非比较排序如果放弃 只通过比较确定顺序 的限制利用元素值本身的结构信息可以突破Ω(nlog⁡n)\Omega(n \log n)Ω(nlogn)的下界。一、计数排序Counting Sort适用条件元素的键值取值范围为[1,k][1, k][1,k]kkk已知且不太大。思想不做任何比较直接统计每个键值出现的频率。四步流程初始化频率数组C[1..k]C[1..k]C[1..k]为 0——O(k)O(k)O(k)遍历AAA统计频率C[A[j]]C[A[j]]C[A[j]]——O(n)O(n)O(n)前缀和C[i]C[i]C[i−1]C[i] C[i] C[i-1]C[i]C[i]C[i−1]使C[i]C[i]C[i]表示键值 ≤iii的元素个数——O(k)O(k)O(k)从后往前遍历AAA将A[j]A[j]A[j]放到B[C[A[j]]]B[C[A[j]]]B[C[A[j]]]的位置C[A[j]]C[A[j]]C[A[j]]–——O(n)O(n)O(n)COUNTING-SORT(A, B, k) for i ← 1 to k: C[i] ← 0 for j ← 1 to n: C[A[j]] ← C[A[j]] 1 for i ← 2 to k: C[i] ← C[i] C[i-1] for j ← n downto 1: B[C[A[j]]] ← A[j] C[A[j]] ← C[A[j]] - 1总时间O(nk)O(n k)O(nk)。当kO(n)k O(n)kO(n)时为O(n)O(n)O(n)。为什么第 4 步从后往前遍历这保证了稳定性相同键值的元素保持原来的相对顺序。稳定性在基数排序中是必需的。为什么不违反Ω(nlog⁡n)\Omega(n \log n)Ω(nlogn)下界因为计数排序不是比较排序——全程没有做任何元素间的比较。二、基数排序Radix Sort思想按位digit从低位到高位逐位使用稳定排序如计数排序。为什么低位优先高位优先会导致需要递归地对每个桶内的元素继续排序而低位优先借助稳定排序的性质高位排完后低位的顺序自然保持。正确性归纳法假设按前t−1t-1t−1位排好了。第ttt位排序后第ttt位不同的元素按第ttt位排序正确第ttt位相同的元素由于稳定性保持前t−1t-1t−1位的顺序也正确。复杂度每个键值有bbb个二进制位分成b/rb/rb/r个 位组 每组rrr位。每轮计数排序代价O(n2r)O(n 2^r)O(n2r)共b/rb/rb/r轮。总时间O((b/r)(n2r))O((b/r)(n 2^r))O((b/r)(n2r))。取rlog⁡nr \log nrlogn每轮代价O(n)O(n)O(n)总时间O(bn/log⁡n)O(bn/\log n)O(bn/logn)。排序算法对比算法最好平均最坏空间稳定类型插入排序O(n)O(n)O(n)O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)O(1)O(1)O(1)是比较归并排序O(nlog⁡n)O(n\log n)O(nlogn)O(nlog⁡n)O(n\log n)O(nlogn)O(nlog⁡n)O(n\log n)O(nlogn)O(n)O(n)O(n)是比较快速排序O(nlog⁡n)O(n\log n)O(nlogn)O(nlog⁡n)O(n\log n)O(nlogn)O(n2)O(n^2)O(n2)O(log⁡n)O(\log n)O(logn)否比较计数排序O(nk)O(nk)O(nk)O(nk)O(nk)O(nk)O(nk)O(nk)O(nk)O(k)O(k)O(k)是非比较基数排序O(d(nk))O(d(nk))O(d(nk))O(d(nk))O(d(nk))O(d(nk))O(d(nk))O(d(nk))O(d(nk))O(nk)O(nk)O(nk)是非比较