第七章快速排序

本文主要是介绍第七章快速排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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= $\lfloor (p+q)/2 \rfloor$ 。
1）返回的是r
2)思路：让主元等于首位的元素；i等于p+1，j=r。i指向的元素向左替换，j指向的元素向右替换，最后i和主元替换。

PARTITION(A,p,r)
{x=A[p]i=p+1for j=r to i=jwhile(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）=θ（ $n^2$ ）。

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

$T(n)=c(n-1)^2+n=cn^2-2cn+1+n\le cn^2\\c>1/2的时候成立$

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

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

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

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

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

7.2-5 假设快速排序的每一层所做的划分的比例都是1-α：α，其中 $0< α\le 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-α)