快速排序中常见中轴选择方法及实现代码(二)
一组N个数的中值是第N/2个最大数，中轴的最好选择就是数组的中值。不幸的是，这很难算出。但这样的中值的估计量可以通过随机选取三个元素并用它们的中值作为中轴而得到。事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为中轴。
分割策略：假设数组被排序的范围为left和right，center=（left+right）/2，对a[left]、a[right]和a[center]进行适当排序，取中值为中轴，将最小者放a[left]，最大者放在a[right]，把中轴元与a[right-1]交换，并在分割阶段将i和j初始化为left+1和right-2。然后使用双向描述法，进行快排。
三数中值分割法的实现
初始数据： 6 1 8 9 4 3 5 2 7 0
对三个数进行排序后： 0 1 8 9 4 3 5 2 7 6
中轴与a[right-1]交换： 0 1 8 9 7 3 5 2 4 6
开始扫描： i→ ←j
第一次交换后： 0 1 2 9 7 3 5 8 4 6
i =2 j=7
第二次交换后： 0 1 2 3 7 9 5 8 4 6
i=3 j=5
第三次交换前： 0 1 2 3 7 9 5 8 4 6
i=4,j= 3 3=j i=4
第三次交换后： 0 1 2 3 4 9 5 8 7 6
(与a[right-1]交换)
分割策略的好处
1）将三元素中最小者被分到a[left]、最大者分到a[right]是正确的，因为当快排一趟后，比中轴小的放到左边，而比中轴大的放到右边，这样就在分割的时候把它们分到了正确的位置，减少了一次比较和交换。
2）在前面所说的所有算法中，都有双向扫描时的越界问题，而使用这个分割策略则可以解决这个问题。因为i向右扫描时，必然会遇到不小于中轴的数a[right-1]，而j在向左扫描时，必然会遇到不大于中轴的数a[left]，这样，a[right-1]和a[left]提供了一个警戒标记，所以不需要检查下标越界的问题。
关键实现代码
[cpp]
DataType Median3(DataType *data, int left, int right)
{
//取数据的头、尾和中间三个数，并对他们进行排序
//排序结果直接保存在数组中
int centre = (left + right)/2;
if(data[left] > data[centre])
Swap(data[left], data[centre]);
if(data[left] > data[right])
Swap(data[left], data[right]);
if(data[centre] > data[right])
Swap(data[centre], data[right]);
//把中值，即枢纽与数组倒数第二个元素交换
swap(data[centre], data[right - 1]);
return data[right - 1];//返回枢纽
}
void QSort(DataType *data, int left, int right)
{
//如果需要排序的数据大于3个则使用快速排序
if(right - left >= 3)
{
//取得枢纽的值
DataType centre = Median3(data, left, right);
int begin = left;
int end = right - 1;
while(true)
{
//向后扫描数组
//由于在选择枢纽时，已经把比枢纽值大的数据放在right位置
//所以不会越界
while(data[++begin] < centre);
//向前扫描数组
//由于在选择枢纽时，已经把比枢纽值小的数据放在left位置
//所以不会越界
while(data[--end] > centre);
//把比枢纽小的数据放在前部，大的放到后部
if(begin < end)
Swap(data[begin], data[end]);
else
{
//已经对要排序的数据都与枢纽比较了一次
//把中枢纽保存在适当的位置，因为begin的数一定比枢纽大
//所以把这个数放在数组后面
Swap(data[begin], data[right - 1]);
break;
}
}
QSort(data, left, begin - 1);
QSort(data, begin + 1, right);
}
else //如果要排序的数据很少，少于等于3个，则直接使用冒泡排序
{
BubbleSort(data+left, right - left + 1);
}
}
注意当要排序的数据很少时（小于3个），则不能进行三数取中值，此时直接使用简单的排序（例如冒泡）即可，而且从效率的角度来考虑这也是合理的，因为可以避免函数调用的开销。
五、与中轴相等时的操作
当i或j在扫描中遇到与中轴相等的元素时，是停止扫描还是继续？
我们仍然采用双向扫描法，而且从实践中我们知道，i与j的操作应该相同（停止或继续）否则，一趟快排后，会出现中轴偏向一边的现象。
下面以一下极端的例子来说明：
采用三数中值分割法
初始数据： 2 2 2 2 2 2 2 2 2
分割后： 2 2 2 2 2 2 2 2 2
i→ ←j
1）继续扫描（先不考虑越界）
2 2 2 2 2 2 2 2 2
j i
第一趟快排后： 2 2 2 2 2 2 2 2 2
(a[i]与a[right-1]交换）
我们可以看到，如果继续扫描，出现的将是快排中的最坏情况，分出来的数组极其不平均，时间复杂度为O(N^2)。采用前面的两种快排算法也同样。
2）停止扫描并交换数据