代码

#include <algorithm>
#include <utility>
#include <cstring>
#include <cstdlib>
template <class _RandomAccessIterator, class _Comp>
inline void insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp) {
    for (_RandomAccessIterator i = __first; i != __last; ++i) {
        for (_RandomAccessIterator j = i; !(j < __first + 1); --j) {
            if (comp(*j, *(j - 1))) {
                std::iter_swap(j, j - 1);
            }
            else break;
        }
    }
}
template <class _RandomAccessIterator, class _Comp>
inline void selection_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp) {
    for (_RandomAccessIterator i = __first; i != __last; ++i) {
        _RandomAccessIterator min = i;
        for (_RandomAccessIterator j = i + 1; j != __last; ++j) {
            if (comp(*j, *min)) min = j;
        }
        std::iter_swap(i, min);
    }
}
template <class _RandomAccessIterator, class _Comp>
inline void bubble_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp) {
    for (_RandomAccessIterator i = __first; i != __last; ++i) {
        for (_RandomAccessIterator j = __first; j != i; ++j) {
            if (comp(*(j + 1), *j)) std::iter_swap(j + 1, j);
        }
    }
}
template <typename _RandomAccessIterator, typename _Comp>
inline void cocktail_shaker_sort(_RandomAccessIterator __first,
    _RandomAccessIterator __last,
    _Comp comp)
{
    typedef typename std::iterator_traits<_RandomAccessIterator>
        ::difference_type diff;
    _RandomAccessIterator lastLeftExchangeIndex = __first;
    diff length = __last - __first;
    _RandomAccessIterator lastRightExchangeIndex = __first + (length - 1);
    _RandomAccessIterator leftBorder = __first, rightBorder = __last - 1;
    for (diff i = 0; i < length / 2 - 1; i++) {
        bool isRightExchanged = false;
        for (_RandomAccessIterator j = leftBorder; j < rightBorder; ++j) {
            if (comp(*(j + 1), *j)) {
                std::iter_swap(j + 1, j);
                isRightExchanged = true;
                lastRightExchangeIndex = j;
            }
        }
        rightBorder = lastRightExchangeIndex;
        if (!isRightExchanged) {
            return;
        }
        bool isLeftExchanged = false;
        for (_RandomAccessIterator k = rightBorder; leftBorder < k; --k) {
            if (comp(*k, *(k - 1))) {
                std::iter_swap(k, k - 1);
                isLeftExchanged = true;
                lastLeftExchangeIndex = k;
            }
        }
        leftBorder = lastLeftExchangeIndex;
        if (!isLeftExchanged) {
            return;
        }
    }
}
template <class _RandomAccessIterator, class _Comp>
inline void odd_even_sort(_RandomAccessIterator __first,
    _RandomAccessIterator __last,
    _Comp comp)
{
    bool sorted = false;
    while (!sorted) {
        sorted = true;
        for (_RandomAccessIterator i = __first + 1; i < __last - 1; i += 2) {
            if (comp(*(i + 1), *i)) {
                std::iter_swap(i, i + 1);
                sorted = false;
            }
        }
        for (_RandomAccessIterator i = __first; i < __last - 1; i += 2) {
            if (comp(*(i + 1), *i)) {
                std::iter_swap(i, i + 1);
                sorted = false;
            }
        }
    }
}
template <class _RandomAccessIterator, class _Comp>
inline void swap_med_to_mid(_RandomAccessIterator __first, _RandomAccessIterator __mid,
    _RandomAccessIterator __last, _Comp comp) {
    if (comp(*__first, *__mid)) {
        if (comp(*__first, *__last)) std::iter_swap(__mid, __last);
        else if (comp(*__last, *__mid)) std::iter_swap(__mid, __first);
    }
    else if (comp(*__first, *__last)) std::iter_swap(__mid, __first);
    else if (comp(*__mid, *__last)) std::iter_swap(__mid, __last);
}
template <class _RandomAccessIterator, class _Comp>
inline void swap_med9_to_mid(_RandomAccessIterator __first, _RandomAccessIterator __mid,
    _RandomAccessIterator __last, _Comp comp) {
    // Assumes that __last - __first >= 50.
    typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _Diff;
    const _Diff dis = __last - __first;
    const _Diff gap = (dis + 1) >> 3;
    const _Diff two_gap = gap << 1;
    swap_med_to_mid(__first, __first + gap, __first + two_gap, comp);
    swap_med_to_mid(__mid - gap, __mid, __mid + gap, comp);
    swap_med_to_mid(__last - two_gap, __last - gap, __last, comp);
    swap_med_to_mid(__first + gap, __mid, __last - gap, comp);
}
template <class _RandomAccessIterator, class _Comp>
inline void swap_med_to_mid_wrapper(_RandomAccessIterator __first, _RandomAccessIterator __mid,
    _RandomAccessIterator __last, _Comp comp) {
    const typename std::iterator_traits<_RandomAccessIterator>::difference_type dis = __last - __first;
    if (50 < dis) swap_med9_to_mid(__first, __mid, __last, comp);
    else swap_med_to_mid(__first, __mid, __last, comp);
}
template <class _RandomAccessIterator, class _Comp>
void __quick_sort_core(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp,
        void(*med_rule)(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Comp)) {
    while (__last - __first > 1) {
        _RandomAccessIterator cut = partition_rule(__first, __last, comp, med_rule);
        __quick_sort_core(cut, __last, comp, med_rule);
        __last = cut;
    }
}
template <class _RandomAccessIterator, class _Comp>
void __quick_sort3_core(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp, 
        void(*med_rule)(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Comp)) {
    while (__last - __first > 1) {
        std::pair< _RandomAccessIterator, _RandomAccessIterator> cut = partition3_rule(__first, __last, comp, med_rule);
        __quick_sort3_core(cut.second, __last, comp, med_rule);
        __last = cut.first;
    }
}
template <class _RandomAccessIterator, class _Comp>
inline _RandomAccessIterator partition_rule(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp,
    void(*policy)(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Comp))
{
    if (!(__first < __last)) return __first;
    --__last;
    _RandomAccessIterator pivot = __first + ((__last - __first) >> 1);
    policy(__first, pivot, __last, comp);
    typename std::iterator_traits< _RandomAccessIterator>::value_type mid = *pivot;
    do {
        while (!(__last < __first) && comp(*__first, mid)) ++__first;
        while (!(__last < __first) && comp(mid, *__last)) --__last;
        if (!(__last < __first)) {
            std::iter_swap(__first, __last);
            ++__first;
            --__last;
        }
    } while (!(__last < __first));
    return __first;
}
template <class _RandomAccessIterator, class _Comp>
inline std::pair< _RandomAccessIterator, _RandomAccessIterator>
partition3_rule(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp,
    void(*policy)(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Comp))
{
    if (!(__first < __last)) return std::make_pair(__first, __first);
    _RandomAccessIterator pivot = __first + ((__last - __first) >> 1);
    policy(__first, pivot, __last - 1, comp);
    typename std::iterator_traits< _RandomAccessIterator>::value_type mid = *pivot;
    _RandomAccessIterator tmp = __first, j = __first, k = __last;
    while (tmp < k) {
        if (comp(*tmp, mid)) {
            std::iter_swap(tmp, j);
            ++tmp;
            ++j;
        }
        else if (comp(mid, *tmp)) std::iter_swap(tmp, --k);
        else ++tmp;
    }
    return std::make_pair(j, k);
}
template <class _RandomAccessIterator, class _Comp>
inline void quick_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp,
    void(*med_rule)(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Comp)) {
    __quick_sort_core(__first, __last, comp, med_rule);
}
template <class _RandomAccessIterator, class _Comp>
inline void quick_sort3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp,
    void(*med_rule)(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Comp)) {
    __quick_sort3_core(__first, __last, comp, med_rule);
}
template <class _RandomAccessIterator, class _Comp>
inline void __intro_sort_core(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp,
    void(*med_rule)(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Comp),
    int depth, typename std::iterator_traits< _RandomAccessIterator>::difference_type __threshold)
{
    while (__last - __first > __threshold) {
        if (depth == 0) {
            sort_max_heap(__first, __last, comp);
            return;
        }
        --depth;
        _RandomAccessIterator cut = partition_rule(__first, __last, comp, med_rule);
        __intro_sort_core(cut, __last, comp, med_rule, depth, __threshold);
        __last = cut;
    }
}
template <class _RandomAccessIterator, class _Comp>
inline void __intro_sort3_core(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp,
    void(*med_rule)(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Comp),
    int depth, typename std::iterator_traits< _RandomAccessIterator>::difference_type __threshold)
{
    while (__last - __first > __threshold) {
        if (depth == 0) {
            sort_max_heap(__first, __last, comp);
            return;
        }
        --depth;
        std::pair<_RandomAccessIterator, _RandomAccessIterator> cut = partition3_rule(__first, __last, comp, med_rule);
        __intro_sort3_core(cut.second, __last, comp, med_rule, depth, __threshold);
        __last = cut.first;
    }
}
template <class _RandomAccessIterator, class _Comp>
inline void intro_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp,
    void(*med_rule)(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Comp),
    typename std::iterator_traits< _RandomAccessIterator>::difference_type __threshold)
{
    __intro_sort_core(__first, __last, comp, med_rule, std::__lg(__last - __first) << 1, __threshold);
    insertion_sort(__first, __last, comp);
}
template <class _RandomAccessIterator, class _Comp>
inline void intro_sort3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp,
    void(*med_rule)(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Comp),
    typename std::iterator_traits< _RandomAccessIterator>::difference_type __threshold)
{
    __intro_sort3_core(__first, __last, comp, med_rule, std::__lg(__last - __first) << 1, __threshold);
    insertion_sort(__first, __last, comp);
}
template <class _RandomAccessIterator, class _Comp>
inline void intro_sort_with_shell_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp,
    void(*med_rule)(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Comp),
    typename std::iterator_traits< _RandomAccessIterator>::difference_type __threshold)
{
    __intro_sort_core(__first, __last, comp, med_rule, std::__lg(__last - __first) << 1, __threshold);
    shell_sort(__first, __last, comp);
}
template <class _RandomAccessIterator, class _Comp>
inline void intro_sort3_with_shell_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp,
    void(*med_rule)(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Comp),
    typename std::iterator_traits< _RandomAccessIterator>::difference_type __threshold)
{
    __intro_sort3_core(__first, __last, comp, med_rule, std::__lg(__last - __first) << 1, __threshold);
    shell_sort(__first, __last, comp);
}
template <class _RandomAccessIterator, class _Comp>
inline void weave_merge(_RandomAccessIterator __first, _RandomAccessIterator __mid, _RandomAccessIterator __last, _Comp comp) {
    _RandomAccessIterator i = __first + 1, j = __mid;
    while (i < j) {
        std::iter_swap(i, j);
        i += 2;
        ++j;
    }
    insertion_sort(__first, __last, comp);
}
template <class _RandomAccessIterator, class _Comp>
inline void weave_merge_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp) {
    if (__last - __first <= 1) return;
    _RandomAccessIterator mid = __first + ((__last - __first) >> 1);
    weave_merge_sort(__first, mid, comp);
    weave_merge_sort(mid, __last, comp);
    weave_merge(__first, mid, __last, comp);
}
template <class _ForwardIterator, class _Comp>
void merge_without_buffer(_ForwardIterator __first, _ForwardIterator __mid, _ForwardIterator __last, _Comp comp) {
    if (__first == __mid || __mid == __last) return;
    typedef typename std::iterator_traits<_ForwardIterator>::difference_type _Diff;
    _Diff dis1, dis2, len1, len2;
    dis1 = std::distance(__first, __mid);
    dis2 = std::distance(__mid, __last);
    _ForwardIterator cut1, cut2;
    if (dis1 < dis2) {
        len2 = dis2 >> 1;
        cut2 = __mid;
        std::advance(cut2, len2);
        cut1 = std::upper_bound(__first, __mid, *cut2, comp);
    }
    else {
        len1 = dis1 >> 1;
        cut1 = __first;
        std::advance(cut1, len1);
        cut2 = std::upper_bound(__mid, __last, *cut1, comp);
    }
    _ForwardIterator new_middle = std::rotate(cut1, __mid, cut2);
    merge_without_buffer(__first, cut1, new_middle, comp);
    merge_without_buffer(new_middle, cut2, __last, comp);
}
template <typename _BidirectionalIterator1, typename _BidirectionalIterator2, typename _BidirectionalIterator, typename _Comp>
inline void merge_backward(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1,
    _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2,
    _BidirectionalIterator __result, _Comp comp)
{
    --__last1;
    --__last2;
    while (true) {
          if (comp(*__last2, *__last1)) {
              *--__result = *__last1;
              if (__first1 == __last1) {
                  std::copy_backward(__first2, ++__last2, __result);
                  return;
            }
              --__last1;
        }
          else {
              *--__result = *__last2;
              if (__first2 == __last2) return;
              --__last2;
        }
    }
}
template <typename _BidirectionalIterator, typename _Pointer, typename _Comp>
void merge_with_buffer(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
    _Pointer buf, ptrdiff_t siz, _Comp comp) {
    if (__first == __middle || __middle == __last) return;
    typedef typename std::iterator_traits<_BidirectionalIterator>::difference_type _Diff;
    _Diff dis1, dis2, len1, len2;
    dis1 = std::distance(__first, __middle);
    dis2 = std::distance(__middle, __last);
    if (dis1 < dis2 && dis1 < siz) {
        _Pointer bufend = std::copy(__first, __middle, buf);
        std::merge(__middle, __last, buf, bufend, __first, comp);
    }
    else if (dis2 < siz) {
        _Pointer bufend = std::copy(__middle, __last, buf);
        merge_backward(__first, __middle, buf, bufend, __last, comp);
    }
    else {
        _BidirectionalIterator cut1, cut2;
        if (dis1 < dis2) {
            len2 = dis2 >> 1;
            cut2 = __middle;
            std::advance(cut2, len2);
            cut1 = std::upper_bound(__first, __middle, *cut2, comp);
        }
        else {
            len1 = dis1 >> 1;
            cut1 = __first;
            std::advance(cut1, len1);
            cut2 = std::upper_bound(__middle, __last, *cut1, comp);
        }
        _BidirectionalIterator new_middle = std::rotate(cut1, __middle, cut2);
        merge_with_buffer(__first, cut1, new_middle, buf, siz, comp);
        merge_with_buffer(new_middle, cut2, __last, buf, siz, comp);
    }
}
template <class _RandomAccessIterator, class _Pointer, class _Size, class _Comp>
inline void merge_sort_with_buffer(_RandomAccessIterator __first,
                                   _RandomAccessIterator __last,
                                   _Pointer buf,
                                   _Size buf_size,
                                   _Comp comp)
{
    if (__last - __first <= 1) return;
    _RandomAccessIterator __middle = __first + ((__last - __first) >> 1);
    merge_sort_with_buffer(__first, __middle, buf, buf_size, comp);
    merge_sort_with_buffer(__middle, __last, buf, buf_size, comp);
    merge_with_buffer(__first, __middle, __last, buf, buf_size, comp);
}
template <class _RandomAccessIterator, class _Comp>
inline void merge_sort_without_buffer(_RandomAccessIterator __first,
                                      _RandomAccessIterator __last,
                                      _Comp comp)
{
    if (__last - __first <= 1) return;
    _RandomAccessIterator __middle = __first + ((__last - __first) >> 1);
    merge_sort_without_buffer(__first, __middle, comp);
    merge_sort_without_buffer(__middle, __last, comp);
    merge_without_buffer(__first, __middle, __last, comp);
}
template <class _RandomAccessIterator, class _Comp>
inline void merge_sort(_RandomAccessIterator __first,
                       _RandomAccessIterator __last,
                       _Comp comp)
{
#ifdef __GNUC__
    std::_Temporary_buffer<_RandomAccessIterator,
#elif defined(_MSC_VER)
    std::_Optimistic_temporary_buffer<
#endif
    typename std::iterator_traits<_RandomAccessIterator>
        ::value_type> buf(
#ifdef __GNUC__
        __first,
#endif
        __last - __first);
#if defined(__GNUC__)
    if (buf.begin() == nullptr) merge_sort_without_buffer(__first, __last, comp);
    else merge_sort_with_buffer(__first, __last, buf.begin(), buf.size(), comp);
#elif defined(_MSC_VER)
    merge_sort_with_buffer(__first, __last, buf._Data, buf._Capacity, comp);
#endif
}
template <class _RandomAccessIterator, class _Comp>
inline void inplace_merge_sort(_RandomAccessIterator __first,
                               _RandomAccessIterator __last,
                               _Comp comp)
{
    merge_sort_without_buffer(__first, __last, comp);
}
template <class _Tp, class _Comp>
inline void merge_sort_helper(_Tp* __first, _Tp* __last, _Tp* mem, _Comp comp) {
    if (__last - __first <= 1) return;
    if (__last - __first == 2) {
        if (comp(*(__first + 1), *__first)) std::iter_swap(__first, __first + 1);
        return;
    }
    ptrdiff_t dis = __last - __first;
    _Tp* mid = __first + (dis >> 1);
    merge_sort_helper(__first, mid, mem, comp);
    merge_sort_helper(mid, __last, mem, comp);
    std::merge(__first, mid, mid, __last, mem, comp);
    __last = std::copy_n(mem, dis, __first);
}
template <class _Tp, class _Comp>
inline void merge_sort(_Tp* __first, _Tp* __last, _Comp comp) {
    _Tp* mem;
    try {
        mem = new _Tp[__last - __first];
        merge_sort_helper(__first, __last, mem, comp);
    }
    catch (std::bad_alloc) {
        delete[] mem;
        merge_sort_without_buffer(__first, __last, comp);
    }
}
template <class _RandomAccessIterator, class _Comp>
inline void shell_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp) {
    typename std::iterator_traits<_RandomAccessIterator>::difference_type h = 1;
    typename std::iterator_traits<_RandomAccessIterator>::difference_type tmp = __last - __first;
    while (h < tmp / 3) h = h * 3 + 1;
    while (h >= 1) {
        for (typename std::iterator_traits<_RandomAccessIterator>::difference_type i = h; i < tmp; i++) {
            for (_RandomAccessIterator j = __first + i; !(j < (__first + h)) && comp(*j, *(j - h)); j -= h) std::iter_swap(j, j - h);
        }
        h /= 3;
    }
}
inline constexpr unsigned getd(unsigned x, int d, unsigned U, int BIT) {
    return (x >> (d * BIT)) & (U - 1);
}
inline void radix_sort_lsd_base256(unsigned* __first, unsigned* __last) {
    static constexpr unsigned bit = 8;
    static constexpr unsigned u = 1u << bit;
    static unsigned cnt[u];
    unsigned* y = new unsigned[__last - __first];
    for (int d = 0; d < 4; d++) {
        for (unsigned i = 0; i < u; i++) cnt[i] = 0;
        for (unsigned* ptr = __first; ptr != __last; ++ptr) ++cnt[getd(*ptr, d, u, bit)];
        for (unsigned i = 1; i < u; i++) cnt[i] += cnt[i - 1];
        for (unsigned* ptr = __last - 1; !(ptr < __first); --ptr) y[--cnt[getd(*ptr, d, u, bit)]] = *ptr;
        memcpy(__first, y, (__last - __first) * sizeof(unsigned));
    }
    delete[] y;
}
inline void radix_sort_lsd_base2048(unsigned* __first, unsigned* __last) {
    static constexpr unsigned bit = 11;
    static constexpr unsigned u = 1u << bit;
    static unsigned cnt[u];
    unsigned* y = new unsigned[__last - __first];
    for (int d = 0; d < 3; d++) {
        for (unsigned i = 0; i < u; i++) cnt[i] = 0;
        for (unsigned* ptr = __first; ptr != __last; ++ptr) ++cnt[getd(*ptr, d, u, bit)];
        for (unsigned i = 1; i < u; i++) cnt[i] += cnt[i - 1];
        for (unsigned* ptr = __last - 1; !(ptr < __first); --ptr) y[--cnt[getd(*ptr, d, u, bit)]] = *ptr;
        memcpy(__first, y, (__last - __first) * sizeof(unsigned));
    }
    delete[] y;
}
inline void radix_sort_lsd_base65536(unsigned* __first, unsigned* __last) {
    static constexpr unsigned bit = 16;
    static constexpr unsigned u = 1u << bit;
    static unsigned cnt[u];
    unsigned* y = new unsigned[__last - __first];
    for (int d = 0; d < 2; d++) {
        for (unsigned i = 0; i < u; i++) cnt[i] = 0;
        for (unsigned* ptr = __first; ptr != __last; ++ptr) ++cnt[getd(*ptr, d, u, bit)];
        for (unsigned i = 1; i < u; i++) cnt[i] += cnt[i - 1];
        for (unsigned* ptr = __last - 1; !(ptr < __first); --ptr) y[--cnt[getd(*ptr, d, u, bit)]] = *ptr;
        memcpy(__first, y, (__last - __first) * sizeof(unsigned));
    }
    delete[] y;
}
void counting_sort(unsigned *__first, unsigned *__last) {
    unsigned* count_arr = (unsigned*)malloc([=]() {
        auto [pmin, pmax] = std::minmax_element(__first, __last);
        return *pmax + 5;
    }() * sizeof(unsigned));
    unsigned *sorted_arr = (unsigned*)malloc((__last - __first) * sizeof(unsigned));
    for (unsigned* ptr = __first; ptr != __last; ++ptr) count_arr[*ptr]++;
    for (unsigned k = 1; k < 100; k++) count_arr[k] += count_arr[k - 1];
    for (unsigned* ptr = __last - 1; !(ptr < __first); --ptr) sorted_arr[--count_arr[*ptr]] = *ptr;
    memcpy(__first, sorted_arr, (__last - __first) * sizeof(unsigned));
    free(count_arr);
    free(sorted_arr);
}
void sort(unsigned* a, int n) { radix_sort_lsd_base2048(a, a + n); }

评测结果