計數排序(Counting Sort)、基數排序(Radix Sort)


「計數排序(counting sort)」與「基數排序(radix sort)」可讓時間複雜度降為線性的 O(n),比合併排序(merge sort)堆積排序(heap sort)快速排序(quick sort)都還要快,但僅能用於整數排列,且若使用時機不恰當,時間複雜度將會大幅升高。


計數排序(counting sort)

計算每筆資料出現次數後,再依照目標順序一一放入長度為 k 的陣列中。

圖示

現假設有 n=10 筆資料 [6,8,8,9,4,4,4,3,2,1] 要由小到大排列,依序有下列三大步驟:

  1. 製作一長度為 k=10(索引值為 0~9)的陣列:
  2. 計算每筆資料出現次數:
  3. 將每筆資料依出現次數照順序放入陣列中:

    排序完成後結果如下:

時間複雜度

共可分為三大步驟討論:

  1. 製作長度為 k 的陣列:時間複雜度為 O(k)。
  2. 計算 n 筆資料出現次數:時間複雜度為 O(n)。
  3. 把 n 筆資料依序排列至長度為 k 的陣列中:時間複雜度為 O(n+k)。

為了維持線性的時間複雜度,k 的值不能太大。


基數排序(radix sort)

將不同位元分開依序比較,比到最高位元後即完成排序。

圖示

現假設有 [264, 658,135] 三筆資料要由小到大排序,過程如下:

  1. 將最低位數由小到大以「counting sort」排序:
  2. 將次低位數由小到大以「counting sort」排序,原排好的最低位數也隨著調整:
  3. 將最高位數由小到大以「counting sort」排序,原排好的較低位數也隨著調整:

    最終得結果為 [135, 264, 658]。

時間複雜度

每一位元都用「counting sort」排序,因此排序每位元時間複雜度皆為 O(n+k);若設共有 d 位元要排序,時間複雜度為 O(d·(n+k))。

現設排序資料中最大者有 S 位數,再將 d 換底成 a,則 d=(logₐ S),即 S 共有 (logₐ S) 位元,此時時間複雜度變為 O(d·(n+a)),將 d 以 (logₐ S) 代換,時間複雜度變成 O((logₐ S)·(n+k))。

根據經驗法則,若要使「(logₐ S)·(n+a)」為最小,k 應取 O(n),時間複雜度 O((logₐ S)·(n+k)) 變成 O((logₙ S)·n),在 S≤nᶜ、即未排序資料中最大者位元數量不超過資料個數時,O((logₙ S)·n)=O(c·n),c 為常數,O(c·n) 為線性時間複雜度。

「radix sort」的時間複雜度為 O(c·n),屬線性時間

如果未排序資料中最大者 S 的位元數遠比資料個數多(如共 5 筆資料要排序,但最大值 S 有 10¹⁰ 位元),「radix sort」要從最小位數排到 10¹⁰ 位元處,不僅無法維持線性的時間複雜度,還會大幅超越合併排序(merge sort)堆積排序(heap sort)快速排序(quick sort)等其他時間複雜度為 O(n·log n) 的排序演算法。

#演算法 #計數排序 #基數排序







你可能感興趣的文章

覺得 JavaScript function 很有趣的我是不是很奇怪

覺得 JavaScript function 很有趣的我是不是很奇怪

for ...in   for...of   forEach

for ...in for...of forEach

Progressive Web App 會是未來趨勢嗎?

Progressive Web App 會是未來趨勢嗎?






留言討論