优化 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 算法快得多，因为要排序的部分序列比整个序列短。