内容简介:目前在网上讨论排序算法更多是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毫秒。这比任何一个排序都要快两个数量级。
所以根据不同场景,选择合适的排序非常重要。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- C++拾取——使用STD标准库简化代码
- three中蒙皮动画(skinnedMesh)的拾取(raycaster)问题
- C++拾取——stl标准库中集合交集、并集、差集、对等差分方法
- C++拾取——Linux下实测布隆过滤器(Bloom filter)和unordered_multiset查询效率
- 通俗易懂--决策树算法、随机森林算法讲解(算法+案例)
- 限流算法之漏桶算法、令牌桶算法
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。