如果说比较排序有什么让人惊愕的算法，我想一定是快排。

第一次学快排，打破了我的一个认知，一个较为有序的数组更容易排序。但用快排时，可能适得其反。

快排也是利用分而治之的思想，只不过比较奇葩的是，它不是将数组分为相等长度的子数组，而是随机的分。

比如取数组中第一个元素，进行partition归类，一类是小于等于此元素的，一类是大于此元素的。

然后数组自然的分成两个，又分别取第一个元素，再partition，直至分到不能再分。

当然，实践证明，没必要分到只剩2个元素，可以在剩4-15个元素开始，就使用插排，对于小数组，插排的平均效率反而是刚刚的。

partition的算法非常快，在于使用双向下标，从两边向中间靠拢，没有繁多的重复交换。

#include <random>
#include <vector>
#include <algorithm>

struct QuickSort
{
    template <typename Iter>
    bool isSorted(const Iter &begin, const Iter &end)
    {
        for (auto i = begin + 1; i != end; ++i)
        {
            if (less(*i, *(i - 1)))
            {
                return false;
            }
        }
        return true;
    }

    template <typename Iter>
    void show(const Iter &begin, const Iter &end)
    {
        std::for_each(begin, end, [](const auto &temp)
                      { std::cout << temp << " "; });
    }
    
    //随机混乱数组
    template <typename Iter>
    void sort(const Iter &begin, const Iter &end)
    {
        std::shuffle(begin, end, std::mt19937(time(0)));
        sortquick(begin, end - 1);
    }

private:
    template <typename T>
    bool less(const T &v, const T &w)
    {
        return v < w;
    }

    template <typename Iter>
    void exch(const Iter &i, const Iter &j)
    {
        std::swap(*i, *j);
    }

    template <typename Iter>
    Iter partition(const Iter &lo, const Iter &hi)
    {
        Iter i = lo;
        Iter j = hi + 1;
        auto v = *lo;
        while (1)
        {
            while (less(*(++i), v))
            {
                if (i == hi)
                {
                    break;
                }
            }
            while (less(v, *(--j)))
            {
                if (j == lo)
                {
                    break;
                }
            }
            if (i >= j)
            {
                break;
            }
            exch(i, j);
        }
        exch(lo, j);
        return j;
    }

    template <typename Iter>
    void sortquick(const Iter &lo, const Iter &hi)
    {
        if (hi - lo <= 8)
        {
            if (hi - lo > 0)
            {
                sortins(lo, hi + 1);
            }
            return;
        }
        auto j = partition(lo, hi);
        sortquick(lo, j - 1);
        sortquick(j + 1, hi);
    }
    
    //插排
    template <typename Iter>
    void sortins(const Iter &begin, const Iter &end)
    {
        for (auto i = begin + 1; i != end; ++i)
        {
            for (auto j = i; j != begin && less(*j, *(j - 1)); --j)
            {
                exch(j, j - 1);
            }
        }
    }
};