八大排序算法 STL大法

冒泡排序

// 一、冒泡排序 [P1177 【模板】排序——(TLE 2, 3, 4, 5)]  
// 最好时间复杂度 O(n) 平均时间复杂度 O(n^2) 最坏时间复杂度 O(n^2)
// 空间复杂度 O(1)
// 稳定  
template<class Iterator, class Comparer>  
void bubble_sort(Iterator begin, Iterator end, const Comparer &cmp) {  
    for (;begin != end; --end)  
        for (auto it = begin, next = std::next(it); next != end; ++it, next = std::next(it)) {  
            if (not cmp(*next, *it)) continue;  
            std::iter_swap(it, next);  
        }  
}  
template<class Iterator>  
void bubble_sort(Iterator begin, Iterator end) {  
    bubble_sort(begin, end, std::less<>());  
}

选择排序

// 二、选择排序 [P1177 【模板】排序——(TLE 2, 3, 4, 5)]  
// 最好时间复杂度 O(n^2) 平均时间复杂度 O(n^2) 最坏时间复杂度 O(n^2)
// 空间复杂度 O(1)
// 不稳定  
template<class Iterator, class Comparer>
void selection_sort (Iterator begin, Iterator end, const Comparer &cmp) {
    for (auto current = end; current != begin;) {
        auto it = std::max_element(begin, current--, cmp);
        std::iter_swap(current, it);
    }
}
template<class Iterator>
void selection_sort(Iterator begin, Iterator end) {
    selection_sort(begin, end, std::less<>());
}

插入排序

// 三、插入排序 [P1177 【模板】排序——(AC)]  
// 最好时间复杂度 O(n) 平均时间复杂度 O(n^2) 最坏时间复杂度 O(n^2)
// 空间复杂度 O(1)
// 稳定  
template<class Iterator, class Comparer>  
void insertion_sort(Iterator begin, Iterator end, const Comparer &cmp) {  
    for (auto current = std::next(begin); current != end; ++current) {  
        auto val = *current;  
        auto it = std::upper_bound(begin, current, val, cmp);  
        std::copy_backward(it, current, std::next(current));  
        *it = val;  
    }  
}  
template<class Iterator>  
void insertion_sort(Iterator begin, Iterator end) {  
    insertion_sort(begin, end, std::less<>());  
}

计数排序

普通实现明显不适合迭代器和泛型实现，用哈希来离散化处理，比较函数便成了哈希函数

红黑树空间优化实现

// 四、2.计数排序(map压缩空间) [P1177 【模板】排序——(AC)]  
// 最好时间复杂度 O(nlogn) 平均时间复杂度 O(nlogn) 最坏时间复杂度 O(nlogn)
// 空间复杂度 O(n)
// 稳定
template<class Iterator, class Comparer>  
void counting_sort(Iterator begin, Iterator end, const Comparer &cmp) {  
    using T = std::remove_reference<decltype(*begin)>::type;  
    std::map<T, std::size_t, Comparer> counter;  
    std::for_each(begin, end, [&counter](const auto &val) { ++counter[val]; });  
    auto it = begin;  
    for (auto &&[val, cnt] : counter)  
        for (; cnt != 0; --cnt, ++it)  
            *it = val;  
}  
template<class Iterator>  
void counting_sort(Iterator begin, Iterator end) {  
    counting_sort(begin, end, std::less<>());  
}

希尔排序

// 五、希尔排序 [P1177 【模板】排序——(AC)]  
// 最好时间复杂度 O(n) 平均时间复杂度 O(n^{1.3}) 最坏时间复杂度 O(n^2)
// 空间复杂度 O(1)
// 不稳定  
template <class Iterator, class Comparer>  
void shell_sort(Iterator begin, Iterator end, const Comparer &cmp) {  
    size_t len = std::distance(begin, end);  
    std::vector<size_t> gaps;  
    for (size_t gap = 1; gap < len; gap = 3 * gap + 1)  
        gaps.emplace_back(gap);  
    auto &&gapped_insertion_sort = [&](const auto &gap) {  
        for (auto i = gap; i < len; ++i) {  
            auto temp = *std::next(begin, i);  
            auto j = i;  
            while (j >= gap and cmp(temp, *std::next(begin, j - gap))) {  
                *std::next(begin, j) = *std::next(begin, j - gap);  
                j -= gap;  
            }  
            *std::next(begin, j) = temp;  
        }  
    };  
    std::for_each(gaps.rbegin(), gaps.rend(), gapped_insertion_sort);  
}  
template<class iterator>  
void shell_sort(iterator begin, iterator end) {  
    shell_sort(begin, end, std::less<>());  
}

快速排序

// 六、快速排序 [P1177 【模板】排序——(AC)]  
// 最好时间复杂度 O(n log_2{n}) 平均时间复杂度 O(n log_2{n}) 最坏时间复杂度 O(n^2)
// 空间复杂度 O(n log_2{n})
// 不稳定  
template<class Iterator, class Comparer>
void quick_sort(Iterator begin, Iterator end, const Comparer &cmp) {
    const auto distance = std::distance(begin, end);
    if (distance <= 1)
        return;
    const auto pivot = *std::next(begin, distance >> 1);
    Iterator middle1 = std::partition(begin, end, 
                         [&cmp, pivot](const auto& val){ return cmp(val, pivot); });
    Iterator middle2 = std::partition(middle1, end, 
                         [&cmp, pivot](const auto& val){ return not cmp(pivot, val); });
    quick_sort(begin, middle1, cmp);
    quick_sort(middle2, end, cmp);
}
template<class Iterator>
void quick_sort(Iterator begin, Iterator end) {
    quick_sort(begin, end, std::less<>());
}

归并排序

// 七、归并排序 [P1177 【模板】排序——(AC)]  
// 最好时间复杂度 O(n log_2{n}) 平均时间复杂度 O(n log_2{n}) 最坏时间复杂度 O(n log_2{n})
// 空间复杂度 O(1)
// 不稳定  
template<class Iterator, class Comparer>
void merge_sort(Iterator begin, Iterator end, const Comparer &cmp) {
    const auto distance = std::distance(begin, end);
    if (distance <= 1)
        return;
    Iterator middle = std::next(begin, distance >> 1);
    merge_sort(begin, middle, cmp);
    merge_sort(middle, end, cmp);
    std::inplace_merge(begin, middle, end, cmp);
}
template<class Iterator>
void merge_sort(Iterator begin, Iterator end) {
    merge_sort(begin, end, std::less<>());
}

堆排序

// 八、堆排序 [P1177 【模板】排序——(AC)]  
// 最好时间复杂度 O(n log_2{n}) 平均时间复杂度 O(n log_2{n}) 最坏时间复杂度 O(n log_2{n})
// 空间复杂度 O(1)
// 不稳定  
template<class Iterator, class Comparer>
void heap_sort(Iterator begin, Iterator end, const Comparer &cmp) {
    std::make_heap(begin, end, cmp);
    std::sort_heap(begin, end, cmp);
}
template<class Iterator>
void heap_sort(Iterator begin, Iterator end) {
    heap_sort(begin, end, std::less<>());
}