只需線性時間的超快排序法─計數排序法(Counting Sort)


這裡所稱的排序(Sorting),是指將一串不規則的數值資料(如陣列資料)依照遞增或是遞減的方式重新編排。要將一串不規則的數值資料遞增或是遞減排列,方法當然不會只有一種,而不同方法排列資料的難易度、速度和其它特性自然也會有所不同。排序演算法(Sorting Algorithm)就是排列資料的方法,目前已知的方法有很多,本站先前已經介紹過實用的六種排序演算法(氣泡排序交換排序選擇排序插入排序快速排序合併排序),而在本篇文章中將會介紹比這六種排序法還要更快速的「計數排序(Counting Sort)」。

計數排序法(Counting Sort)

計數排序法的概念

計數排序法是一種只需要線性的時間和空間的排序演算法,但它並不算是常見的排序演算法,因為它只能用來排序已知的一組數值(由於要直接對應陣列索引值,所以這組數值通常會是一組整數)。舉例來說,已知陣列中的每個元素(或是其它要用來作為排序依據的屬性)是數值範圍n到m中的任一整數,那麼我們便可以使用計數排序法來排序這個陣列。計數排序法的思路不同於文章首段中提到的六種排序演算法,它排序元素的方式並不是去「比較」兩元素間的大小,而是先去計算每個元素(或是其作為排序依據的屬性)在陣列中出現的次數,再利用這個次數資訊去進行更進一步的排序,以下將說明兩種不同的應用情形。

首先,第一種作法是,在取得次數資訊之後,直接把已知的那一組數值中的數,依序根據其出現的次數填寫到原本要排序的陣列中,填寫完成後該陣列也就排序完了。舉例來說,已知陣列中的元素均為1, 2, 3, 4其中一個數值,陣列中實際儲存的內容為[3, 2, 1, 2, 3, 3, 1],我們可以先計算出這個陣列共有2個1、2個2、3個3、和0個4。接著就開始把數值依序填寫進這個陣列中,首先填入2個1,陣列內容會變成[1, 1, 1, 2, 3, 3, 1]。再來填入2個2,陣列內容會變成[1, 1, 2, 2, 3, 3, 1]。再來填入3個3,陣列內容會變成[1, 1, 2, 2, 3, 3, 3]。最後的4由於原先就沒有出現,所以不用填寫,此時陣列已經排序完成。這樣的排序方式十分簡單快速,屬於「原地(in-place)」的作法,適用在被排序的元素就是用來作為排序依據的數值。也就是說,若要排序一個整數陣列的話,可以直接使用這個方式。

再來,第二種作法是,在取得次數資訊之後,還要再對它依序進行累加。同樣地,以上面那個例子來說,已知陣列中的元素均為1, 2, 3, 4其中一個數值,而陣列中實際儲存的內容為[3, 2, 1, 2, 3, 3, 1],在計算出陣列中有2個1、2個2、3個3、和0個4之後,可以將其累加成「有2 + 0 = 2個元素小於等於1」、「有2 + 2 = 4個元素小於等於2」、「有4 + 3 = 7個元素小於等於3」、「有7 + 0 = 7個元素小於等於4」。接著產生出另一個相同大小的空陣列,並從這個原陣列的尾端開始將所有元素放入新陣列中,至於這些元素要放在新陣列中的哪個位置,可以去查詢我們剛才累加出來的結果。一開始我們會從原陣列的尾端拿到「1」這個元素,並且發現到目前「有2個元素小於等於1」,於是把「1」這個元素放到陣列中第二個位置(也就是索引1的位置),再把「1」這個元素的大小累計結果減一,此時新陣列的內容為[?, 1, ?, ?, ?, ?, ?]。接著從原陣列中拿到下一個元素「3」,並且發現到目前「有7個元素小於等於3」,於是把「3」這個元素放到陣列中第七個位置(也就是索引6的位置),再把「3」這個元素的大小累計結果減一,此時新陣列的內容為[?, 1, ?, ?, ?, ?, 3]。接著從原陣列中拿到下一個元素,還是「3」,並且發現到此時「有6個元素小於等於3」,於是把「3」這個元素放到陣列中第六個位置(也就是索引5的位置),再把「3」這個元素的大小累計結果減一,此時新陣列的內容為[?, 1, ?, ?, ?, 3, 3]。接下來的步驟依此類推,新陣列的內容變化為[?, 1, ?, ?, ?, 3, 3]→[?, 1, ?, 2, ?, 3, 3]→[1, 1, 2, ?, 3, 3]→[1, 1, 2, 2, ?, 3, 3]→[1, 1, 2, 2, 3, 3, 3]。這樣的排序方式稍微複雜一點,而且會需要額外的陣列來儲存結果,屬於「非原地(out-of-place)」的作法,但其元素的順序是穩定的(stable),且適用於「用來作為排序依據的數值不直接是被排序的元素,而是該元素的某個屬性」的情形。

計數排序法的過程

雖然上述的概念講解已經有提到計數排序的過程,但這邊會用更為複雜的例子來完整演示一次。

已知陣列中的元素均為0到9(包含0和9)中的一個整數數值,假設現在有個要排序的陣列,內容如下:

由於現在要排序的資料是整數資料,因此前面提到的第一種(in-place)和第二種(out-of-place)的計數排序法皆可以使用。

