比较排序算法的下界: O(nlogn)
非比较排序: 位排序，计数排序，基数排序
位排序适用于: 1. 输入数据限制在相对较小的范围内； 2. 数据没有重复； 3. 对于每条记录而言，除了单一整数外，没有任何其他关联数据
计数排序
前提: n个输入数据的每一个都是介于0到k之间的整数
时间复杂度: O(n)，如果k=O(n)
基本思想: 对于每个输入元素x，统计出小于等于x的元素的个数，有了这个信息，就可以把x直接放到最终输出数组的正确位置上
特点: 计数排序是稳定的。计数排序的稳定性，对于基数排序是至关重要的
代码:
/*
* counting-sort: stable, O(n)
* precondition: the value of n input integers must between 0 and k, k = O(n)
*/
void
counting_sort(int *array, int *ret, int n, int k)
{
int i, j, *count = (int *)malloc((k+1) * sizeof(int));
assert(count != NULL);
memset(count, 0, sizeof(int)*(k+1));
for(i=0; i<n; ++i) {
assert(array[i]>=0 && array[i]<=k);
++count[array[i]];
}
for(i=1; i<=k; ++i)
count[i] += count[i-1];
for(j=n-1; j>=0; --j) {
ret[count[array[j]]-1] = array[j];
--count[array[j]];
}
free(count);
}
基数排序
基本思想: 按照最低有效位到最高有效位的顺序（这里的位，可以看作是关键值），采用一种稳定性排序算法对该位进行排序
伪代码:
RADIX-SORT（A， d)
for i = 1..d /* 每一位，按低到高的顺序 */
do use a stable sort to sort array A on digit i
应用举例:
假设我们想根据三个关键字年，月，日来对日期进行排序
对于这个问题，可以用带有比较函数的排序算法来做，而另一方面，我们可以采用另一种方法，即用一种稳定的排序方法对所给的信息进行三次排序：先以日，其次对月，再对年