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

栏目: C++ · 发布时间: 6年前

内容简介:目前在网上讨论排序算法更多是C语言实现的。因为C语言可以展现出一些细节。但是从某种角度说,这也让“算法思想的光辉”被计算机操作细节所遮蔽。本文将使用C++的标准库去实现一些排序算法,我们从中将会发现它掩盖了很多计算机操作细节,而让算法的光辉得以显现。min_element返回两个索引之间最小元素的索引;iter_swap将最小索引和不停迭代的索引进行交换。这就是选择排序:逐位替换之后(包含自身)序列中最小的元素。

目前在网上讨论 排序 算法更多是 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 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, 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.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。heap_sort和partial_sort差不多。最差的是selection_sort。

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

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


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

数据结构与算法

数据结构与算法

卓滋德克 / 陈曙晖 / 清华大学出版社 / 2003-4-1 / 69.00

本书是一本介绍数据结构与算法的优秀书籍。 本书系统介绍了C++面向对象程序设计、算法复杂度、链表、栈、队列、递归、树、图、排序和查找算法、散列技术、数据压缩算法、内存管理等内容;尤其对递归算法进行了深入剖析。在附录中详细介绍了大O符号与标准模板库:在大多数章中提供了相应的实例分析和程序设计作业。 本书适合作为计算机软件专业或其他相关专业的教科书。对于需要参加计算机考试,......一起来看看 《数据结构与算法》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具