专栏首页方亮C++拾取——使用stl标准库实现排序算法及评测

C++拾取——使用stl标准库实现排序算法及评测

        今天看了一篇文章,讲各种语言的优势和劣势。其中一个观点:haskell非常适合写算法,因为使用者不用去关心具体的计算机实现,而只要关注于操作语义。这让它在专心研究算法的人中非常受欢迎。所以很多时候,语言的争论没有太多的意义,有意义的是它适不适合某些场景或者某些人。(转载请指明出于breaksoftware的csdn博客)

        目前在网上讨论排序算法更多是C语言实现的。因为C语言可以展现出一些细节。但是从某种角度说,这也让“算法思想的光辉”被计算机操作细节所遮蔽。本文将使用C++的标准库去实现一些排序算法,我们从中将会发现它掩盖了很多计算机操作细节,而让算法的光辉得以显现。

实现

选择排序

template<class ForwardIt>
void selection_sort(ForwardIt begin, ForwardIt end) {
    for (ForwardIt i = begin; i != end; ++i) {
        std::iter_swap(i, std::min_element(i, end));
    }
}

        min_element返回两个索引之间最小元素的索引;iter_swap将最小索引和不停迭代的索引进行交换。

        这就是选择排序:逐位替换之后(包含自身)序列中最小的元素。

合并排序

template<class ForwardIt>
void merge_sort(ForwardIt begin, ForwardIt end)
{
    if (end - begin > 1) {
        ForwardIt middle = begin + (end - begin) / 2;
        merge_sort(begin, middle);
        merge_sort(middle, end);
        std::inplace_merge(begin, middle, end);
    }
}

        inplace_merge会将有序序列[begin,middle)和有序序列[middle,end)合并成一个有序队列[begin,end)。因为merge_sort会递归下去,所以可以从最低粒度开始保证上述是有序的。

插入排序

template<class ForwardIt>
void insertion_sort(ForwardIt begin, ForwardIt end) {
    for (ForwardIt i = begin; i != end; ++i) {
        std::rotate(std::upper_bound(begin, i, *i), i, std::next(i));
    }
}

        upper_bound返回已排序[begin,i)序列中第一个大于i所指向值的迭代器j。rotate把i翻转到j,[j,i)之间的数据往后移动。

        由于i是从begin开始迭代,所以可以保证[begin,i)区间是有序的。

        rotate后两参数——i和std::next(i)构成了[i,i+1)区间,即只有迭代器i。

快速排序

template <class ForwardIt>
void quick_sort(ForwardIt first, ForwardIt last) {
    if (first == last) return;
    auto pivot = *std::next(first, std::distance(first, last) / 2);
    ForwardIt middle1 = std::partition(first, last,
        [pivot](const auto& em) { return em < pivot; });
    ForwardIt middle2 = std::partition(middle1, last,
        [pivot](const auto& em) { return !(pivot < em); });
    quick_sort(first, middle1);
    quick_sort(middle2, last);
}

        pivot指向容器中位置处于中间的迭代器所指向的值。

        partition可以保证按照lambda表达式的结果,将序列分成两个区间,并返回第二个区间的首元素迭代器。

        middlle1的左边元素都是小于pivot,右边的都是大于等于pivot的。

        middle2指向的是大于pivot的元素区间首个迭代器。

        [middle1,middle2)就是所有等于pivot的元素。

        然后递归调用自身,分别处理[first,middle1)和[middle2,last)区间。

        由于partition是不稳定的,如果希望使用稳定的版本,可以使用partition_stable替代。

堆排序

template<class ForwardIt>
void heap_sort(ForwardIt first, ForwardIt last) {
    std::make_heap(first, last);
    std::sort_heap(first, last);
}

        由于C++对此封装太多,所有我们没法从名称上看到其算法光辉。

评测

