[Counting Sort, Radix Sort] 計數排序, 基數排序

 Counting Sort是一種效率很高的排序方式，複雜度為$\ord{n+k}$，其中$k$是Bucket的大小，由此可知僅限於整數且數字範圍不能太大。根據觀察在很多應用中會有對物件以編號大小進行排序的行為，在這方面應該能做到很大的加速。

另外一個問題是Counting Sort雖然簡單，很多人甚至可以自己想到實作方法，但這也導致了標準的作法常常被人忽略。因此這裡就來給大家展示標準的Counting sort：

	#include <algorithm>
	#include <numeric>
	template <typename InputIter, typename OutputIter, typename BucketIter,
	typename KeyFunction>
	void counting_sort(InputIter First, InputIter Last, BucketIter BucketFirst,
	BucketIter BucketLast, OutputIter OutputFirst,
	KeyFunction Key) {
	std::fill(BucketFirst, BucketLast, 0);
	for (auto Iter = First; Iter != Last; ++Iter)
	++(*(BucketFirst + Key(*Iter)));
	std::partial_sum(BucketFirst, BucketLast, BucketFirst);
	do {
	--Last;
	*(OutputFirst + --(*(BucketFirst + Key(*Last)))) = std::move(*Last);
	} while (Last != First);
	}

view raw CountingSort.hpp hosted with ❤ by GitHub

參數的解釋如下：

• First, Last:
  和std::sort的定義一樣，需要排序的範圍，注意不一定要是random access iterator。
• BucketFirst, BucketLast:
  Counting Sort正統的實作方式會有一個正整數陣列作為Bucket，考量到各種應用所以這裡接傳Bucket的範圍進來能做的優化會比較多，必須要是random access iterator。
• OutputFirst:
  Counting Sort的output是直接將input存到另一個陣列中，因此OutputFirst指的是Output陣列的開頭，必須要是random access iteator，且要注意output的空間是足夠的。這邊將input存進output時是用std::move的方式，如果想要保留原本input的話可以將其拿掉。
• Key:
  這是一個函數，Key(x)必須要回傳一個0~(BucketLast-BucketFirst-1)的正整數作為被排序物件x的關鍵值。

有了Counting sort，Radix Sort就比較好解釋了。首先正統的Counting sort是stable sort，所以Key值相同的東西排序前後的先後順序是不變的。因此可以透過多次的Counting Sort來完成一些原本Counting Sort無法完成的事情。

以整數(int, -2147483648~2147483647)排序為例，可以先針對第十億位做為Key進行排序，接著再對第一億位做為Key、第一千萬位做為Key...直到十位數、個位數作為Key，最後再以正負號最為Key進行排序，這樣就可以完成一般範圍的整數排序。

實際上一般不會這樣用，通常是用在有多個Key值的情況，以下面的程式碼來說，可以自行執行看看花費的時間有多少：

	#include "CountingSort.hpp"
	#include <cassert>
	#include <chrono>
	#include <iostream>
	#include <random>
	#include <vector>
	using namespace std;
	int main() {
	vector<pair<int, int>> V1;
	mt19937 MT(7122);
	const int N = 10000000, A = 1000, B = 10000;
	for (int i = 0; i < N; ++i) {
	V1.emplace_back(MT() % A, MT() % B);
	}
	decltype(V1) V2 = V1;
	auto Begin = chrono::high_resolution_clock::now();
	sort(V2.begin(), V2.end());
	auto End = chrono::high_resolution_clock::now();
	cout << "std::sort: "
	<< chrono::duration_cast<chrono::milliseconds>(End - Begin).count()
	<< "ms\n";
	Begin = chrono::high_resolution_clock::now();
	decltype(V2) Tmp(V1.size());
	vector<int> Bucket(max(A, B), 0);
	counting_sort(V1.begin(), V1.end(), Bucket.begin(), Bucket.begin() + B,
	Tmp.begin(), [&](const auto &P) -> int { return P.second; });
	counting_sort(Tmp.begin(), Tmp.end(), Bucket.begin(), Bucket.begin() + A,
	V1.begin(), [&](const auto &P) -> int { return P.first; });
	End = chrono::high_resolution_clock::now();
	cout << "radix_sort: "
	<< chrono::duration_cast<chrono::milliseconds>(End - Begin).count()
	<< "ms\n";
	assert(V1 == V2);
	return 0;
	}

view raw main.cpp hosted with ❤ by GitHub