快速排序优化：一步一步优化，将快速排序的性能提升5倍

redhat9i

众所周知，在排序上应用最广泛的便是快速排序。虽然快速排序的最坏时间复杂度能达到O(n^2)，但在实际使用中可以用各种技巧把最坏情况优化掉，使算法在各种情况的排序中令时间复杂度接近O(nlogn)。
本文将通过各种常用的快排优化技巧，一步一步优化朴素快速排序算法。由于篇幅有限，本文只用随机数数组做测试，对于有序数组、逆序数组和含有大量重复元素的数组的优化，本文不表。
<hr/>测试函数

这是测试函数，通过在测试函数中生成随机数数组并对数组进行排序、计算排序时间。
auto test = [](auto& arr, auto& sort)
{
        static default_random_engine e(time(nullptr));
        uniform_int_distribution<remove_reference<decltype(arr)>::type::value_type> rand;
        generate(arr.begin(), arr.end(), [&] {return rand(e); });

        auto tic = clock();
        sort(arr.begin(), arr.end());
        cout << "used time: " << clock() - tic << "ms" << endl;
};

int main(void)
{
        for (size_t n = 1; n <= 1e8; n *= 10)
        {
                cout << "n: " << n << endl;

                vector<unsigned long long> arr(n);
                test(arr, sort<decltype(arr.begin())>);//std::sort
                test(arr, quick_sort<decltype(arr.begin())>);//my fucking sort

                cout << endl;
        }

        return 0;
}
原始快速排序算法

首先我们实现一个最朴素的快速排序算法，一个不含任何添加剂，纯洁无暇的快速排序算法。
template<typename Iter>
void quick_sort(Iter first, Iter last)
{
        if (last - first > 1)
        {
                auto i = first + 1, j = last - 1;

                while (i < j)
                        if (*i < *first)
                                ++i;
                        else if (*j > *first)
                                --j;
                        else
                                swap(*i++, *j--);

                if (*first > *j)
                        swap(*first, *j);

                quick_sort(first, j);
                quick_sort(j, last);
        }
}
测试结果：


可以看到，虽然不及stl的sort快，但至少是在一个量级。
排序前的有序性检查

众所周知，用来排序的数组经常会出现有序片段。对随机数数组而言，当数组大小越小时，出现有序数组的概率越大。又有两个前提：一，对有序数组进行排序是无意义，浪费时间的；二，检查数组是否有序时间复杂度很低，只需要O(n)。基于这两个前提，我们可以在快速排序算法的每个递归子数组排序前进行有序性检查，无序时才进行排序操作。
template<typename Iter>
void quick_sort(Iter first, Iter last)
{
        bool sorted = true;

        for (auto iter = first + 1; iter != last; ++iter)
        {
                if (*iter < *(iter - 1))
                {
                        sorted = false;
                        break;
                }
        }

        if (not sorted && last - first > 1)
        {
                auto i = first + 1, j = last - 1;

                while (i < j)
                        if (*i < *first)
                                ++i;
                        else if (*j > *first)
                                --j;
                        else
                                swap(*i++, *j--);

                if (*first > *j)
                        swap(*first, *j);

                quick_sort(first, j);
                quick_sort(j, last);
        }
}
测试结果：


性能并没有质的提升，因为测试用的是随机数数组，出现有序子数组的概率极小，所以这个优化对这种情况毫无意义。但在实践中，由于大部分数组经常出现有序片段（甚至整个数组都是有序的），所以这个优化提升极大。
三数取中法

众所周知，快速排序算法的具体时间复杂度取决于递归时数组的分割比例。比如说，如果我们在每个递归中都能将数组分成均等的两份，那么算法的时间复杂度将是最佳的O(nlogn)；而如果我们在每个递归中都倒霉地把数组分成大小1和大小n-1这样的两份，快速排序就退化成了递归版的冒泡排序，时间复杂度为O(n^2)。
而数组的分割比例取决于我们选择的基准。基准的选择主要有固定选择法，比如只选第一个元素或最后一个元素（上面的算法就是只选第一个元素）；随机选择法，即从数组中随机选一个元素作为基准，这个方法对随机数数组毫无意义，对相对有序的数组有提升但不是最佳提升；三数取中法，即取三个元素（一般是第一个、最后一个和中间的元素）的中间值，实践中这个方法对各种数组的适应性都很好，所以这里给安排一下。
auto&& quick_sort = [](auto first, auto last)
{
        auto&& three_get_mid = [](auto& a, auto& b, auto& c)
        {
                if (a > b)
                        swap(a, b);
                if (b > c)
                        swap(b, c);
                if (a > c)
                        swap(a, c);
        };

        auto&& sort = [&](auto&& self, auto first, auto last)->void
        {
                bool sorted = true;

                for (auto iter = first + 1; iter != last; ++iter)
                {
                        if (*iter < *(iter - 1))
                        {
                                sorted = false;
                                break;
                        }
                }

                if (not sorted && last - first > 1)
                {
                        auto i = first + 1, j = last - 1;
                        three_get_mid(*(first + ((last - first) >> 1)), *i, *j);

                        while (i < j)
                                if (*i < *first)
                                        ++i;
                                else if (*j > *first)
                                        --j;
                                else
                                        swap(*i++, *j--);

                        if (*first > *j)
                                swap(*first, *j);

                        self(self, first, j);
                        self(self, j, last);
                }
        };

        sort(sort, first, last);
};
测试结果：