class UtSort:
    public ::testing::Test
{
protected:
    virtual void SetUp() {
        _data.resize(_data_count);
        std::iota(_data.begin(), _data.end(), 1);

        _orded_data.assign(_data.begin(), _data.end());

        std::random_device rd;
        std::mt19937 g(rd());
        std::shuffle(_data.begin(), _data.end(), g);
    } 

    template<class ForwardIt>
    void test_the_same(ForwardIt begin, ForwardIt end) const {
        auto same_count = std::inner_product(begin, end,
                                            _orded_data.begin(), 0,
                                            std::plus<>(), std::equal_to<>());
        ASSERT_EQ(same_count, std::distance(begin, end));
    }
        
protected:
    std::vector<int> _data;
    decltype(_data) _orded_data;
    size_t _data_count = 1024 * 256;
};  

        我们使用gtest测试框架。

        第7行,我们构建了按1递增的数列_data,它是有序的。第9行将这个排序的数据保存到_orded_data中以供之后比较。第13行,我们将_data中的元素顺序打乱。

       第18行,将计算两个序列中,相同位置的值相等的格式。如果我们算法正确,则个数和传入的迭代器个数一致。

       为了测试每个排序的时间,我还设计了Perform用于统计时间

#include <gtest/gtest.h>
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <array>
#include <numeric>
#include <set>
#include <chrono>
#include <random>

using duration_mil = std::chrono::duration<double, std::milli>;

class Perform {
public:
    Perform() {
        _start = std::chrono::high_resolution_clock::now();
    }

    ~Perform() {
        _end = std::chrono::high_resolution_clock::now();
        duration_mil ms = _end - _start;
        std::cout << ms.count() << "ms" << std::endl;
    }
private:
    decltype(std::chrono::high_resolution_clock::now()) _start;
    decltype(std::chrono::high_resolution_clock::now()) _end;
};

        于是之前介绍的几种排序的测试代码是

TEST_F(UtSort, quick_sort) {
    {
        Perform perform;
        quick_sort(_data.begin(), _data.end());
    }
    test_the_same(_data.begin(), _data.end());
}

TEST_F(UtSort, heap_sort) {
    {
        Perform perform;
        heap_sort(_data.begin(), _data.end());
    }
    test_the_same(_data.begin(), _data.end());
}

TEST_F(UtSort, insertion_sort) {
    {
        Perform perform;
        insertion_sort(_data.begin(), _data.end());
    }
    test_the_same(_data.begin(), _data.end());
}

TEST_F(UtSort, merge_sort) {
    {
        Perform perform;
        merge_sort(_data.begin(), _data.end());
    }
    test_the_same(_data.begin(), _data.end());
}

TEST_F(UtSort, selection_sort) {
    {
        Perform perform;
        selection_sort(_data.begin(), _data.end());
    }
    test_the_same(_data.begin(), _data.end());
}

        除了这几种排序外,STL标准库还提供了其他几种方法

  • 使用partial_sort进行局部排序
  • 使用sort函数
  • 使用关系容器,比如set

        这三种的测试代码如下

TEST_F(UtSort, partial_sort) {
    {
        Perform perform;
        std::partial_sort(_data.begin(), _data.end(), _data.end());
    }
    test_the_same(_data.begin(), _data.end());
}

TEST_F(UtSort, stl_sort) {
    {
        Perform perform;
        std::sort(_data.begin(), _data.end());
    }
    test_the_same(_data.begin(), _data.end());
}


TEST_F(UtSort, set_sort) {
    std::set<int> ordered_data;
    {
        Perform perform;
        std::copy(make_move_iterator(_data.begin()), make_move_iterator(_data.end()), std::inserter(ordered_data, ordered_data.begin()));
    }
    test_the_same(ordered_data.begin(), ordered_data.end());
}

        这儿特别提一句,如果我们不需要全排序,只需要前N个元素是排序的,则可以优先考虑partial_sort。因为它的效率很高,比如下面代码测试排序最小的10个元素

TEST_F(UtSort, partial_sort_head_10) {
    {
        Perform perform;
        std::partial_sort(_data.begin(), std::next(_data.begin(), 10), _data.end());
    }
    test_the_same(_data.begin(), std::next(_data.begin(), 10));
}

        我们看下测试结果

