代码

#include <algorithm>
#include <iostream>
#include <vector>
#include<algorithm>
#include<array>
#include<ios>
#include<iterator>
#include <chrono>
#include<queue>
#include<random>
#include<climits>
#include<cmath>
#include<type_traits>
#include<string>
#include<iterator>
#include <experimental/random>
#include<stack>

namespace InsertionSort {

    template<typename Iterator>
    void Sort_copy(Iterator begin, Iterator end) {
        if (end - begin <= 1) return;
        for (Iterator it = std::next(begin); it != end; ++it) {
            Iterator aim = std::upper_bound(begin, it, *it);//upper_bound在[begin,it)二分查找第一个大于*it
            auto temp = *it;
            std::copy(aim, (it), std::next(aim));
            *aim = temp;
        }
    }
}
namespace BubbleSort {
    template<typename Iterator>
    void Sort1(Iterator begin, Iterator end) {
        auto len = std::distance(begin, end);
        if (len <= 1) return;
        bool flag(true);
        while (flag) {//数列有序时退出
            flag = false;
            for (auto it(begin); it != std::prev(end); ++it) {
                if ((*it) > (*std::next(it))) {
                    flag = true;//发现数列非有序
                    std::iter_swap(it, std::next(it));
                }
            }
        }
    }

}
namespace HeapSort {
    template<typename Iterator>
    void sift_down(Iterator begin, Iterator end, Iterator parent) {
        auto size = std::distance(begin, end);
        while (true) {
            auto child = std::next(parent, std::distance(begin, parent) + 1);//左儿子
            if (std::distance(begin, child) >= size) break;////该节点没有子节点了，是叶节点了，结束
            if (std::next(child, 1) < end && (*child) < (*std::next(child))) ++child;//如果有右儿子并且右儿子更大，则选择右儿子来交换

            if (*(child) > *(parent)) {
                std::swap(*parent, *child);//子节点有大于父节点的，交换，维护堆
                parent = child;
            } else break;//已经维护好了
        }
    }

    template<typename Iterator>
    void Sort(Iterator begin, Iterator end) {
        auto len = std::distance(begin, end);
        //从最后一个节点的非叶子结点开始维护堆
        for (auto i = (len - 1 - 1) / 2; i >= 0; --i) sift_down(begin, end, std::next(begin, i));//自底向上建立初始堆

        for (auto i = len - 1; i > 0; --i) {//将堆顶元素移动至堆顶，并且维护堆
            std::iter_swap(begin, std::next(begin, i));
            sift_down(begin, std::next(begin, i), begin);
        }
    }
}

namespace QuickSort {
    template<typename T>
    T randint(T lower, T upper) {
        static std::random_device rd;//用于生成种子 记得搞静态，不然会很慢，这个很昂贵
        static std::mt19937 gen(rd());//使用梅森旋转算法生成随机数
        std::uniform_int_distribution<T> dis(lower, upper);//创建整数分布对象
        return dis(gen);//生成指定范围内的随机数
//        return std::experimental::randint(lower,upper);
    }

    template<typename Iterator>
    std::vector<Iterator> PartitionThreeWaySTD(Iterator begin, Iterator end) {
        using difference_type = typename std::iterator_traits<Iterator>::difference_type;
        auto len = std::distance(begin, end);
        auto pivot = *std::next(begin, randint((difference_type) 0, len - 1));//随机基准值

        Iterator middle1 = std::partition(begin, end,
                                          [&pivot](const auto &element) {
                                              return (element < pivot);
                                          });// 小于基准值
        Iterator middle2 = std::partition(middle1, end,
                                          [&pivot](const auto &element) {
                                              return (element <= pivot);
                                          });//等于基准值的
        return {middle1, middle2};//[middle1,middle2)都是等于pivot的元素
    }

    template<typename Iterator>
    void IntroSort(Iterator begin, Iterator end, int const depth, int const &insert_limit = 16) {
        if (end <= begin) return;
        if (end - begin + 1 < insert_limit) {
            InsertionSort::Sort_copy(begin, end);
            return;
        }
        if (!depth) {
            HeapSort::Sort(begin, end);
        }

        auto pivot = PartitionThreeWaySTD(begin, end);
        IntroSort(begin, pivot[0], depth - 1);
        IntroSort(pivot[1], end, depth - 1);
    }

    template<typename Iterator>
    void IntroSort(Iterator begin, Iterator end) {
        int depth = static_cast<int>(2 * log(end - begin));
        IntroSort(begin, end, depth);
    }
}

void sort(unsigned *a, int n) {
QuickSort::IntroSort(a,a+n);
}

评测结果