第七章快速排序

59 阅读 0 评论 39 点赞

我是靠谱客的博主幸福丝袜，最近开发中收集的这篇文章主要介绍第七章快速排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

7.1 快速排序的描述

7.1.-1参照图7-1的方法，说明PARTITION在数组A=<13,19,9,5,12,8,7,4,21,2,6,11>上的操作过程。

这里写图片描述
图解：在一个样例数组上的PARTITION操作过程。数组项A[r]是主元x=11,红褐色阴影部分。浅绿部分的数组元素都在划分的第一部分，其值都不大于x。深绿部分的元素都在划分的第二部分，其值都大于x。无色的元素是还未分入这两部分中的任意一个。

7.1-2 当数组A[p…r]中的元素都相同时，PARTITION返回的q值是什么？修改PARTITION,使得当数组A[p…r]中所有元素的值都相同时，q= ⌊(p+q)/2⌋ 。
1）返回的是r
2)思路：让主元等于首位的元素；i等于p+1，j=r。i指向的元素向左替换，j指向的元素向右替换，最后i和主元替换。

PARTITION(A,p,r)
{
x=A[p]
i=p+1
for j=r to i=j
while(A[i]<x && i!=j)
i++
exchange A[i] and A[j]
i++
while(A[j]>x && i!=j)
j++
exchange A[i] and A[j]
j++
exchange A[i] and A[p]
}

7.1-3 请简要的证明：在规模为n的子数组上，PARTITION的时间复杂度为θ（n）。
它的循环次数为r-p-1次，在规模为n的数组上，循环次数为n-2次
所以PARTITION的时间复杂度为θ（n）

7.1-4 如何修改QUICKSORT,使得它能够以非递增序进行排列？
控制递增排序的是PARTITION而不是QUICKSORT部分，所以要对PARTITION函数进行修改，将里面A[j]<=x变成A[j]>=x即可。

7.2 快速排序的性能

7.2-1 利用代入法证明：正如7.2节开头提到的那样，递归式T(n)=T(n-1)+θ(n)的解为T（n）=θ（ n2 ）。

T (n) = c (n - 1) 2 + n = c n 2 - 2 c n + 1 + n \leq c n 2 c > 1 / 2 的 时 候 成 立

7.2-2 当数组A的所有元素都具有相同值时，QUICKSORT的时间复杂度是什么
θ(n2)

7.2-3 证明：当数组A包含的元素不同，并且是按降序排列的时候，QUICKSORT的时间复杂度为θ（ n2 ）
第一次，划分为0：n
第二次，划分为0：n-1
……
最后进行次数（1+n）n2

7.2-4 银行一般会按照交易时间来记录某一账户的交易情况。但是，很多人却喜欢收到的银行对账单是按照支票号码的顺序来排列的。这是因为，人们通常都是按照支票号码的顺序来开出支票的，而商人也通常都是根据支票编号的顺序兑付支票。这一问题是将按交易时间排序的序列转换成按支票号排序的序列，它实质上是一个对几乎有序的输入序列进行排序的问题。请证明：在这个问题上，INSERTION-SORT 的性能往往要优于QUICKSORT？

QUICKSORT(a,p,r)
if p<r
q=PARTITION(A,p,r)
QUICKSORT(A,p,q-1)
QUICKSORT(A,q+1,r)
INSERTION-SORT(A)
for j=2 to A.length
key=A[j]
//Insert A[j] into the sorted sequence A[1…j-1]
i=j-1
while i>0 and A[i]>key
A[i+1]=A[i]
i=i-1
A[i+1]=key

假如支票序列是排好序的
但是INSERTION-SORT时间复杂度为n
而QUICKSORT时间复杂度为 n2
所有INSERTION-SORT的性能往往要优于QUICKSORT

7.2-5 假设快速排序的每一层所做的划分的比例都是1-α：α，其中 0<α≤1/2 且是一个常数。试证明：在相应的递归树中，叶节点的最小深度大约是-lgn/lgα ，最大深度大约是-lgn/lg(1-α)(无需考虑整数舍入问题)。
这里写图片描述
最小深度：设最大深度为m，每次向α分割方向下降，m次分割后仅剩1个元素 n*α^m = 1， α^m = 1/n ，两边取对数 mlgα = lg1-lgn ，m = -lgn/lgα
最大深度：同理 n*((1-α)^m) = 1， (1-α)^m = 1/n ，取对数 mlg(1-α) = -lgn 即 m = -lgn/lg(1-α)

7.3 快速排序的随机化版本

7.3-1 为什么我们分析随机化算法的期望运行时间，而不是其最坏运行时间呢？
因为想快速排序这样的算法，很少处于最坏运行时间。

7.3-2 在RANDOMIZED-QUICKSORT 的运行过程中，在最坏情况下，随机数生成器RANDOM 被调用了多少次？最好情况下呢？以θ的形式给出你的答案。
最坏情况下n-1次，θ（n）
最好情况下是lgn次，θ（lgn）

7.4 快速排序分析

7.4-1 证明：在递归式

T (n) = max 0 \leq q \leq n - 1 (T (q) + T (n - q - 1)) + θ (n)

中，T(n)=Ω（

n2 ）

用代入法证明：

T (n) = c q 2 + c (n - q - 1) 2 + θ (n) T (n) \geq c (n - q - 1) 2

所以T(n)=Ω（

n2 ）

7.4-2 证明：在最好的情况下，快速排序的运行时间为Ω（nlgn）。
最好的情况即每次都恰好均分，像二叉树一样nlgn。

7.4-3 证明：在q=0，1，…，n-1区间内，当q=0或q=n-1时， q2+(n−q−1)2 取得最大值。

设 f = q 2 + (n - q - 1) 2 ， 用 配 方 法 f = q 2 2 + ( n - q - 1 ) 2 2 + q (n - q - 1) + q 2 2 + ( n - q - 1 ) 2 2 - q (n - q - 1) f = ( n - 1 ) 2 2 + ( 2 q - n + 1 ) 2 2 由 题 意 可 知 ， 当 q = n - 1 时 取 得 最 小 值 当 n = 0 时, q = n - 1 = - 1, 而 q 又 是 大 于 0 的 ， 不 可 能 存 在 故 当 q = 0 ， 或 q = n - 1 时 ， 取 得 最 大 值 。

7.4-4 证明：RANDOMIZED-QUICKSORT期望运行时间是Ω（nlgn）。

由 书 上 可 知 : E [X] = \sum i = 1 n - 1 \sum j = i + 1 n 2 j - i + 1 E [X] = \sum i = 1 n - 1 \sum j = i + 1 n 2 j - i + 1 = \sum i = 1 n - 1 \sum k = 1 n - i 2 k + 1 \geq \sum i = 1 n - 1 \sum k = 2 n - i + 1 2 k = \sum i = 1 n - 1 Ω （ l g n ） = Ω （ n l g n ）

7.4-5 当输入数据已经“几乎有序”时，插入排序速度很快。在实际应用中，我们可以利用这一特点来提高快速排序的速度。当对一个长度小于k的子数组调用快速排序时，让它不做任何排序就返回。当上层的快速排序调用返回后，对整个数组运行插入排序来完成排序过程。试证明：这一排序算法的期望时间复杂度为O（nk+nlg(n/k)）。分别从理论和实践的角度说明我们应该如何选择k。