比較排序算法的下界: 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
應用舉例:
假設我們想根據三個關鍵字年，月，日來對日期進行排序
對于這個問題，可以用帶有比較函數的排序算法來做，而另一方面，我們可以采用另一種方法，即用一種穩定的排序方法對所給的信息進行三次排序：先以日，其次對月，再對年