快速排序中常见中轴选择方法及实现代码

57 阅读 0 评论 38 点赞

我是靠谱客的博主无情黄豆，最近开发中收集的这篇文章主要介绍快速排序中常见中轴选择方法及实现代码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、选取最后一个元素

在我们的课本中，看到最多的就是选择第一个元素作为中轴，但是在很多书上却选择最后一个元素作为中轴。下面就让我们来一睹选取最后一个元素作为中轴的快排。

注：本文中的所有算法都采用双向扫描法，即，设两个下标i和j，i和右扫描，j向左扫描，直到i不小于j。而当下标为i的数小于中轴时，跳过并继续向右扫描，否则停止扫描，并开始j的向左扫描，相对地，当下标为j的数大于中轴时，跳过并继续向右扫描，否则停止扫描，然后交换下标为i和j的两个数，并从下一个位置继续两个方向的扫描，直到i不小于j。最后把中轴与下标为i的元素交换即完成一趟的快排。

下面就以最后一个元素作为中轴来说明。

初始数据为： 8 1 4 9 0 3 5 2 7 6
中轴为：6，第一趟快排的情景如下：

8 1 4 9 0 3 5 2 7 6

↑ ↑

i→ ←j
第一次交换后：
2 1 4 9 0 3 5 8 7 6
↑ ↑
i j

第二次交换后：
2 1 4 5 0 3 9 8 7 6
↑ ↑
i j
第三次交换前：
2 1 4 5 0 3 9 8 7 6
↑ ↑
j i
将下标为i的元素与最后一个元素（中轴）交换
即，一趟快排后：
2 1 4 5 0 3 6 8 7 9
对左边的数组和右边的数组重复上述过程。

选取最后一个元素作为中轴的好处是简单直观，操作一致。因为我们通常把下标为i的元素与中轴元素作为交换，而i则总是指向比中轴大的元素，而把大的元素放到后面总是合理的。

二、双向描述法中的越界问题

快速排序中都非常喜欢使用双向扫描法，然而这个方法却存在一个越界问题，考虑如下的情况：
8 1 4 6 9 3 5 2 7 0
i→ ←j

当我们选取最后一个元素作为中轴时，j向左扫描，一直到找到一个比0小的数，但是它却是数组中的最小值，所以j会一直向左走，直到越界。

这个问题无论是使用第一个元素作为中轴，还是使用最后一个元素作为中轴都会存在。所以，在双向描述中，必然有一个方向（远离中轴的方法）要做越界检查。

选取最后一个元素作为中轴的快排的关键代码

void QSort(DataType *data, int left, int right)
{
    //如果数据的个小数为1或0则不需要排序
    if(left >= right)
        return;
    //取最后一个元素作为枢纽
    DataType centre = data[right];
    int i = left;
    int j = right-1;
    while(true)
    {
        //从前向后扫描，找到第一个小于枢纽的值，
        //在到达数组末尾前，必定结果循环,因为最后一个值为centre
        while(data[i] < centre)
            ++i;
        //从后向前扫描，此时要检查下标，防止数组越界
        while(j >= left && data[j] > centre)
            --j;
        //如果没有完成一趟交换，则交换
        if(i < j)
            Swap(data[i++], data[j--]);
        else
            break;
    }
    //把枢纽放在正确的位置
    Swap(data[i], data[right]);
    QSort(data, left, i - 1);
    QSort(data, i + 1, right);
}

三、随机选元法

我们知道，在快排中，中轴的选择对于算法的效率是非常重要的，选择一个好的中轴选择策略会使算法的效率显著提高。

无论是前面说的选取第一个元素还是最后一个元素作为中轴，其实都是一个坏的选元方法。因为当元素基本有序时，这两种方法都会使算法的效率非常低，最坏情况下，是O(n^2)。

随机选元法的思路：使用随机数生成函数生成一个随机数rand，随机数的范围为[left, right]，并用此随机数为下标对应的元素a[rand]作为中轴，并与最后一个元素a[right]交换，然后进行与选取最后一个元素作为中轴的快排一样的算法即可。

随机选元法仍然存在扫描越界问题，所以在远离中轴的方法上仍然需要检查下标。

随机选元法的关键代码

void QSort(DataType *data, int left, int right)
{
    //如果数据的个小数为1或0则不需要排序
    if(left >= right)
        return;
    //随机选取一个元素作为枢纽，并与最后一个元素交换
    int ic = Random(left, right);
    Swap(data[ic], data[right]);


    DataType centre = data[right];
    int i = left;
    int j = right-1;
    while(true)
    {
        //从前向后扫描，找到第一个小于枢纽的值，
        //在到达数组末尾前，必定结果循环,因为最后一个值为centre
        while(data[i] < centre)
            ++i;
        //从后向前扫描，此时要检查下标，防止数组越界
        while(j >= left && data[j] > centre)
            --j;
        //如果没有完成一趟交换，则交换
        if(i < j)
            Swap(data[i++], data[j--]);
        else
            break;
    }
    //把枢纽放在正确的位置
    Swap(data[i], data[right]);
    QSort(data, left, i - 1);
    QSort(data, i + 1, right);
}
inline int Random(int begin, int end)
{
    //产生begin至end，包括begin和end的随机数，即[begin, end]范围的整数
    return rand()%(end - begin + 1) + begin;
}

从上面的代码也可以看出，随机选法与选取最后一个元素作为中轴的方法是非常相近的，只是多了把随机的中轴放到最后的位置的操作。

四、三数中值分割法

一组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]提供了一个警戒标记，所以不需要检查下标越界的问题。

关键实现代码

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）停止扫描并交换数据
初始数据： 2 2 2 2 2 2 2 2 2
分割后： 2 2 2 2 2 2 2 2 2
i→ ←j
第一次交换后： 2 2 2 2 2 2 2 2 2
i=1 j=6
第二次交换后： 2 2 2 2 2 2 2 2 2
i=2 j=5
第三次交换后： 2 2 2 2 2 2 2 2 2
3= i j=4
第四前交换后： 2 2 2 2 2 2 2 2 2
（与a[right-1]交换） 3= j i=4