然而不管使用哪種方式,都要先計算出數值組中的各項數值在陣列中出現的次數。

由於待排序陣列的元素只能是0到9(包含0和9)中的一個整數數值,因此陣列元素為有(9 - 0 + 1) = 10種可能的數值。所以要建立出一個大小為10的整數陣列,陣列索引i的位置儲存表示數值i在待排序陣列中出現的次數。計算之後我們得到了如下的計數陣列:

in-place 計數排序

由於0和1的數量都是0,因此無需填寫到新陣列中。

將1個2填寫到新陣列中。

將3個3填寫到新陣列中。

將1個4填寫到新陣列中。

由於5的數量是0,因此無需填寫到新陣列中。

將1個6填寫到新陣列中。

由於7的數量是0,因此無需填寫到新陣列中。

將1個8填寫到新陣列中。

將2個9填寫到新陣列中。

out-of-place 計數排序

累加計數陣列。

建立與待排序陣列同等大小的新陣列。

從原來待排序的陣列之尾端開始將所有元素放入新陣列。

將元素「3」填入新陣列的第四個位置(索引3)。

從待排序的陣列中找下一個元素放入。

將元素「6」填入新陣列的第六個位置(索引5)。

從待排序的陣列中找下一個元素放入。

將元素「4」填入新陣列的第五個位置(索引4)。

從待排序的陣列中找下一個元素放入。

將元素「2」填入新陣列的第一個位置(索引0)。

從待排序的陣列中找下一個元素放入。

將元素「9」填入新陣列的第九個位置(索引8)。

從待排序的陣列中找下一個元素放入。

將元素「3」填入新陣列的第三個位置(索引2)。

從待排序的陣列中找下一個元素放入。

將元素「3」填入新陣列的第二個位置(索引1)。

從待排序的陣列中找下一個元素放入。

將元素「8」填入新陣列的第七個位置(索引6)。

從待排序的陣列中找下一個元素放入。

將元素「9」填入新陣列的第八個位置(索引7)。

至此排序已完成!

計數排序法的程式實作

計數排序法的複雜度

以「n」來表示待排序的陣列大小,「k」來表示用來作為排序依據的數值的所有可能之數量。

in-place 計數排序

最差時間複雜度:O(n+k)

最佳時間複雜度:O(n+k)

平均時間複雜度:O(n+k)

額外最差空間複雜度:O(k)

out-of-place 計數排序

最差時間複雜度:O(n+k)

最佳時間複雜度:O(n+k)

平均時間複雜度:O(n+k)

額外最差空間複雜度:O(n+k)

排序演算法速度測試

本站先前介紹過的六種實用排序演算法中,最佳化的快速排序法排序速度可以說是最好的。現在就來比較看看最佳化的快速排序法計數排序法的計算時間之差異吧!

測試一:排序長度為10000000,元素數值範圍在-103~103之間的整數陣列

亂序陣列:

最佳化的快速排序法:6607 ms
in-place的計數排序法:23 ms
out-of-place的計數排序法:175 ms

正序陣列:

最佳化的快速排序法:5735 ms
in-place的計數排序法:22 ms
out-of-place的計數排序法:175 ms

反序陣列:

最佳化的快速排序法:5615 ms
in-place的計數排序法:23 ms
out-of-place的計數排序法:179 ms

測試二:排序長度為1000000,元素數值範圍在-103~103之間的整數陣列

亂序陣列:

最佳化的快速排序法:171 ms
in-place的計數排序法:9 ms
out-of-place的計數排序法:25 ms

正序陣列:

最佳化的快速排序法:99 ms
in-place的計數排序法:1 ms
out-of-place的計數排序法:61 ms

反序陣列:

最佳化的快速排序法:136 ms
in-place的計數排序法:2 ms
out-of-place的計數排序法:23 ms

測試三:排序長度為1000000,元素數值範圍在-105~105之間的整數陣列

亂序陣列:

最佳化的快速排序法:137 ms
in-place的計數排序法:11 ms
out-of-place的計數排序法:41 ms

正序陣列:

最佳化的快速排序法:29 ms
in-place的計數排序法:5 ms
out-of-place的計數排序法:70 ms

反序陣列:

最佳化的快速排序法:495 ms
in-place的計數排序法:5 ms
out-of-place的計數排序法:19 ms

測試四:排序長度為1000000,元素數值範圍在-108~108之間的整數陣列

亂序陣列:

最佳化的快速排序法:149 ms
in-place的計數排序法:232 ms
out-of-place的計數排序法:243 ms

正序陣列:

最佳化的快速排序法:37 ms
in-place的計數排序法:171 ms
out-of-place的計數排序法:569 ms

反序陣列:

最佳化的快速排序法:56 ms
in-place的計數排序法:195 ms
out-of-place的計數排序法:280 ms

結論

在多數情況下,計數排序法比最佳化的快速排序法還要快,而且當n愈大、k愈小時,兩者速度差異會更加明顯。但k如果比n還大很多時,最佳化的快速排序法則會比計數排序法還要快。所以在實務上,若資料需要根據整數進行排序,且如果可以的話,最好事先確定要排序之對象的n和k,如此一來將有助於選擇適當的演算法來加快程式的運行速度!

關於作者

Magic Len

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章