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

然而，計(jì)數(shù)排序和基數(shù)排序打破了規(guī)則的約束，僅僅在?(n)時(shí)間內(nèi)就能夠?qū)崿F(xiàn)對(duì)數(shù)組的排序。

背景：

§ 基于排序的規(guī)則：

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

§ 基于比較排序的下界：

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

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

關(guān)于此下界的說明：

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

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

使用計(jì)數(shù)排序超越下界：

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

首先通過計(jì)算出有多少個(gè)元素的排序關(guān)鍵字等于某個(gè)值，隨后就能計(jì)算出有多少個(gè)元素的排序關(guān)鍵字小于每個(gè)可能的排序—關(guān)鍵字值。

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

輸入 A：一個(gè)數(shù)組（數(shù)組內(nèi)元素取值范圍為介于0到m-1之間的整數(shù)）

n：數(shù)組A中的元素個(gè)數(shù)

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

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

步驟

1.創(chuàng)建一個(gè)新數(shù)組equal[0......m-1]。

2.令equal數(shù)組中的每個(gè)元素值均為0。

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

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

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

4.返回equal 數(shù)組。

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

接著通過equal數(shù)組的使用，得出對(duì)于每一個(gè)值，有多少個(gè)元素的排序關(guān)鍵字小于該值。

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

輸入 equal:由COUNT-KEYS-EQUAL返回的數(shù)組。

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

輸出 一個(gè)數(shù)組less[0......m-1]（對(duì)于j=0,1,2,...,m-1,less[j]=equal[0]+equal[1]+...+equal[j-1])。

步驟

1.創(chuàng)建一個(gè)新數(shù)組less[0......m-1]。

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

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

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

4.返回less數(shù)組。

很容易得出COUNT-KEYS-LESS程序能在?(m)時(shí)間內(nèi)運(yùn)行完成，并且它一定不會(huì)對(duì)排序關(guān)鍵字進(jìn)行比較。

接著可以創(chuàng)建一個(gè)排好序的數(shù)組，盡管并非原址排序：

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

輸入 A：一個(gè)數(shù)組（數(shù)組內(nèi)元素取值范圍為介于0到m-1之間的整數(shù)）

n：數(shù)組A中的元素個(gè)數(shù)

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

輸出 一個(gè)數(shù)組B（包含數(shù)組A中的元素，并且是排好序的）

步驟

1.創(chuàng)建新數(shù)組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.返回?cái)?shù)組B

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

第二步的循環(huán)首先確定了next數(shù)組的元素值，next[j]=l+1，其中l(wèi)=less[j]。

第三步的循環(huán)從左到右仔細(xì)檢查了數(shù)組A的值。對(duì)于每個(gè)元素A[i]，第3A步將A[i]存儲(chǔ)在key中，第3B步中計(jì)算出A[i]應(yīng)該存放在數(shù)組B中的索引位置index,第3C步將A[i]移動(dòng)到數(shù)組B中的這一索引位置上。因?yàn)閿?shù)組A中的下一元素應(yīng)該存放在數(shù)組B的下一個(gè)位置上，所以第3D步將next[key]值自增一。

將上面三個(gè)程序合并，形成計(jì)數(shù)排序(counting sort):

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

輸入 A：一個(gè)數(shù)組（數(shù)組內(nèi)元素取值范圍為0～m-1)

n：數(shù)組A中的元素個(gè)數(shù)

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

輸出 一個(gè)數(shù)組B（包含數(shù)組A中的元素，并且是排好序的）

步驟

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

2.調(diào)用COUNT-KEYS-LESS(equal, m),將該調(diào)用返回的結(jié)果賦值給數(shù)組less。

3.調(diào)用REARRANGE(A,less,n,m),將該調(diào)用返回的結(jié)果賦值給數(shù)組B。

4.返回?cái)?shù)組B。

計(jì)數(shù)排序能夠超越額比較排序的下界Ω(nlgn)，因?yàn)樗鼜膩聿粫?huì)對(duì)排序關(guān)鍵字進(jìn)行比較。反之，它將排序關(guān)鍵字作為數(shù)組的索引，能進(jìn)行這樣的操作是因?yàn)榕判蜿P(guān)鍵字均是非常小的整數(shù)，如果排序關(guān)鍵字是帶有分?jǐn)?shù)的實(shí)數(shù)，或者是字符串，那么我們就不能使用計(jì)數(shù)排序了。

計(jì)數(shù)排序還有另外一個(gè)特性：它是穩(wěn)定的。在一個(gè)穩(wěn)定的排序中，帶有相同排序關(guān)鍵字的元素在輸出數(shù)組中輸出的次序與它們?cè)谳斎霐?shù)組中的排序一致，即將輸入數(shù)組中的第一個(gè)元素放置在輸出數(shù)組中的第一個(gè)位置上。

運(yùn)行時(shí)間為?(n)，因?yàn)閷?duì)于n個(gè)學(xué)生的成績(jī)進(jìn)行排序時(shí)，成績(jī)?nèi)?#20540;為0～100，m=101是個(gè)常量（注意，待排序關(guān)鍵字的變化范圍是0～m-1）

基數(shù)排序：

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

當(dāng)基數(shù)排序使用計(jì)數(shù)排序來對(duì)每一位進(jìn)行排序時(shí)，它從來不會(huì)對(duì)兩個(gè)排序關(guān)鍵字進(jìn)行比較。它將每一位看作是計(jì)數(shù)排序中數(shù)組的索引。所以基數(shù)排序和計(jì)數(shù)排序能后超越比較排序的下界Ω(nlgn)。