快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是： 1）、设置两个变量I、J，排序开始的时候I：=1，J：=N； 2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]； 3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换； 4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换； 5）、重复第3、4步，直到I=J； 例如：待排序的数组A的值分别是：（初始关键数据X：=49） A[1]     A[2]     A[3]     A[4]     A[5]      A[6]     A[7]：  49        38       65       97       76       13        27 进行第一次交换后：   27        38       65       97       76       13        49 ( 按照算法的第三步从后面开始找 进行第二次交换后：   27        38       49       97       76       13        65 ( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时I：=3 ) 进行第三次交换后：   27        38       13       97       76       49        65 ( 按照算法的第五步将又一次执行算法的第三步从后开始找 进行第四次交换后：   27        38       13       49       76       97        65 ( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 ) 此时再执行第三不的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27        38       13       49       76       97        65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。 快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示： 初始状态                        {49     38     65     97     76     13     27}    进行一次快速排序之后划分为      {27     38     13}     49   {76     97     65} 分别对前后两部分进行快速排序       27     结束         结束    {49    65}    76    49           结束 结束 图6    快速排序全过程1）、设有N（假设N=10）个数，存放在S数组中；2）、在S[1。。N]中任取一个元素作为比较基准，例如取T=S[1]，起目的就是在定出T应在排序结果中的位置K，这个K的位置在：S[1。。K-1]<=S[K]<=S[K+1..N]，即在S[K]以前的数都小于S[K]，在S[K]以后的数都大于S[K]；3）、利用分治思想（即大化小的策略）可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。如具体数据如下，那么第一躺快速排序的过程是：数组下标： 1      2      3      4      5      6      7      8      9      1045     36     18     53     72     30     48     93     15      36I                                                                   J （1）      36     36     18     53     72     30     48     93     15      45（2）      36     36     18     45     72     30     48     93     15      53（3）      36     36     18     15     72     30     48     93     45      53（4）      36     36     18     15     45     30     48     93     72      53（5）      36     36     18     15     30     45     48     93     72      53通过一躺排序将45放到应该放的位置K，这里K=6，那么再对S[1。。5]和S[6。。10]分别进行快速排序。   分而治之方法还可以用于实现另一种完全不同的排序方法，这种排序法称为快速排序（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中的元素。也可以采用其他选择方式来提高排序性能，本章稍后部分将给出这样一种选择。 程序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中的其余代码。 图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）。   */#define MAXN 20 void Carve_up(int array[],int number,int *m){ int i,j,k,middle,temp; i = 0; j = number - 1; k = (i + j) / 2; //在下标i,j,k的数组元素中选取中项 if(array[i] >= array[j] && array[j] >= array[k])  middle = j;  //Array[j]是中项 else if(array[i] >= array[k] && array[k] >= array[j])  middle = k;  //Array[k]是中项 else  middle = i;  //Array[i]是中项 temp = array[middle]; array[middle] = array[i]; while(i != j) {  while(i < j && array[j] >= temp)   j --; //j逐步减小，直到发现一个array[j] < temp为止  if(i < j)  {   array[i] = array[j];   i ++ ;   while(i < j && array[i] <= temp)    i ++ ; //i逐步减小，直到发现一个array[i] > temp为止   if(i < j)   {    array[j] = array[i];    j --;   }  } } array[i] = temp; *m = i; return;}void Quick_Sort(int array[],int number){ int i; if(number > 1) {  Carve_up(array,number,&i);  Quick_Sort(array,i);  Quick_Sort(&array[i + 1],number - i - 1); } return;}void Run_Quick_Sort(){ int i,array[MAXN] = {1,9,3,7,18,2,20,4,16,5,15,6,14,7,13,6,12,8,11,10}; Quick_Sort(array,MAXN); for(i = 0;i < MAXN;i++)  printf("%3d",array[i]);}//:============================“快速排序算法”问题的分而治之算法=========================== int main(int argc, char* argv[]){ Run_Quick_Sort();  printf("\n应用程序运行结束！\n"); return 0;}

评论