多少排序算法都是基于对序列中的元素进行比较操作来完成排序的，称这些排序算法为比较排序。如：快速排序（平均时间复杂度[latex]\Theta(n\lg{n})[/latex]，最坏时间复杂度[latex]\Omega(n\lg{n})[/latex]），随机快速排序（[latex]\Theta(n\lg{n})[/latex]），合并排序（[latex]\Theta(n\lg{n})[/latex]），堆排序（[latex]\Theta(n\lg{n})[/latex]），插入排序（[latex]\Theta(n^2)[/latex]）等。排序算法的时间复杂度的下限是[latex]\Omega(n\lg{n})[/latex]。

下面介绍几种非排序算法，这些算法的时间复杂度优于[latex]\Omega(n\lg{n})[/latex]。

(1) 计数排序（Counting Sort）

基本思想：统计输入序列中各数值的出现次数，进而统计小于等于某一数值的元素个数，最后根据该值确定各数值在排序后序列中的位置（若元素位置从1开始，则刚好等于小于等于该数值的元素个数）。

计数排序的时间复杂度为：[latex]\Theta(n+k)[/latex]。（输入元素的取值范围为0~k）

计数算法具有稳定性，即在序列中相同元素的出现顺序保持不变。计数排序用于小范围数（如8bit）时，具有非常好的性能；但当其用于大范围数（如32bit）时，它用于存储辅助序列的空间过大（~16GB）。

// 计数排序
// 计数排序
// data 输入序列
// outputData 输出序列
// count 输入序列长度（输出序列长度应与其相同）
// dataRange 输入序列元素值介于0~dataRange之间
void CountingSort(int *data, int *outputData, int count, int dataRange)
{
	if (count <= 0 || data == 0)
		return;

	// 初始化辅助空间
	int *counter = new int[dataRange];
	
	for (int i=0; i<dataRange; ++i)
	{
		counter[i] = 0;
	}

	// 统计数组中各数出现的次数
	for (int i=0; i<count; ++i)
	{
		counter[data[i]]++;
	}

	// 统计数组中小于等于各数的元素的数量
	for (int i=1; i<dataRange; ++i)
	{
		counter[i] += counter[i-1];
	}

	// 输出排序结果
	for (int i=count-1; i>=0; --i)
	{
		outputData[counter[data[i]] - 1] = data[i];	// 注意-1，数组中的位置下标始于0
		counter[data[i]]--;
	}

	delete []counter;
}

(2) 基数排序（Radix Sort）

基数排序主要用于大范围数的排序。

基本思想是按数据的各个位进行排序，先对最低位进行排序，然后是次低位，之到最高位。对每一位的排序过程中，需保持具有相同值的元素在输入序列中的顺序与输入序列不变，即排序算法具有稳定性，常使用计数排序。

基数排序的时间复杂度：给定n个b位数和任意正整数[latex]r\leq{b}[/latex]，如果采用的稳定排序算法时间复杂度为[latex]\Theta(n+k)[/latex]（如计数排序），则基数排序的时间复杂度为[latex]\Theta((b/r)(n+2^r))[/latex]。当[latex]b=O(\lg{n})[/latex]且选择[latex]r\approx{\lg{n}}[/latex]时，基数排序的时间复杂度为[latex]\Theta(n)[/latex]。

算法代码待添加

(3) 桶排序（Bucket Sort）

桶排序假设输入序列中的元素值在区间[0,1)上均匀分布。其基本思想是：

1) 把曲江[0,1)划分成n个大小相同的子区间（桶）

2) 将输入序列中的元素放入各桶中

3) 先对各桶中的元素进行排序（如插入排序）

4) 然后按次序把个桶中的元素输出。

桶排序的期望运行时间为：[latex]\Theta(n)[/latex]。