java写入word换行符:9.9.3 快速排序优化（1）

9.9.3 快速排序优化（1）

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

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所示。

图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]交换，此时就不容易出现这样的情况，这被称为随机选取枢轴法。应该说，这在某种程度上，解决了对于基本有序的序列快速排序时的性能瓶颈。不过，随机就有些撞大运的感觉，万一没撞成功，随机到了依然是很小或很大的关键字怎么办呢？

再改进，于是就有了三数取中（medianofthree）法。即取三个关键字先进行排序，将中间数作为枢轴，一般是取左端、右端和中间三个数，也可以随机选取。这样至少这个中间数一定不会是最小或者最大的数，从概率来说，取三个数均为最小或最大数的可能性是微乎其微的，因此中间数位于较为中间的值的可能性就大大提高了。由于整个序列是无序状态，随机选取三个数和从左中右端取三个数其实是一回事，而且随机数生成器本身还会带来时间上的开销，因此随机生成不予考虑。

我们来看看取左端、右端和中间三个数的实现代码，在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[lo /* 用子表的第一个记录作枢轴记录 */ 

试想一下，我们对数组{9,1,5,8,3,7,4,6,2}，取左9、中3、右2来比较，使得L.r[low]=3，一定要比9和2来得更为合理。

三数取中对小数组来说有很大的概率选择到一个比较好的pivotkey，但是对于非常大的待排序的序列来说还是不足以保证能够选择出一个好的pivotkey，因此还有个办法是所谓九数取中（medianofnine），它先从数组中分三次取样，每次取三个数，三个样品各取出中数，然后从这三个中数当中再取出一个中数作为枢轴。显然这就更加保证了取到的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{  
while（lowr[high]>=pivotkey）  
high--;  
L->r[low]=L->r[high]; /* 采用替换而不是交换的方式进行操作 */  
while（lowr[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所示。
图9-9-9