有些许提升，已经很接近stl的sort了。由于测试的是随机数数组，所以三数取中法提升效果不明显，但能有这样肉眼可见的提升还是很出乎我意料的。
结合直接插入排序

接下来我们要用猥琐一点的方法来超越stl的sort----即快速排序和直接插入排序的结合。众所周知，元素数量较小的数组对快速排序是不友好的，此时快速排序仍然在开栈递归、选基准、分数组......，而这么辛苦仅仅是为了给那区区几个破元素排序，太不划算了。所以我们要把快速排序递归末端的小数组换成花销比较小的排序算法，避免递归开栈等花销。传统做法是用直接插入排序，虽然其时间复杂度为O(n^2)，但用在小数组上还是可以接受的。
至于这个小数组得多小，测试一下就知道了：


我不知道这个参数是否硬件无关，反正在我电脑上是64最佳。
auto&& quick_sort = [](auto first, auto last)
{
        auto&& insert_sort = [](auto first, auto last)
        {
                for (auto iter = first + 1; iter != last; ++iter)
                {
                        auto temp = *iter;
                        auto jter = iter;

                        while (jter != first && temp < *(jter - 1))
                        {
                                *jter = *(jter - 1);
                                --jter;
                        }

                        *jter = temp;
                }
        };

        auto&& three_get_mid = [](auto& a, auto& b, auto& c)
        {
                if (a > b)
                        swap(a, b);
                if (b > c)
                        swap(b, c);
                if (a > c)
                        swap(a, c);
        };

        auto&& sort = [&](auto&& self, auto first, auto last)->void
        {
                bool sorted = true;

                for (auto iter = first + 1; iter != last; ++iter)
                {
                        if (*iter < *(iter - 1))
                        {
                                sorted = false;
                                break;
                        }
                }

                if (not sorted && last - first > 1)
                {
                        if (last - first > 64)
                        {
                                auto i = first + 1, j = last - 1;
                                three_get_mid(*(first + ((last - first) >> 1)), *i, *j);

                                while (i < j)
                                        if (*i < *first)
                                                ++i;
                                        else if (*j > *first)
                                                --j;
                                        else
                                                swap(*i, *j),
                                                ++i, --j;

                                if (*first > *j)
                                        swap(*first, *j);

                                self(self, first, j);
                                self(self, j, last);
                        }
                        else
                        {
                                insert_sort(first, last);
                        }
                }
        };

        sort(sort, first, last);
};
测试结果：


性能提升明显，并一举超越stl的sort（虽然只有一丁点）。
事实上，传统的快速排序优化还有各种奇技淫巧，如聚集重复元素、尾递归优化（上面的代码编译器一般会自动做尾递归优化）等。但这些都是小提升，早就满足不了我了，接下来......
多线程优化

这个算是开挂了吧，拿多核运算去和单核运算的std::sort做比较......
快速排序用的是分治思想，用基准把数组分为两个子数组去排序，两个子数组又分别分成两个孙数组......我们可以发现，两个子数组的排序操作是独立的、互不影响的，这给了我们多线程优化的机会。简单说，就是分开的两个子数组分别用单独的线程去排序，子数组分成的孙数组也分别用单独的线程去排序......当cpu有多个核心时，算法的性能将有成倍的提升。
值得注意的是，数组的分裂是呈指数爆炸的，即1生2，2生4，4生balabala......如果不加限制，线程数量会直接突破操作系统极限，虽然这个极限可以修改，但线程远远超过cpu核心数的话，不但没有额外加速，还要浪费时间资源去开辟线程。
至于线程数限制多少最合适，测试一下就知道了：


