在一些特定的規則下，排序的時間復雜度不能超越?(nlgn)

然而，計數排序和基數排序打破了規則的約束，僅僅在?(n)時間內就能夠實現對數組的排序。

背景：

§ 基于排序的規則：

選擇，插入，歸并，快速排序算法，在確定排序順序時都僅僅依賴于對排序關鍵字對進行比較，它們確定決策時的依據均是”如果這個元素的排序關鍵字比另一個元素的排序關鍵字小，那么就進行相應操作，否則，進行其他操作或者什么也不做”

§ 基于比較排序的下界：

將比較排序定義為僅僅通過比較元素對來確定排序順序，

Ω符號給出了下界，因此稱“對于任意大的n，任何比較排序算法在最壞情況下至少需要cnlgn次比較操作（對于某個常量c成立)”由于每次比較至少需要花費常量時間，對于n個元素的基于比較的排序操作，能夠得出一個時間為Ω(nlgn)的下界。

關于此下界的說明：

1.它僅僅指最壞情況。在最壞情況下，該排序必定需要Ω（nlgn)次比較操作。

2.Ω(nlgn)這一下界不依賴于任何算法，只要該算法是一個比較排序。

使用計數排序超越下界：

假設我們知道排序關鍵字是0到m-1范圍內的整數，并且假定我們知道剛好有3個元素的排序關鍵字等于5并且剛好有6個元素的排序關鍵字小于5，那么可得，在排好序的數組中，排序關鍵字等于5的元素應該位于位置7，8，9上。更一般地講，如果已知有k個元素的排序關鍵字等于x，而l 個元素的排序關鍵字小于x，那么可得，排序關鍵字等于x的元素應該位于位置l+1到l+k之間。因此，我們需要計算出對于每個可能的排序—關鍵字值，有多少個元素的排序關鍵字小于那個值，又有多少個元素的排序關鍵字等于那個值。

首先通過計算出有多少個元素的排序關鍵字等于某個值，隨后就能計算出有多少個元素的排序關鍵字小于每個可能的排序—關鍵字值。

程序 COUNT-KEYS-EQUAL(A,n,m)

輸入 A：一個數組（數組內元素取值范圍為介于0到m-1之間的整數）

n：數組A中的元素個數

m：定義了數組A中元素的取值范圍

輸出 一個數組equal[0......m-1](equal[j]表示數組A中元素值等于j的元素個數，j=0,1,2,...,m-1)。

步驟

1.創建一個新數組equal[0......m-1]。

2.令equal數組中的每個元素值均為0。

3.令i從1到n依次取值

A.key被賦值為A[i]。

B.將equal[key]的值自增一。

4.返回equal 數組。

<步驟2執行了m次迭代，步驟3執行了n次迭代，并且每次循環的每次迭代均會耗費常量時間，COUNT-KEYS-EQUAL花費的時間為?(m+n)。如果m是一個常數，那么COUNT-KEYS-EQUAL花費的時間為?(n)。

接著通過equal數組的使用，得出對于每一個值，有多少個元素的排序關鍵字小于該值。

程序 COUNT-KEYS-LESS(equal, m)

輸入 equal:由COUNT-KEYS-EQUAL返回的數組。

m：定義了equal數組中的索引的取值范圍：0~m-1。

輸出 一個數組less[0......m-1]（對于j=0,1,2,...,m-1,less[j]=equal[0]+equal[1]+...+equal[j-1])。

步驟

1.創建一個新數組less[0......m-1]。

2.將less[0]賦值為0。

3.令j從1到m-1依次取值：

A.將less[j]賦值為less[j-1]+equal[j-1]。

4.返回less數組。

很容易得出COUNT-KEYS-LESS程序能在?(m)時間內運行完成，并且它一定不會對排序關鍵字進行比較。

接著可以創建一個排好序的數組，盡管并非原址排序：

程序 REARRANGE(A,less,n,m)

輸入 A：一個數組（數組內元素取值范圍為介于0到m-1之間的整數）

n：數組A中的元素個數

m：定義了數組A中元素的取值范圍

輸出 一個數組B（包含數組A中的元素，并且是排好序的）

步驟

1.創建新數組B[1...n],next[0...m-1]

2.令j從0到m-1依次取值：

A.將next[j]賦值為less[j]+1

3.令i從1到n依次取值：

A.將key賦值為A[i]

B.將index賦值為next[key]

C.將B[index]賦值為A[i]

D.將next[key]自增一

4.返回數組B

該思想如下，從左到右檢查數組A時，next[j]指出了原本在數組A中的下一個值為j的元素應該存放在數組B中的索引位置。

第二步的循環首先確定了next數組的元素值，next[j]=l+1，其中l=less[j]。

第三步的循環從左到右仔細檢查了數組A的值。對于每個元素A[i]，第3A步將A[i]存儲在key中，第3B步中計算出A[i]應該存放在數組B中的索引位置index,第3C步將A[i]移動到數組B中的這一索引位置上。因為數組A中的下一元素應該存放在數組B的下一個位置上，所以第3D步將next[key]值自增一。

將上面三個程序合并，形成計數排序(counting sort):

程序 COUNTING-SORT(A,n,m)

輸入 A：一個數組（數組內元素取值范圍為0～m-1)

n：數組A中的元素個數

m：定義了數組A中元素的取值范圍

輸出 一個數組B（包含數組A中的元素，并且是排好序的）

步驟

1.調用COUNT-KEYS-EQUAL(A,n,m),將該調用返回的結果賦值給數組equal。

2.調用COUNT-KEYS-LESS(equal, m),將該調用返回的結果賦值給數組less。

3.調用REARRANGE(A,less,n,m),將該調用返回的結果賦值給數組B。

4.返回數組B。

計數排序能夠超越額比較排序的下界Ω(nlgn)，因為它從來不會對排序關鍵字進行比較。反之，它將排序關鍵字作為數組的索引，能進行這樣的操作是因為排序關鍵字均是非常小的整數，如果排序關鍵字是帶有分數的實數，或者是字符串，那么我們就不能使用計數排序了。

計數排序還有另外一個特性：它是穩定的。在一個穩定的排序中，帶有相同排序關鍵字的元素在輸出數組中輸出的次序與它們在輸入數組中的排序一致，即將輸入數組中的第一個元素放置在輸出數組中的第一個位置上。

運行時間為?(n)，因為對于n個學生的成績進行排序時，成績取值為0～100，m=101是個常量（注意，待排序關鍵字的變化范圍是0～m-1）

基數排序：

基數排序算法中，我們假定將每個排序關鍵字看作是d位數字，其中每一位取值為0~m-1,我們自右向左地對每一位上的數字進行穩定排序，如果使用計數排序作為這一穩定排序算法，每位上的排序時間為?(m+n)，那么對d位進行排序的總時間為?(d(m+n))。如果m是一個常量，那么基數排序的時間為?(dn)。如果d也是一個常量，那么基數排序的時間僅僅為?(n)。

當基數排序使用計數排序來對每一位進行排序時，它從來不會對兩個排序關鍵字進行比較。它將每一位看作是計數排序中數組的索引。所以基數排序和計數排序能后超越比較排序的下界Ω(nlgn)。