c语言算法 - 分而治之算法 - 快速排序

核心提示：程序14-6 快速排序templatevoid QuickSort(T*a, int n){// 对a[0:n-1]进行快速排序{// 要求a[n] 必需有最大关键值quickSort(a, 0, n-1);templatevoid quickSort(T a[], int l, int r){// 排序a[ l :

程序14-6 快速排序

template
void QuickSort(T*a, int n)
{// 对a[0:n-1]进行快速排序
{// 要求a[n] 必需有最大关键值
quickSort(a, 0, n-1);
template
void quickSort(T a[], int l, int r)
{// 排序a[ l : r ]， a[r+1] 有大值
if(l >= r)return;
int i = l, // 从左至右的游标
j = r + 1; // 从右到左的游标
T pivot = a[l];
// 把左侧>= pivot的元素与右侧<= pivot 的元素进行交换
while(true){
do {// 在左侧寻找>= pivot 的元素
i = i + 1;
} while(a[i] < pivot);
do {// 在右侧寻找<= pivot 的元素
j = j - 1;
} while(a[j] > pivot);
if(i >= j)break; // 未发现交换对象
Swap(a[i], a[j]);
}
// 设置p i v o t
a[l] = a[j];
a[j] = pivot;
quickSort(a, l, j-1); // 对左段排序
quickSort(a, j+1, r); // 对右段排序
}

若把程序1 4 - 6中d o - w h i l e条件内的<号和>号分别修改为< =和> =，程序1 4 - 6仍然正确。实验结果表明使用程序1 4 - 6的快速排序代码可以得到比较好的平均性能。为了消除程序中的递归，必须引入堆栈。不过，消除最后一个递归调用不须使用堆栈。消除递归调用的工作留作练习（练习1 3）。程序1 4 - 6所需要的递归栈空间为O(n)。若使用堆栈来模拟递归，则可以把这个空间减少为O( l o gn)。在模拟过程中，首先对left和right中较小者进行排序，把较大者的边界放入堆栈中。在最坏情况下l e f t总是为空，快速排序所需的计算时间为(n2 )。在最好情况下， l e f t和r i g h t中的元素数目大致相同，快速排序的复杂性为(nl o gn)。令人吃惊的是，快速排序的平均复杂性也是(nl o gn)。

定理2-1 快速排序的平均复杂性为(nl o gn)。

证明用t(n)代表对含有n个元素的数组进行排序的平均时间。当n≤1时，t(n)≤d，d为某一常数。当n <1时，用s 表示左段所含元素的个数。由于在中段中有一个支点元素，因此右段中元素的个数为n-s- 1。所以左段和右段的平均排序时间分别为t(s), t(n-s- 1 )。分割数组中元素所需要的时间用cn 表示，其中c 是一个常数。因为s 有同等机会取0 ~n- 1中的任何一个值.

如对（2 - 8）式中的n 使用归纳法，可得到t(n)≤kn l o ge n，其中n> 1且k=2(c+d)，e～2 . 7 1 8为自然对数的基底。在归纳开始时首先验证n= 2时公式的正确性。根据公式（1 4 - 8），可以得到t( 2 )≤2c+ 2d≤k nl o ge 2。在归纳假设部分，假定t(n)≤kn l o ge n（当2≤n＜m 时，m 是任意一个比2大的整数＝.

图1 4 - 1 0对本书中所讨论的算法在平均条件下和最坏条件下的复杂性进行了比较。