快速排序（二）

快速排序优化
        刚才讲的快速排序还是有不少可以改进的地方，我们来看一些优化的方案。

1.优化选取枢轴
        如果我们选取的pivotkey是处于整个序列的中间位置，那么我们可以将整个序列分成小数集合和大数集合了。但注意，我刚才说的是“如果……是中间”，那么假如我们选取的pivotkey不是中间数如何呢？比如我们前面讲冒泡和简单选择排序一直用到的数组{9,1,5,8,3,7,4,6,2}，由代码第4行“pivotkey=L->r[low];”知道，我们应该选取9作为第一个枢轴pivotkey。此时，经过一轮“pivot=Partition(L,1,9);”转换后，它只是更换了9与2的位置，并且返回9给pivot，整个系列并没有实质性的变化。如图9-9-8。
 

        就是说，代码第4行“pivotkey=L->r[low];”变成了一个潜在的性能瓶颈。排序速度的快慢取决于L.r[1]的关键字处在整个序列的位置，L.r[1]太小或者太大，都会影响性能(比如第一例子中的50就是一个中间数，而第二例子的9就是一个相对整个序列过大的数)。因为在现实中，待排序的系列极有可能是基本有序的，此时，总是固定选取第一个关键字（其实无论是固定选取哪一个位置的关键字）作为首个枢轴就变成了极为不合理的作法。
        改进办法，有人提出，应该随机获得一个low与high之间的数rnd，让它的关键字L.r[rnd]与L.r[low]交换，此时就不容易出现这样的情况。这被称为随机选取枢轴法。应该说，这在某种程度上，解决了对于基本有序的序列快速排序时的性能瓶颈。不过，随机就有些撞大运的感觉，万一没撞成功，随机到了依然是很小或很大的关键字怎么办呢？
        再改进，于是就有了三数取中（median-of-three）法。即取三个关键字先进行排序，将中间数作为枢轴，一般是取左端、右端和中间三个数，也可以随机选取。这样至少这个中间数一定不会是最小或者最大的数，从概率来说，取三个数均为最小或最大数的可能性是微乎其微的，因此中间数位于较为中间的值的可能性就大大提高了。由于整个序列是无序状态，随机选取三个数和从左中右端取三个数其实是一回事，而且随机数生成器本身还会带来时间上的开销，因此随机生成不予考虑。
        我们来看看取左端、右端和中间三个数的实现代码，在Partition函数代码的第3行与第4行之间增加这样一段代码。

 

3 int pivotkey;

 int m = low + (high - low) / 2;  /* 计算数组中间的元素的下标 */  
 if (L->r[low]>L->r[high])   
  swap(L,low,high);    /* 交换左端与右端数据，保证左端较小 */
 if (L->r[m]>L->r[high])
  swap(L,high,m);    /* 交换中间与右端数据，保证中间较小 */
 if (L->r[m]>L->r[low])
  swap(L,m,low);    /* 交换中间与左端数据，保证左端较小 */
 
 /* 此时L.r[low]已经为整个序列左中右三个关键字的中间值。*/
4 pivotkey=L->r[low];    /* 用子表的第一个记录作枢轴记录 */

 

        试想一下，我们对数组{9,1,5,8,3,7,4,6,2}，取左9，中3，右2来比较，使得L.r[low]=3，一定要比9和2要来得更为合理。
        三数取中对小数组来说有很大的概率选择到一个比较好的pivotkey，但是对于非常大的待排序的序列来说还是不足以保证能够选择出一个好的pivotkey，因此还有个办法是所谓九数取中（median-of-nine），它是先从数组中分三次取样，每次取三个数，三个样品各取出中数，然后从这三个中数当中再取出一个中数作为枢轴。显然这就更加保证了取到的pivotkey是比较接近中间值的关键字。有兴趣的同学可以自己去实现一下代码，这里不再详述了。

2. 优化不必要的交换
        观察图9-9-1～图9-9-6，我们发现，50这个关键字，其位置变化是1→9→3→6→5，可其实，它的最终目标就是5，当中的交换其实是不需要的。因此我们对Partition函数的代码再进行优化。

