c语言算法 – 分而治之算法 – 快速排序
副标题#e#
分而治之要领还可以用于实现另一种完全差异的排序要领，这种排序法称为快速排序（quick sort）。在这种要领中， n个元素被分成三段（组）：左段l e f t，右段r i g h t和中段m i d d l e。中段仅包括一个元素。左段中各元素都小于便是中段元素，右段中各元素都大于便是中段元素。因此l e f t和r i g h t中的元素可以独立排序，而且不必对l e f t和r i g h t的排序功效举办归并。m i d d l e中的元素被称为支点( p i v o t )。图1 4 – 9中给出了快速排序的伪代码。
/ /利用快速排序要领对a[ 0 :n- 1 ]排序
从a[ 0 :n- 1 ]中选择一个元素作为m i d d l e，该元素为支点
把余下的元素支解为两段left和r i g h t，使得l e f t中的元素都小于便是支点，而right中的元素都大于便是支点
递归地利用快速排序要领对left举办排序
递归地利用快速排序要领对right举办排序
所得功效为l e f t + m i d d l e + r i g h t
图14-9 快速排序的伪代码
考查元素序列[ 4 , 8 , 3 , 7 , 1 , 5 , 6 , 2 ]。假设选择元素6作为支点，则6位于m i d d l e；4，3，1，5，2位于l e f t；8，7位于r i g h t。当left 排好序后，所得功效为1，2，3，4，5；当r i g h t排好序后，所得功效为7，8。把right中的元素放在支点元素之后， l e f t中的元素放在支点元素之前，即可获得最终的功效[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。
把元素序列分别为l e f t、m i d d l e和r i g h t可以当场举办（见措施1 4 – 6）。在措施1 4 – 6中，支点老是取位置1中的元素。也可以回收其他选择方法来提高排序机能，本章稍后部门将给出这样一种选择。
#p#副标题#e#
措施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对本书中所接头的算法在平均条件下和最坏条件下的巨大性举办了较量。
要领最坏巨大性平均巨大性
冒泡排序n2 n2
计数排序n2 n2
插入排序n2 n2
选择排序n2 n2
堆排序nl o gn nl o gn
合并排序nl o gn nl o gn
快速排序n2 nl o gn
图14-10 各类排序算法的较量
中值快速排序（median-of-three quick sort）是措施1 4 – 6的一种变革，这种算法有更好的平均机能。留意到在措施1 4 – 6中老是选择a[ 1 ]做为支点，而在这种快速排序算法中，可以不必利用a[ 1 ]做为支点，而是取{a[1],a[(1+r)/2],a[r]}中巨细居中的谁人元素作为支点。譬喻，如果有三个元素，巨细别离为5，9，7，那么取7为支点。为了实现中值快速排序算法，一种最简朴的方法就是首先选出中值元素并与a[1]举办互换，然后操作措施1 4 – 6完成排序。假如a[ r ]是被选出的中值元素，那么将a[1] 与a[r]举办互换，然后将a[ 1 ]（即本来的a[ r ]）赋值给措施1 4 – 6中的变量p i v o t，之后继承执行措施1 4 – 6中的其余代码。
#p#分页标题#e#
图2 – 11中别离给出了按照尝试所获得的合并排序、堆排序、插入排序、快速排序的平均时间。对付每一个差异的n, 都随机发生了至少1 0 0组整数。随机整数的发生是通过重复挪用s t d l i b . h库中的r a n d o m函数来实现的。假如对一组整数举办排序的时间少于1 0个时钟滴答，则继承对其他组整数举办排序，直到所用的时间不低于1 0个时钟滴答。在图2 – 11中的数据包括发生随机整数的时间。对付每一个n，在各类排序法顶用于发生随机整数及其他开销的时间是沟通的。因此，图2 – 11中的数据对付较量各类排序算法是很有用的。
对付足够大的n，快速排序算法要比其他算法效率更高。从图中可以看到快速排序曲线与插入排序曲线的交点横坐标比2 0略小，可通过尝试来确定这个交点横坐标的准确值。可以别离用n = 1 5 , 1 6 , 1 7 , 1 8 , 1 9举办尝试，以寻找准确的交点。令准确的交点横坐标为nBr e a k。当n≤nBreak 时，插入排序的平均机能最佳。当n＞nBreak 时，快速排序机能最佳。当n＞nBreak 时，把插入排序与快速排序组合为一个排序函数，可以提高快速排序的机能，实现要领是把措施1 4 – 6中的以下语句：
if(l >= r)r e t u r n ;
替换为
if(r-1
这里I n s e r t i o n S o r t( a , l , r )用来对a[ 1 : r ]举办插入排序。丈量修改后的快速排序算法的机能留作操练（操练2 0）。用更小的值替换n B r e a k有大概使机能进一步提高（见操练2 0）。
大大都尝试表白，当n＞c时（c为某一常数），在最坏环境下合并排序的机能也是最佳的。而当n≤c时，在最坏环境下插入排序的机能最佳。通过将插入排序与合并排序殽杂利用，可以提高合并排序的机能（操练2 1）。
