C++拾取——使用stl標準庫實現排序演算法及評測
目前在網上討論排序演算法更多是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毫秒。這比任何一個排序都要快兩個數量級。
所以根據不同場景，選擇合適的排序非常重要。