/* 快速排序优化算法 */
int Partition1(SqList *L,int low,int high)
{ 
 int pivotkey;
 //这里省略三数取中代码
 pivotkey=L->r[low];  /* 用子表的第一个记录作枢轴记录 */
 L->r[0]=pivotkey;   /* 将枢轴关键字备份到L->r[0] */
 while(low<high)   /* 从表的两端交替地向中间扫描 */
 { 
   while(low<high&&L->r[high]>=pivotkey)
   high--;
   L->r[low]=L->r[high]; /* 采用替换而不是交换的方式进行操作 */
   while(low<high&&L->r[low]<=pivotkey)
   low++;
   L->r[high]=L->r[low]; /* 采用替换而不是交换的方式进行操作 */
 }
 L->r[low]=L->r[0];   /* 将枢轴数值替换回L.r[low] */
 return low; /* 返回枢轴所在位置 */
}

 

        注意代码中高亮部分的改变。我们事实将pivotkey备份到L.r[0]中，然后在之前是swap时，只作替换的工作，最终当low与high会合，即找到了枢轴的位置时，再将L.r[0]的数值赋值回L.r[low]。因为这当中少了多次交换数据的操作，在性能上又得到了部分的提高。如图9-9-9所示。
 

 

3. 优化小数组时排序方案
        对于一个数学科学家，博士生导师，他可以攻克世界性的难题，可以培养最优秀的数学博士，但让他去教小学生“1+1=2”的算术课程，那还真未必会比常年在小学学校里耕耘的数学老师教得好。换句话说，大材小用有时会变得反而不好用。刚才我谈到了对于非常大的数组的解决办法。那么相反的情况，如果数组非常小，其实快速排序反而不如直接插入排序来得更好（直接插入是简单排序中性能最好）。其原因在于快速排序用到了递归操作，在大量数据排序时，这点性能影响相对于它的整体算法优势而言是可以忽略的，但如果数组只有几个记录需要排序时，这就成了一个大炮打蚊子的大问题。因此我们需要改进一下QSort函数。

#define MAX_LENGTH_INSERT_SORT 7  /* 数组长度阀值 */
/* 对顺序表L中的子序列L.r[low..high]作快速排序 */
void QSort(SqList &L,int low,int high)
{ 
 int pivot;
 if((high-low)>MAX_LENGTH_INSERT_SORT) /*当high-low大于常数时快速排序*/
 {
  pivot=Partition(L,low,high);  /* 将L.r[low..high]一分为二，算出枢轴值pivot */
  QSort(L,low,pivot-1);   /* 对低子表递归排序 */
  QSort(L,pivot+1,high);   /* 对高子表递归排序 */
 }
 else        /* 当high-low小于等于常数时用直接插入排序 */
  InsertSort(L); 
}

 

        我们增加了一个判断，当high-low不大于某个常数时（有资料认为7比较合适，也有认为50更合理，实际应用可适当调整），就用直接插入排序，这样就能保证最大化的利用两种排序的优势来完成排序工作。

4. 优化递归操作
        大家知道，递归对性能是有一定影响的，QSort函数在其尾部有两次递归操作。如果待排序的序列划分极端不平衡，递归的深度将趋近于n，而不是平衡时的log₂n，这就不仅仅是速度快慢的问题了。栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。因此如果能减少递归，将会大大提高性能。
        于是我们对QSort实施尾递归优化。来看代码。

/* 对顺序表L中的子序列L.r[low..high]作快速排序 */
void QSort1(SqList *L,int low,int high)
{ 
 int pivot;
 if((high-low)>MAX_LENGTH_INSERT_SORT)
 {
  while(low<high)
  {
   pivot=Partition1(L,low,high); /*  L.r[low..high]一分为二,算出枢轴值pivot */
   QSort1(L,low,pivot-1);   /* 对低子表递归排序 */
   low=pivot+1;     /* 尾递归 */
  }
 }
 else
  InsertSort(L);
}

 

        当我们将if改成while后（见高亮代码部分），因为第一次递归以后，变量low就没有用处了，所以可以将pivot+1赋值给low，再循环后，来一次Partition(L,low,high)，其效果等同于“QSort(L,pivot+1,high);”。结果相同，但因采用迭代而不是递归的方法可以缩减堆栈深度，从而提高了整体性能。
在现实的应用中，比如C++、java、PHP、C#、VB、Javascript等等都有对快速排序算法的实现 ，实现方式上略有不同，但基本上都是在我们讲解的快速排序法基础上的精神体现。

        我们现在学过的排序算法，有按照实现方法分类命名的，如简单选择排序、直接插入排序、归并排序，有按照其排序的方式类比现实世界命名的，比如冒泡排序、堆排序，还有用人名命名的，比如希尔排序。但是刚才我们讲的排序，却用“快速”来命名，这也就意味着只要再有人找到更好的排序法，此“快速”就会名不符实，不过，至少今天，TonyHoare发明的快速排序法经过多次的优化后，在整体性能上，依然是排序算法王者。我们应该要好好研究并掌握它。