排序算法 - C++11实现

原文链接

一、前言

排序算法一般是所有算法书函授的第一类算法。

本文旨在用C++11来实现主流的排序算法：插入排序、冒泡排序、归并排序、快速排序、堆排序、选择排序。并设计单元测试和代码覆盖率直观比较排序算法性能异同。

说明：本文代码需支持C++11标准编译器编译，单元测试仅支持googletest。

项目地址：github.com/Pipapa/algorithm

二、函数声明

函数格式声明如下

// iterator_traits<It>::value_tpye 用于获取模版中It的类型
template<class It>
using value_type_t = typename std::iterator_traits<It>::value_type;

// 所有排序函数声明如下
// 参数传入为迭代器起始位置、结束位置，比较函数，迭代器遵循标准左开右闭
// 默认比较函数std::less<>
template<class It, class Compare = std::less<value_type_t<It>>>
void XxxSort(It begin, It end, Compare cmp = Compare());

三、排序算法实现

3.1.插入排序

将会用到的库函数：

std::next(it)

• 说明：获取it迭代器的下一个迭代器。

std::upper_bound(first, last, value, cmp)

• 说明：在有序区间[first, last)，查找第一个满足!cmp(valut, *it)迭代器。
• 复杂度：随机访问迭代器为logn（二分查找），否则为n（遍历）。

std::rotate(first, n_first, last)

• 说明：左旋区间，在区间[first, last)中，让迭代器n_first成为第一个元素，n_first - 1成为最后一个元素。即：旋转前[first, ..., n_first, ... , last)，旋转后：[n_first, ..., first, ..., last)。

插入排序思想：

将排序数组分为两部分：已排序、待排序。

依次遍历待排序数组元素并插入到已排序数组中。

template<class It, class Compare = std::less<value_type_t<It>>>
void InsertionSort(It begin, It end, Compare cmp = Compare()) {
    for(auto it = begin; it != end; it = std::next(it)) {
        auto const insertion = std::upper_bound(begin, it, *it, cmp);
        std::rotate(insertion, it, std::next(it));
    }
}

3.2.冒泡排序

将会用到的库函数：

std::iter_swap(a, b)

• 说明：交换迭代器a,b所指向的值。

冒泡排序思想：

将排序数组分为两部分：待排序、已排序。

依次遍历待排序数组元素，调整元素使两两之间满足大小关系，每一次调整，都使最大（小）元素在后面的位置。

最后会使待排序区中最大（小）元素位于待排序区最后位置，归入已排序区即可。

冒泡排序优化：

如果不发生元素交换，证明数组有序，可结束排序。

如果元素在某区域不发生交换，证明该区域已有序，更新已排序区开始位置为最后一次发生交换的位置。

template<class It, class Compare = std::less<value_type_t<It>>>
void BubbleSort(It begin, It end, Compare cmp = Compare()) {
    for(auto it = end, sorted = false; it != begin && !sorted;) {
        sorted = true;
        auto nit = std::prev(it);
        for(auto fwdit = std::next(begin); fwdit != it; fwdit = std::next(fwdit)) {
            if(cmp(*fwdit, *std::prev(fwdit))) {
                std::iter_swap(fwdit, std::prev(fwdit));
                sorted = false;
                nit = fwdit;
            }
        }
        it = nit;
    }
}

3.3.选择排序

将会用到的库函数：

std::min_element(first, end, cmp)

• 说明：在[first, end)中查找满足cmp(it, others)的迭代器。

选择排序思想：

将排序数组分为两部分：已排序、待排序。

不同于插入排序，将待排序元素插入已排序区域，而是在待排序区域查找满足大（小）于已排序区域最后一个元素，让其成为已排序区的最后元素。

template<class It, class Compare = std::less<value_type_t<It>>>
void SelectionSort(It begin, It end, Compare cmp = Compare()) {
    for(auto it = begin; it != end; it = std::next(it)) {
        std::iter_swap(it, std::min_element(it, end, cmp));
    }
}

3.4.归并排序

将会用到的库函数：

std::distance(first, last)

• 说明：计算迭代器first和last之间有多少元素。
• 复杂度：随机访问迭代器在常数时间内完成（地址相减），其余在n时间内完成（遍历）。

