第7章 快速排序
7.1 快速排序
void swap(
int *a,
int *b)
{
int tmp =
*a;
*a =
*b;
*b = tmp;
}
int partition(
int a[],
int low,
int high)
{
int privotKey = a[low];
while(low < high){
while(low < high && a[high] >= privotKey) --high;
swap(&a[low], &a[high]);
while(low < high && a[low] <= privotKey ) ++low;
swap(&a[low], &a[high]);
}
return low;
}
void quickSort(
int a[],
int low,
int high){
if(low < high){
int privotLoc = partition(a, low, high);
quickSort(a, low, privotLoc -
1);
quickSort(a, privotLoc +
1, high);
}
}
7.2 快速排序的性能
快速排序的运行时间依赖于划分是否平衡。 最好情况：partition得到的两个子问题的规模都不大于n/2，递归式为
T(n)=2T(n/2)+Θ(n)
根据主定理，上述递归式的解为
T(n)=Θ(nlgn)
。
7.3 快排的随机版本
int randomized_partition(
int a[],
int low,
int high){
int i = random(low, high);
swap(&a[low], &a[i]);
partition(a, low, high);
}
void randomized_quickSort(
int a[],
int low,
int high){
if(low < high){
int privotLoc = randomized_partition(a, low, high);
randomized_quickSort(a, low, privotLoc -
1);
randomized_quickSort(a, privotLoc +
1, high);
}
}
7.4 快排分析
最坏情况：
T(n)=max{0≤q≤n−1}(T(n)+T(n−q−1))+Θ(n)
猜测
T(n)≤cn2
成立，代入上式，得：
T(n)=max{0≤q≤n−1}(cq2+c(n−q−1)2)+Θ(n)=c∗max{0≤q≤n−1}(q2+(n−q−1)2)+Θ(n)≤c∗(n−1)2/2+Θ(n)≤cn2
期望运行时间：
定义：
zi
是数组A中地i小的元素，
Zij={zi,zi+1,...,zj}
，
Xij=I{zi compare with zj}
，
X=∑n−1i=1∑nj=i+1Xij
E[X]=∑i=1n−1∑j=i+1nE[Xij]=∑i=1n−1∑j=i+1nP(zi compare with zj)
zi
与
zj
会进行比较，当且仅当
Zij
中将被选为主元的第一个元素是
zi
或
zj
。于是有
P(zi compare with zj)=2j−i+1
，所以有
E[X]=∑i=1n−1∑j=i+1n2j−i+1=∑i=1n−1∑k=1n−i2k+1<∑i=1n−1∑k=1n2k=∑i=1n−1O(lgn)=O(nlgn)
