計數排序法是什麼
是一種線性時間複雜度O(n)的排序演算法，其中n為數列個數，適合處裡有限範圍整數數據集。基本原理計算每個元素出現次數，據計算後的元素次數做排序。
時間複雜度
掃描數列找出最大值時間複雜度O(n)，計算元素出現次數掃描數列時間複雜度O(n)，最後遍歷計數陣列輸出排序結果時間複雜度O(n)，所以計數排序法的時間複雜度為O(n)。
空間複雜度
- 輸入陣列，長度為n,的輸入陣列
- 計數陣列，取決於數值範圍最大值+1
- 輸出陣列，長度為n,的輸入陣列
故空間複雜度為O(n+k)，n為輸入資料長度，k為輸入數值範圍最大值。
- 輸入數值範圍很小，空間需求接近O(n)。
- 輸入數值範圍很大，空間需求接近為O(n+k)。
步驟
1. 建立計數陣列，每個索引對應一個數，計數陣列大小為數列中的最大值加1。
2. 遍歷數列，將元素次數填入計數陣列。計數陣列的索引指元素數值，計數陣列的數值需填入元素次數。
3. 照計數陣列輸出排序陣列，遍歷count陣列，遇到0值不做，遇其他值，按其他值（做幾次），將數列值放到output陣列。
舉例說明
有一個數列要用計數排序法排序[4, 2, 2, 8, 3, 3, 1]，數值範圍0-8。
1. 建立計數陣列count，初始值皆設0，大小為數列中的最大值加1，故大小為9。
2. 計算數值出現次數。
count=[0,1,2,2,1,0,0,0,1]
3. 照計數陣列輸出排序陣列，遍歷count陣列，遇到0值不做，遇其他值，按其他值（做幾次），將數列值放到output陣列。
output=[1,2,2,3,3,4,8]
沒有留言:
張貼留言
寫下幸福點子吧！