std::inplace_merge(first, mid, last)

• 合并两个有序区间[first, mid)和[mid, last)。

归并排序思想：

将两个有序数组合并为一个有序数组，使用递归或多路归并保障合并的两数组皆有序。

template<class It, class Compare = std::less<value_type_t<It>>>
void MergeSort(It begin, It end, Compare cmp = Compare()) {
    const auto N = std::distance(begin, end);
    if(N <= 1) {
        return;
    }
    const auto mid = std::next(begin, N/2);
    MergeSort(begin, mid, cmp);
    MergeSort(mid, end, cmp);
    std::inplace_merge(begin, mid, end);
}

3.5.堆排序

堆排序思路：

将排序数组分为两部分：待排序、已排序。

在待排序区建立大（小）根堆，根堆满足其根节点均大（小）于所有子节点。

每次迭代交换根节点到已排序区，待排序区再重新调整根堆。

// 仅给出适用于随机存储的迭代器实现,详细参考github
// 堆调整
template<class It, class Compare = std::less<value_type_t<It>>>                                                                   
void RandomAccessAdjustHeap(It begin, It end, It root, Compare cmp = Compare()) {                                                 
    auto son = (root - begin) * 2 + 1 + begin;
    while(son < end) {           
        if(son + 1 < end && cmp(*son, *(son+1))) {
            son++;                  
        }             
        if(cmp(*son, *root)) return;   
        std::iter_swap(son, root);
        root = son;                            
        son = (root - begin) * 2 + 1 + begin;          
    }                                                  
}
// 堆构建
template<class It, class Compare = std::less<value_type_t<It>>>
void RandomAccessMakeHeap(It begin, It end, Compare cmp = Compare()) {
    const auto N = std::distance(begin, end);
    if(N <= 1) {
        return;
    }
    for(auto root = std::next(begin, (N-2)/2); root >= begin; --root) {
        RandomAccessAdjustHeap(begin, end, root, cmp);
    }
}
// 堆排序
template<class It, class Compare = std::less<value_type_t<It>>>
void RandomAccessSortHeap(It begin, It end, Compare cmp = Compare()) {
    const auto N = std::distance(begin, end);
    if(N <= 1) {
        return;
    }
    auto last = std::prev(end);
    while(begin != last) {
        std::iter_swap(begin, last);
        RandomAccessAdjustHeap(begin, last, begin, cmp);
        last = std::prev(last);
    }
}
template<class It, class Compare = std::less<value_type_t<It>>>
void HeapSort(It begin, It end, Compare cmp = Compare()) {
    RandomAccessMakeHeap(begin, end, cmp);
    RandomAccessSortHeap(begin, end, cmp);
}

3.6.快速排序

将会用到的库函数：

std::partition(first, last, p)

• 说明：将区间[first, last)分为两部分，第一部分满足条件p，第二部分不满足条件p，返回第一个不满足条件p的迭代器。

快速排序思路：

将数组分为三部分，第一部分所有元素小（大）于pivot值，第二部分所有元素等于pivot值，第三部分所有元素大（小）于pivot值。

递归排序第一、第三部分直到不可划分，即排序完成。

template<class It, class Compare = std::less<value_type_t<It>>>
void QuickSort(It begin, It end, Compare cmp = Compare()) {
    auto const N = std::distance(begin, end);
    if(N <= 1) {
        return;
    }
    auto const pivot = *std::next(begin, N/2);
    auto const midl = std::partition(begin, end, [=](value_type_t<It> const& elem) {
        return cmp(elem, pivot);
    });
    auto const midg = std::partition(midl, end, [=](value_type_t<It> const &elem) {
        return !cmp(pivot, elem);
    });
    QuickSort(begin, midl, cmp);
    QuickSort(midg, end, cmp);
}

四、单元测试设计

• 随机生成1000组长度为[0, 1000]的数组，其值为[0, 1000]之间，排序该数组所有值。
• 随机生成1000组长度为[0, 1000]的数组，其值为[0, 1000]之间，排序该数组区间[l, r]间值（保障区间合法）。

总结：

• 共2000组测试用例，分别测试区间全排序和合法部分区间[l, r]排序。

测试结果执行如下：

image