比較排序算法的下界: O(nlogn)
非比較排序: 位排序，計數(shù)排序，基數(shù)排序
位排序適用于: 1. 輸入數(shù)據(jù)限制在相對較小的范圍內(nèi)； 2. 數(shù)據(jù)沒有重復； 3. 對于每條記錄而言，除了單一整數(shù)外，沒有任何其他關(guān)聯(lián)數(shù)據(jù)
計數(shù)排序
前提: n個輸入數(shù)據(jù)的每一個都是介于0到k之間的整數(shù)
時間復雜度: O(n)，如果k=O(n)
基本思想: 對于每個輸入元素x，統(tǒng)計出小于等于x的元素的個數(shù)，有了這個信息，就可以把x直接放到最終輸出數(shù)組的正確位置上
特點: 計數(shù)排序是穩(wěn)定的。計數(shù)排序的穩(wěn)定性，對于基數(shù)排序是至關(guān)重要的
代碼:
/*
* 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);
}
基數(shù)排序
基本思想: 按照最低有效位到最高有效位的順序（這里的位，可以看作是關(guān)鍵值），采用一種穩(wěn)定性排序算法對該位進行排序
偽代碼:
RADIX-SORT（A， d)
for i = 1..d /* 每一位，按低到高的順序 */
do use a stable sort to sort array A on digit i
應用舉例:
假設我們想根據(jù)三個關(guān)鍵字年，月，日來對日期進行排序
對于這個問題，可以用帶有比較函數(shù)的排序算法來做，而另一方面，我們可以采用另一種方法，即用一種穩(wěn)定的排序方法對所給的信息進行三次排序：先以日，其次對月，再對年