9.9.2 快速排序算法 快速排序（Quick Sort）的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。 从字面上感觉不出它的好处来。假设现在要对数组{50,10,90,30,70,40,80,60,20}进行排序。我们通过代码的讲解来学习快速排序的精妙。 我们来看代码。
/* 对顺序表L作快速排序 */ void QuickSort(SqList *L) { QSort(L,1,L->length); }
又是一句代码，和归并排序一样，由于需要递归调用，因此我们外封装了一个函数。现在我们来看QSort的实现。
/* 对顺序表L中的子序列L->r[low..high]作快速排序 */ void QSort(SqList *L,int low,int high) { int pivot; if(low
从这里，你应该能理解前面代码“QSort(L,1,L->length);”中1和L->length代码的意思了，它就是当前待排序的序列最小下标值low和最大下标值high。 这一段代码的核心是“pivot=Partition(L,low,high);”在执行它之前，L.r的数组值为{50,10,90,30,70,40,80,60,20}。Partition函数要做的，就是先选取当中的一个关键字，比如选择第一个关键字50，然后想尽办法将它放到一个位置，使得它左边的值都比它小，右边的值比它大。我们将这样的关键字称为枢轴（pivot）。 在经过Partition(L,1,9)的执行之后，数组变成{20,10,40,30,50,70,80,60,90}，并返回值5给pivot，数字5表明50放置在数组下标为5的位置。此时，计算机把原来的数组变成了两个位于50左和右小数组{20,10,40,30}和{70,80,60,90}，而后的递归调用“QSort(L,1,5-1);”和“QSort(L,5+1,9);”语句，其实就是在对{20,10,40,30}和{70,80,60,90}分别进行同样的Partition操作，直到顺序全部正确为止。 到了这里，应该说理解起来还不算困难。下面我们就来看看快速排序最关键的Partition函数实现是怎么样的。
/* 交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置 */ /* 此时在它之前(后)的记录均不大(小)于它。 */ 1 int Partition(SqList *L,int low,int high) 2 { 3 int pivotkey; 4 pivotkey=L->r[low]; /* 用子表的第一个记录作枢轴记录 */ 5 while(low
1) 程序开始执行，此时low=1，high=L.length=9。第4行，我们将L.r[low]=L.r[1]=50赋值给枢轴变量pivotkey，如图9-9-1所示。
2) 第5～13行为while循环，目前low=1
5) 第10行，当L.r[low]= L.r[1]=20，pivotkey=50，L.r[low]50，退出循环。 6) 第12行，交换L.r[low]=L.r[3]与L.r[high]=L.r[9]的值，使得L.r[3]=50，L.r[9]=90。此时相当于将一个比50大的值90交换到了50的右边。注意此时low已经指向了3，如图9-9-3所示。
7) 继续第5行，因为low=3
10) 第10行，当L.r[low]= L.r[3]=40，pivotkey=50，L.r[low]50，退出循环。 11) 第12行，交换L.r[low]=L.r[5]=70与L.r[high]=L.r[6]=50的值，使得L.r[5]=50，L.r[6]=70，如图9-9-5所示。
12) 再次循环。因low=5
13) 最后第14行，返回low的值5。函数执行完成。接下来就是递归调用“QSort(L,1,5-1);”和“QSort(L,5+1,9);”语句，对{20,10,40,30}和{70,80,60,90}分别进行同样的Partition操作，直到顺序全部正确为止。我们就不再演示了。 通过这段代码的模拟，大家应该能够明白，Partition函数，其实就是将选取的pivotkey不断交换，将比它小的换到它的左边，比它大的换到它的右边，它也在交换中不断的更改自己的位置，直到完全满足这个要求为止。
9.9.3 快速排序复杂度分析 我们来分析一下快速排序法的性能。快速排序的时间性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。如图9-9-7，它是{50,10,90,30,70,40,80,60,20}在快速排序过程中的递归过程。由于我们的第一个关键字是50，正好是待排序的序列的中间值，因此递归树是平衡的，此时性能也比较好。
在最优情况下，Partition每次都划分得很均匀，如果排序n个关键字，其递归树的深度就为⌊log2n⌋+1（⌊x⌋表示不大于x的最大整数），即仅需递归log2n次，需要时间为T(n)的话，第一次Partiation应该是需要对整个数组扫描一遍，做n次比较。然后，获得的枢轴将数组一分为二，那么各自还需要T(n/2)的时间（注意是最好情况，所以是平分两半）。于是不断的划分下去，我们就有了下面的不等式推断： T(n)≤2T(n/2) +n，T(1)=0 T(n)≤2(2T(n/4)+n/2) +n=4T(n/4)+2n T(n)≤4(2T(n/8)+n/4) +2n=8T(n/8)+3n …… T(n)≤nT(1)+(log2n)×n= O(nlog2n)
也就是说，在最优的情况下，快速排序算法的时间复杂度为O(nlogn)。 在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。此时需要执行n-1次递归调用，且第i次划分需要经过n-i次关键字的比较才能找到第i个记录，也就是枢轴的位置，因比较次数为
，最终其时间复杂度为O(n2)。 平均的情况，设枢轴的关键字应该在第k的位置（1≤k≤n），那么
由数学归纳法可证明，其数量级为O(nlogn)。 就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n-1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。 可惜的是，由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。(下篇将讲解快速排序的各种优化)
最新评论