[==========] Running 8 tests from 1 test case.
[----------] Global test environment set-up.
[----------] 8 tests from UtSort
[ RUN      ] UtSort.quick_sort
135.274ms
[       OK ] UtSort.quick_sort (168 ms)
[ RUN      ] UtSort.heap_sort
194.824ms
[       OK ] UtSort.heap_sort (225 ms)
[ RUN      ] UtSort.insertion_sort
2637.53ms
[       OK ] UtSort.insertion_sort (2667 ms)
[ RUN      ] UtSort.merge_sort
135.243ms
[       OK ] UtSort.merge_sort (165 ms)
[ RUN      ] UtSort.selection_sort
337051ms
[       OK ] UtSort.selection_sort (337083 ms)
[ RUN      ] UtSort.partial_sort
195.34ms
[       OK ] UtSort.partial_sort (225 ms)
[ RUN      ] UtSort.stl_sort
84.7456ms
[       OK ] UtSort.stl_sort (118 ms)
[ RUN      ] UtSort.set_sort
294.94ms
[       OK ] UtSort.set_sort (456 ms)
[ RUN      ] UtSort.partial_sort_head_10
2.51487ms
[       OK ] UtSort.partial_sort_head_10 (31 ms)
[----------] 8 tests from UtSort (340973 ms total)

[----------] Global test environment tear-down
[==========] 8 tests from 1 test case ran. (340973 ms total)
[  PASSED  ] 8 tests.

        完整排序中,std::sort是最快的,其次是quick_sort和merge_sort。heap_sort和partial_sort差不多。最差的是selection_sort。

        同时,我们看使用partial_sort只选出并排列最小的10个元素的耗时是2.51487毫秒。这比任何一个排序都要快两个数量级。

        所以根据不同场景,选择合适的排序非常重要。

        相关代码见:https://github.com/f304646673/stl_example/tree/master/sort

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++拾取——使用stl标准库实现排序算法及评测

            今天看了一篇文章,讲各种语言的优势和劣势。其中一个观点:haskell非常适合写算法,因为使用者不用去关心具体的计算机实现,而只要关注于操作语义...

    方亮
  • C++拾取——stl标准库中集合交集、并集、差集、对等差分方法

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    方亮
  • 一种解决启动进程传递参数过长的方法

            工作中,QA同学在测试我们程序的时候,发现在XP下,我们的A进程无法启动我们的B进程。而在Win7 64bit系统下功能正常。RD同学调试后,发...

    方亮
  • C++拾取——使用stl标准库实现排序算法及评测

            今天看了一篇文章,讲各种语言的优势和劣势。其中一个观点:haskell非常适合写算法,因为使用者不用去关心具体的计算机实现,而只要关注于操作语义...

    方亮
  • 1627: [Usaco2007 Dec]穿越泥地

    1627: [Usaco2007 Dec]穿越泥地 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 504  So...

    HansBug
  • FPGA学习altera系列: 第五篇 Verilog HDL基础语法及三种建模方式

    大侠好,欢迎来到FPGA技术江湖,江湖偌大,相见即是缘分。大侠可以关注FPGA技术江湖,在“闯荡江湖”、"行侠仗义"栏里获取其他感兴趣的资源,或者一起煮酒言欢。...

    FPGA技术江湖
  • 3298: [USACO 2011Open]cow checkers

    3298: [USACO 2011Open]cow checkers Time Limit: 10 Sec  Memory Limit: 128 MB Subm...

    HansBug
  • 务实推进新工科产学协同育人:腾讯公司与深圳大学合作举办敏捷研发研讨会

    2018年12月8日至9日,在教育部高等学校软件工程专业指导委员会指导下,由深圳大学计算机与软件学院承办,腾讯科技(深圳)有限公司与机械工业出版社华章分社联合...

    腾讯高校合作
  • 自己动手制作一个恶意流量检测系统(附源码)

    我们假设恶意C2C服务器IP是220.181.38.148(百度的某个节点),某个木马的恶意流量特征是?? ?? ?? ??(? 匹配所有)

    FB客服
  • Mysql锁

    在数据库中数据也是一种供许多用户共享的资源,如何保证数据并发访问的一致性,有效性是所有数据库必须解决的一个问题,锁冲突也是影响数据库并发访问性能的一个重要因素;

    彼岸舞

扫码关注云+社区

领取腾讯云代金券