一、前言

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

本文旨在用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)

  • 说明:计算迭代器firstlast之间有多少元素。
  • 复杂度:随机访问迭代器在常数时间内完成(地址相减),其余在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]排序。

测试结果如下,测试用例参考源码:

[==========] Running 6 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 6 tests from SortTest

[ RUN      ] SortTest.QuickSort
[       OK ] SortTest.QuickSort (340 ms)
[ RUN      ] SortTest.MergeSort
[       OK ] SortTest.MergeSort (439 ms)
[ RUN      ] SortTest.HeapSort
[       OK ] SortTest.HeapSort (610 ms)
[ RUN      ] SortTest.InsertionSort
[       OK ] SortTest.InsertionSort (453 ms)
[ RUN      ] SortTest.SelectionSort
[       OK ] SortTest.SelectionSort (4368 ms)
[ RUN      ] SortTest.BubbleSort
[       OK ] SortTest.BubbleSort (16012 ms)
[----------] 6 tests from SortTest (22223 ms total)

[----------] Global test environment tear-down
[==========] 6 tests from 1 test suite ran. (22512 ms total)
[  PASSED  ] 6 tests.
Last modification:January 4th, 2020 at 06:30 pm