这里的递归深度表示如果未超过这个递归深度，则无脑给子数组的排序开辟线程，如果超过，就不开辟线程了。
测试数据抖动非常大。当可开辟线程的递归深度设为4~10时算法性能最佳。但由于不能保证快速排序递归时子数组的划分每次都是均等的，所以这里取10，因为开辟线程越多，每个线程排序的子数组出现大数组的概率越小，排序的时间越稳定，不易抖动。
我猜这个参数是硬件相关的，跟cpu核心数有关。但我手头上只有一台电脑，难以验证。不过这里可开辟线程递归深度设为10，即数组够大的话，最多会开辟1024个线程，这个数量至少对大部分cpu的利用率都是极高的。
auto&& quick_sort = [](auto first, auto last)
{
        auto&& insert_sort = [](auto first, auto last)
        {
                for (auto iter = first + 1; iter != last; ++iter)
                {
                        auto temp = *iter;
                        auto jter = iter;

                        while (jter != first && temp < *(jter - 1))
                        {
                                *jter = *(jter - 1);
                                --jter;
                        }

                        *jter = temp;
                }
        };

        auto&& three_get_mid = [](auto& a, auto& b, auto& c)
        {
                if (a > b)
                        swap(a, b);
                if (b > c)
                        swap(b, c);
                if (a > c)
                        swap(a, c);
        };

        auto&& sort = [&](auto&& self, auto first, auto last, auto depth)->void
        {
                bool sorted = true;

                for (auto iter = first + 1; iter != last; ++iter)
                {
                        if (*iter < *(iter - 1))
                        {
                                sorted = false;
                                break;
                        }
                }

                if (not sorted && last - first > 1)
                {
                        if (last - first > 64)
                        {
                                auto i = first + 1, j = last - 1;
                                three_get_mid(*(first + ((last - first) >> 1)), *i, *j);

                                while (i < j)
                                        if (*i < *first)
                                                ++i;
                                        else if (*j > *first)
                                                --j;
                                        else
                                                swap(*i, *j),
                                                ++i, --j;

                                if (*first > *j)
                                        swap(*first, *j);

                                if (depth < 10)
                                {
                                        thread t0(self, self, first, j, depth + 1), t1(self, self, j, last, depth + 1);
                                        t0.join();
                                        t1.join();
                                }
                                else
                                {
                                        self(self, first, j, depth + 1);
                                        self(self, j, last, depth + 1);
                                }
                        }
                        else
                        {
                                insert_sort(first, last);
                        }
                }
        };

        sort(sort, first, last, 0);
};
测试结果：


算法的性能已经有了质的飞跃。
但还有一个小瑕疵，数组太小时依然很消耗时间。通过std::sort的对比可以知道，对这个大小的数组进行排序，哪怕是单核排序，也能在瞬间完成，而我的算法却花了数十毫秒。可以肯定的是，这些时间都消耗在了线程开辟和初始化上，因为之前没用多线程时没用这种情况。
因此，当多线程开辟及初始化的性能损耗超过了用多线程带来的性能提升时，用多线程是不必要的。所以对于小数组就没必要用多线程了。至于这个小数组得多小，经过测试，对小于10000的子数组的排序选择不开辟新线程时性能最佳。
此时只要把
if (depth < 10)
{
        thread t0(self, self, first, j, depth + 1), t1(self, self, j, last, depth + 1);
        t0.join();
        t1.join();
}
改成
if (depth < 10 && last - first > 10000)
{
        thread t0(self, self, first, j, depth + 1), t1(self, self, j, last, depth + 1);
        t0.join();
        t1.join();
}
测试结果：


完美，收工！
<hr/>总结

本文通过对快速排序的一步步优化，不断提升算法性能，最后用的多线程魔法，更是让算法在运行过程中不断-1ms，-1ms......但由于本人人生经验不足，对快速排序的优化止步于此。事实上，快速排序的优化潜力远不及此，各种高级优化对性能的提升不知道比我高到哪里去了。本文仅为抛砖引玉，介绍了几种简单的优化方法，以作学习交流用。

TheLudGamer

看完了，我还是需要再学习一个

KaaPexei

可以的

量子计算9

我记得还有一个优化方式是对序列聚集操作[思考]

JamesB

什么聚集操作？三路快排？

yukamu

多线程和预排序检查倒是学到了。除了小数组插入排序外，三数取中选锚点，还有三路快排，也就是把等于锚点的元素放到中间，只递归两边的。实际上工程上还有其它一些优化，比如如果设置递归深度，超过就转换为堆排，有序数组不是都递归展开，而是小数组递归，大数组迭代展开等等方式