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