Quick sort(快速排序)杂谈 1

我们现在使用的排序，很大比例在使用quick sort，因为它是平均速度最快的排序，但与此同时它可能也是坑最深的排序，现在我们就来讨论讨论它，因为内容较多，我计划写多篇，本篇是第一篇。

快排的思路

我们先来介绍一下快排的思路。快排的思路其实很简单，在数组中选一个元素，我们就称呼这个元素为pivot，通过与这个元素的比较，把数组划分成不比pivot大的在一边，不比pivot小的在另一边，于是就分成了两个更小的数据，对它们分别再排序就行了。但是，这个描述特别的含糊，首先是怎么选中间元素，这里面有很多不同的做法。然后就是划分了，这个划分方法非常的多，水也特别深，这里主要介绍最为常见的划分方法。

划分结果分类

首先，就是划分的结果，划分的结果有什么好讲的呢？其实算法的描述只说了划分成不比pivot大的在一边，不比pivot小的在另一边，并没有说等于的数怎么办。事实上，关键就在等于的数怎么处理，你既可以划在其中一边，也可以两边都有，也可以划成3分，中间那块就是等于pivot的，左边是小于等于，右边是大于等于，三种划分结果都是可以的。但是，不能容许的一种情况是划分后只有一块，例如你选的pivot正好是最小的数，于是划分后，整个数组就一块，全是大于等于pivot的，这样很可能导致无限递归，这次划分也白干了。

所以很多人单凭算法思路来实现的时候，往往陷入栈溢出异常，其实就是划分结果上出了问题，并没有保证每次划分后，至少划分成两块。

划分手段分类

划分手段的典型方法至少有5种，本篇介绍其中的4种

1. Lomuto partition scheme

首先我们来看以下代码：

sort_element_t * partition(
    sort_element_t * beg,
    sort_element_t * end)
{
    sort_element_t pivot = *beg;
    sort_element_t * p = beg;
    for (sort_element_t * i = beg + 1; i < end; i++)
    {
        if (*i < pivot)
        {
            sort_element_swap(++p, i);
        }
    }
    sort_element_swap(p, beg);
    return p;
}

void quick_sort_recursive(
    sort_element_t * beg,
    sort_element_t * end)
{
    if (end - beg > 1)
    {
        sort_element_t * p = partition(beg, end);
        quick_sort_recursive(beg, p);
        quick_sort_recursive(p + 1, end);
    }
}

这种划分方法wiki上有描述，叫做 Lomuto partition scheme 它的思路挺好理解，首先p就是划分边界，一开始p = left，遍历数组，发现比pivot小的，就交换到p的位置，并且p++，那么p左边的就全是比p要小的。而在最后面，把pivot交换到p的位置，所以这个方法期望把数组划分成三块，小于pivot的，等于pivot的，大于等于pivot的，而且能保证至少划分出两块（中间那块等于pivot的一定存在，不过只有一个元素）。这个方法的优点是可以通过简单的修改就变成3路划分（小于、等于、大于三块），缺点是它这种划分方法速度最慢，交换次数较多。

2. 不知名字的方法

这种方法来源不明，如果你知道请告诉我，在我看来有点像 Hoare partition scheme 的变种，来看代码

sort_element_t* partition(
    sort_element_t * first,
    sort_element_t * last)
{
    sort_element_t pivot = *first;
    while (first < last)
    {
        while (first < last && pivot < *last)
            last--;
        *first = *last;
        while (first < last && pivot >= *first)
            first++;
        *last = *first;
    }
    *first = pivot;
    return first;
}

void quick_sort_recursive(
    sort_element_t * beg,
    sort_element_t * end)
{
    if (end - beg > 1)
    {
        sort_element_t* p = partition(beg, end - 1);
        quick_sort_recursive(beg, p);
        quick_sort_recursive(p + 1, end);
    }
}

这个方法通过在右边寻找应该放在左边的元素，与pivot交换，然后在左边寻找应该放在右边的元素，再次与pivot交换，这样pivot通过多数交换换到划分位置上。不过上面代码做了一个简单优化，通过赋值而不是直接交换以减少赋值的次数，这种方法在网上非常常见。

3. Hoare partition scheme

后来有个叫做 C.A.R. Hoare 的人发明了这种划分方法，见代码

sort_element_t* partition(
    sort_element_t * first,
    sort_element_t * last)
{
    sort_element_t * begin = first;
    sort_element_t pivot = *first;
    while (first < last)
    {
        while (first < last && *last >= pivot)
            --last;
        while (first < last && pivot >= *first)
            ++first;
        if (first < last)
            sort_element_swap(first, last);
    }
    sort_element_swap(first, begin);
    return first;
}

void quick_sort_recursive(
    sort_element_t * beg,
    sort_element_t * end)
{
    if (end - beg > 1)
    {
        sort_element_t* p = partition(beg, end - 1);
        quick_sort_recursive(beg, p);
        quick_sort_recursive(p + 1, end);
    }
}

注意的是，这个写法和 wiki 上的略有差别。这个方法与前一个的不同点是，通过在左边寻找应该放在右边的元素，而在右边寻找应该放在左边的元素，然后交换。这个方法是以上三种里面速度最快的，但与此同时是坑最多的。例如，原描述是左边找小于，右边找大于的交换，而上面代码的实现是左边找小于等于，右边找大于等于；原描述是先找左边再找右边，上面实现是先找右边再找左边。也就是说，取不取等于号有4种组合，再乘以先左或先右两种，共8种组合，这8种有一些要求pivot取最左边，有一些要求pivot取最右边，有些左右都行，有些pivot任意位置都行。所以当你写这种划分方法的时候，看起来没什么区别的代码，偏偏出现栈溢出各种问题，其实就隐藏在这些细节上。如果你想练习调试的本领，就把这8种组合的划分全写出来，你肯定收获不少。至于哪种组合最佳，我不知道，但我知道最差的组合，就是两边都取等于号的那两种。

这个写法还有一个四路划分的变种，即先划分成以下这样

划分好后再把两端的相等元素交换到中间得到

这里不具体展开，有兴趣可以自行实现

4. VS partition scheme

之所以这么叫是因为我目前只看到在Visual Studio系列STL的std::sort是这么写的，这个写成代码有点长，但思路和上面说的四路划分有点类似，这里简单讲讲它的思路。首先pivot选择在中间，形成这样的状态

找到等于的元素就交换到等于那块的旁边扩大它就行了，核心思想就这样，还有很多其它的细节，这里不展开。这种方法网上几乎没有人这么写，因为写起来确实挺麻烦的。

总结

本篇先介绍到这里，大家写快排练习建议使用 Hoare partition scheme ，如果你觉得你的能力更好，那你可以写 VS partition scheme 自己琢磨一下细节问题，相信你是能写出来的。那么下一篇会介绍优化的部分。