最佳化 C++/通用最佳化技術/排序

C++ 標準模板庫 (STL) 提供模板函式 sort，它實現了一個比較排序演算法。由於 sort 是模板化的，因此它可用於各種型別的序列，這些序列包含任何型別的鍵，只要這些鍵是可比較的（實現 < 運算子）。一個好的編譯器可以生成針對各種序列/鍵組合最佳化的程式碼。

STL 的參考實現使用 introsort 演算法（自 2000 年釋出以來；GNU C++ 庫使用參考實現）。該演算法是快速排序和堆排序的快速組合，並帶有專門設計的選擇演算法。

sort 模板函式不能保證是穩定的。如果需要穩定排序，請改用 stable_sort 模板函式。

本節建議使用替代 sort 和 stable_sort 模板函式的方案，這些方案在特定情況下可能更快。

對小範圍鍵進行排序

要根據具有小範圍的整數鍵對資料集進行排序，請使用 計數排序 演算法。

計數排序 演算法的複雜度為 O(N+M)，其中 N 是要排序的元素數量，M 是排序鍵的範圍，即最高鍵和最低鍵之間的差。如果要排序的 N 個元素的鍵是屬於不超過 2 倍 N 個值的區間的整數（即當 M <= 2 * N 成立時），則該演算法可能比 sort 快得多。在某些情況下，它甚至在更大的範圍內更快。

該演算法也可用作部分排序；例如，如果鍵是 0 到 10 億之間的整數，則仍然可以使用最高有效位元組對它們進行排序，以便得到滿足公式 $a_{n}<a_{n+1}+256*256*256$ 的順序。

示例：排序 8 位整數

假設您要對任意 unsigned char 元素陣列進行排序。<climits> 為特定實現定義了整數和字元型別的常量限制。CHAR_BIT 是 char 物件中的位數。ISO C++ 要求 CHAR_BIT 為 8 或更大。unsigned char 的值範圍在 0 到 UCHAR_MAX 之間。ISO C++ 要求 UCHAR_MAX 為 255 (2^8-1) 或更大。

注意：必須使用 unsigned char，因為 char 可以根據實現是有符號還是無符號。

#include <climits>

void count_sort(unsigned char *a, unsigned char *const end)
{
	unsigned char freq[UCHAR_MAX+1] = {0};
	unsigned char *p, c;
	
	for (p = a; p < end; ++p) {
		freq[*p] += 1;
	}
	for (c = 0, p = a; c < UCHAR_MAX; ++c) {
		while (freq[c]-- > 0) {
			*p++ = c;
		}
	}
	while (freq[c]-- > 0) {
		*p++ = c;
	}
}

counting_sort 函式實現鴿巢排序演算法。它接收輸入陣列第一個元素的指標和指向陣列末尾之後的一個元素的指標。為什麼？因為我們不必在這裡停止。

我們可以將 counting_sort 泛化為模板函式，該函式也適用於 string、vector<unsigned char> 和其他序列型別，而不會損失效率。這樣做時，我們需要使用迭代器而不是指標。

#include <iterator>
#include <limits>

template <typename iterator>
void counting_sort(iterator const &begin, iterator const &end)
{
	typedef std::iterator_traits<iterator>::value_type T;
	T max = std::numeric_limits<T>::max();
	T freq[max+1] = {0};
	iterator it;
	T c;

	for (it = begin; it < end; ++it) {
		freq[*it] += 1;
	}
	for (c = 0, it = begin; c < max; ++c)
		while (freq[c]-- > 0) {
			*it++ = c;
		}
	}
	while (freq[c]-- > 0) {
		*it++ = c;
	}
}

部分排序

分割槽

如果您必須根據某個標準拆分序列，請使用分割槽演算法，而不是排序演算法。

在 STL 中，有 std::partition 演算法，它比 std::sort 演算法快，因為它具有 O(N) 複雜度，而不是 O(N log(N))。

穩定分割槽和排序

如果您必須對可能交換等效實體的序列進行分割槽或排序，請勿使用穩定演算法。

在 STL 中，有 std::stable_partition 分割槽演算法，它比 std::partition 演算法略慢；並且有 std::stable_sort 排序演算法，它比 std::sort 演算法略慢。

順序分割槽

如果您必須從序列中選出前 N 個元素，或者選出序列中的第 N 個元素，請使用順序分割槽演算法，而不是排序演算法。

在 STL 中，有 std::nth_element 演算法，雖然它比 std::stable_partition 演算法略慢，但它比 std::sort 演算法快得多，因為它具有 O(N) 複雜度，而不是 O(N log(N))。

僅排序前 N 個元素

如果您必須對更長序列的前 N 個元素進行排序，請使用順序統計算法，而不是排序演算法。

在 STL 中，有 std::partial_sort 和 std::partial_sort_copy 演算法，雖然它們比 std::nth_element 演算法慢，但它們比 std::sort 演算法快得多，因為要排序的部分序列比整個序列短。