二排序与顺序统计 11 2.maximum(S)返回S中最大关键字元素 3.extract_max(S)去掉并返回S中最大关健字元素 4.increase_key(S,x,k)将×的关键字增加到k[只允许增加] *最小伏牛队列类似相反 *大根堆实现时，最大关健字元素即为第一个元素[复杂度O()]:别除最大值直接将最大值与最后一个 元素交换，堆长度减小1并调整即可[复杂度O(1ogn)小：增大某元素值通过不断和父结点比较交换实 现[复杂度O(1og)]:加入结点堆长度增加1，先将末尾元素赋值为-∞再增大值到目标即可[复杂 度0(1ogn]。 S2.3快速排序 对于包含n的数的输入数组，时间复杂度最坏情况O(n2),不稳定、就地，期望时间日(nlogn)且常 数因子很小。 *分治思相 划分：划分为左右两个子数组与中间，使得左侧均小于等于中间，右侧均大于等于中间，中间下标在 别分中确定。 解决：递归调用，两边分别排序 合并：由于子数组有序，合并直接已经排好。 def QUICKSORT(A,p,r): if (p<r) q=Partition(A,p,r) QUICKSORT(A,p,q-1) QUICKSORT(A,q+1,r) def PARTITION(A,p,r): x <A[r] i<-p-1 for j<-p to r-1 ifA[j】(=X i<-1+1 swap A[i],A[j] swap A[i+1],A[r] return i+1 另一种PARTITION: def PARTITION(A.p.r): i<-p;j<r;temp <A[i]i while (i I=j) while (A[j]>=temp and i<j) j<j-1 if (i<j) A[i]<-A[j]
二 排序与顺序统计 11 2. maximum(S) 返回 S 中最大关键字元素 3. extract_max(S) 去掉并返回 S 中最大关键字元素 4. increase_key(S, x, k) 将 x 的关键字增加到 k [只允许增加] *最小优先队列类似相反 *大根堆实现时，最大关键字元素即为第一个元素 [复杂度 O(1)]；删除最大值直接将最大值与最后一个 元素交换，堆长度减小 1 并调整即可 [复杂度 O(log n)]；增大某元素值通过不断和父结点比较交换实 现 [复杂度 O(log n)]；加入结点堆长度增加 1，先将末尾元素赋值为 −∞ 再增大值到目标即可 [复杂 度 O(log n)]。 §2.3 快速排序 对于包含 n 的数的输入数组，时间复杂度最坏情况 O(n 2 )，不稳定、就地，期望时间 Θ(n log n) 且常 数因子很小。 *分治思想 划分：划分为左右两个子数组与中间，使得左侧均小于等于中间，右侧均大于等于中间，中间下标 q 在 划分中确定。 解决：递归调用，两边分别排序。 合并：由于子数组有序，合并直接已经排好。 def QUICKSORT(A, p, r): if (p < r) q = Partition(A, p, r) QUICKSORT(A, p, q‐1) QUICKSORT(A, q+1, r) def 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[i+1], A[r] return i + 1 另一种 PARTITION： def PARTITION(A, p, r): i <‐ p; j <‐ r; temp <‐ A[i]; while (i != j) while (A[j] >= temp and i < j) j <‐ j ‐ 1 if (i < j) A[i] <‐ A[j]
二排序与顺序统计 <-i+1 while (A[i]<temp and i<j) 1<-1+1 1f(i<) A[j]<-A[i] 1<-1-1 A[i]<-temp return i *看似双方向进行，但由于必须检查越界，需要额外比较 复杂度：分解均匀时接近归并，不均匀时最坏情况，为O() *解递推式T()=max,(T(g)+T(n-1-g)+Cm可知最坏情况上界，而每次最不均匀划分能取到cm2 时间，从而可知最坏情况复杂度 平均情况：可以发现，对任何不超过固定比例（如每次少比多不超过1：9）的划分，复杂度都是O(1ogm), 利用此估算，设平均复杂度T(m),有T(n)=1∑nd(T(k)+T(m-1-k)+m)=n。T(+m。 考虑nT(m)-(m-1)Tm-1)可估算出智≤过+，利用1++~1ogn可知平均复杂度 随机快速排序：每次PARTITION并非将最右元素作为分制，而是选取随机元素分制以优化性能。 *堆排序与快速排序比较：按照通常R模型会发现堆排序的复杂度更低，而引进一级缓存（缓存的量 级在n3左右)时即会有快速排序的复杂度更低。 2.4线性时间排序 比较排序的时间下界 比较排序的算法可以用决策树的方式表示，边代表判定过程，而结点代表已经确定顺序的部分。 *决策树中至少需要！个叶结点表示！种判定结果 定理：比较排序的最坏情况时间2(n1ogn)。 证明：由于一次比较产生一层，比较h次的高度为h,而此时最多容纳24个叶结点，因此2必≥,从 而h≥1ogn)=(m1ogn) *线性时间排序一定不能直接基于比较 计数[counting】.排序 思路：对日到k中的整数组成的数列，只要知道每个整数出现了几次就会知道结果所在的位置。 def COUNTING_SORT(A,B,k) for i<-e to k c[i]<-0 for i<-1 to length(A) C[A[j]]<-C[A[j]]+1//c[t]sum(A--t) for i <-1 to k c[i]<-c[i]+c[i-1]//C[t]sum(A<=t) for i-length(A)downto 1 B[C[A[j]]<-A[j]
二 排序与顺序统计 12 i <‐ i + 1 while (A[i] <= temp and i < j) i <‐ i + 1 if (i < j) A[j] <‐ A[i] j <‐ j ‐ 1 A[i] <‐ temp return i *看似双方向进行，但由于必须检查越界，需要额外比较 复杂度：分解均匀时接近归并，不均匀时最坏情况，为 O(n 2 ) *解递推式 T(n) = maxq(T(q) + T(n − 1 − q)) + Cn 可知最坏情况上界，而每次最不均匀划分能取到 cn2 时间，从而可知最坏情况复杂度 平均情况：可以发现，对任何不超过固定比例 (如每次少比多不超过 1:9) 的划分，复杂度都是 O(n log n)， 利用此估算，设平均复杂度 T(n)，有 T(n) = 1 n ∑n−1 k=0 (T(k) + T(n − 1 − k) + cn) = 2 n ∑n−1 k=0 T(k) + cn。 考虑 nT(n) − (n − 1)T(n − 1) 可估算出 T(n) n+1 ≤ T(n−1) n + 2c n ，利用 1 + · · · + 1 n ∼ log n 可知平均复杂度。 随机快速排序：每次 PARTITION 并非将最右元素作为分割，而是选取随机元素分割以优化性能。 **堆排序与快速排序比较：按照通常 RAM 模型会发现堆排序的复杂度更低，而引进一级缓存 (缓存的量 级在 n 1/3 左右) 时即会有快速排序的复杂度更低。 §2.4 线性时间排序 比较排序的时间下界 比较排序的算法可以用决策树的方式表示，边代表判定过程，而结点代表已经确定顺序的部分。 *决策树中至少需要 n! 个叶结点表示 n! 种判定结果 定理：比较排序的最坏情况时间 Ω(n log n)。 证明：由于一次比较产生一层，比较 h 次的高度为 h，而此时最多容纳 2 h 个叶结点，因此 2 h ≥ n!，从 而 h ≥ log(n!) = Ω(n log n)。 *线性时间排序一定不能直接基于比较 计数 [counting] 排序 思路：对 0 到 k 中的整数组成的数列，只要知道每个整数出现了几次就会知道结果所在的位置。 def COUNTING_SORT(A, B, k): for i <‐ 0 to k C[i] <‐ 0 for i <‐ 1 to length(A) C[A[j]] <‐ C[A[j]] + 1 //C[t] = sum(A==t) for i <‐ 1 to k C[i] <‐ C[i] + C[i‐1] //C[t] = sum(A<=t) for i <‐ length(A) downto 1 B[C[A[j]]] <‐ A[j]
二排序与顺序统计 13 C[A[j]<-C[A[j]·1 *考虑四个循环可发现其复杂度为Θ（十），且为稳定排序。 基数[radix]排序 思路：对整数，按位数从末位向前排序（对每位采用稳定排序算法，如计数排序） 时间复杂度：n个d位数，每位k种取值，计数排序时耗时O〔dn+) *由上方可知，给定n个b位二进制数与正整数r≤b,时间复杂度可以控制在日(6(n+2)/r)内。 桶[bucket】排序 思路：对日到1之间，先划分所有数据到n个不同的“桶”内再进行排序。 def BUCKET_SORT(A): n<-length(A) for i <-1 to n insert A[i]into list B[floor(nA[i])] for i<-0 to n-1 sort list B[i]with insertion sort Print B[i]in order 时间复杂度：针对均匀一致分布才能达到较好效果，最坏情况O(m)。平均性能较好，为Θ()。 2.5中位数与顺序统计 定义：第1小的元素称为第1个顺序统计量，n个元素的低中位数为第【个顺序统计量，高中位 数为第「+11个，一般吠认为低中位数 *寻找最大或最小值时间复杂度必然为()，但同时找最大最小值问题至少可通过「婴1-2次比较完成 证明：记N状态为从未参与过比较，L状态为参与过但只大不小，S为参与过但只小不大，M为参与过且 小大都成为过，则状态间的转换关系为N->L/S-M。所有元素只有一个能保证L/S不变，即为最大/最 小，剩下的都会成为M,总状态转换数为2(n-2)+1+1=2m-2 下面考虑一次比较能造成的状态转换：只有当N与N比较时一定会有两次状态转换，其余在最坏情况下至 多一次状态转换[严谨性间题：整体最坏未必每次都能遇到最坏]。由此最坏情况至少号+(2一2-(2号)= 一2，而由于比较次数一定为整数，需要取上整，即为结果。 算法：先每两位进行比较，将小的放在奇数位置。在偶数位中找到最大值，奇数位中找到最小值即可。 思考：找第二大元素需要的最少比较次数？ 寻找任意第1小元素：类似快速排序，通过PARTITIO后左右元素数量确定应在哪一侧找 def RANDOMIZED_SELECT(A,p,r,i): if p==r: return A[p] q=RANDOMIZED PARTITION(A,p,r) k =q-p +1 if i =k: return A[q]
二 排序与顺序统计 13 C[A[j]] <‐ C[A[j]] ‐ 1 *考虑四个循环可发现其复杂度为 Θ(n + k)，且为稳定排序。 基数 [radix] 排序 思路：对整数，按位数从末位向前排序 (对每位采用稳定排序算法，如计数排序)。 时间复杂度：n 个 d 位数，每位 k 种取值，计数排序时耗时 O(d(n + k)) *由上方可知，给定 n 个 b 位二进制数与正整数 r ≤ b，时间复杂度可以控制在 Θ(b(n + 2r )/r) 内。 桶 [bucket] 排序 思路：对 0 到 1 之间，先划分所有数据到 n 个不同的“桶”内再进行排序。 def BUCKET_SORT(A): n <‐ length(A) for i <‐ 1 to n insert A[i] into list B[floor(nA[i])] for i <‐ 0 to n‐1 sort list B[i] with insertion sort Print B[i] in order 时间复杂度：针对均匀一致分布才能达到较好效果，最坏情况 O(n 2 )。平均性能较好，为 Θ(n)。 §2.5 中位数与顺序统计 定义：第 i 小的元素称为第 i 个顺序统计量，n 个元素的低中位数为第 ⌊ n+1 2 ⌋ 个顺序统计量，高中位 数为第 ⌈ n+1 2 ⌉ 个，一般默认为低中位数。 *寻找最大或最小值时间复杂度必然为 Θ(n)，但同时找最大最小值问题至少可通过 ⌈ 3n 2 ⌉ −2 次比较完成。 证明：记 N 状态为从未参与过比较，L 状态为参与过但只大不小，S 为参与过但只小不大，M 为参与过且 小大都成为过，则状态间的转换关系为 N‐>L/S‐>M。所有元素只有一个能保证 L/S 不变，即为最大/最 小，剩下的都会成为 M，总状态转换数为 2(n − 2) + 1 + 1 = 2n − 2。 下面考虑一次比较能造成的状态转换：只有当 N 与 N 比较时一定会有两次状态转换，其余在最坏情况下至 多一次状态转换 [严谨性问题：整体最坏未必每次都能遇到最坏]。由此最坏情况至少 n 2 + ( 2n−2−(2 n 2 ) ) = 3n 2 − 2，而由于比较次数一定为整数，需要取上整，即为结果。 算法：先每两位进行比较，将小的放在奇数位置。在偶数位中找到最大值，奇数位中找到最小值即可。 思考：找第二大元素需要的最少比较次数？ 寻找任意第 i 小元素：类似快速排序，通过 PARTITION 后左右元素数量确定应在哪一侧找。 def RANDOMIZED_SELECT(A, p, r, i): if p == r: return A[p] q = RANDOMIZED_PARTITION(A, p, r) k = q ‐ p + 1 if i == k: return A[q]