計數排序的簡單理解
詳細描述
計數排序作為一種線性時間複雜度的排序演算法,其要求輸入的數據必須是有確定範圍的整數,核心在於將輸入的數據值轉化為鍵存儲在額外開闢的數組空間中。
計數排序詳細的執行步驟如下:
- 找出原數組中元素值最大的,記為
max
; - 創建一個新數組
count
,其長度是max+1
,其元素默認值都為0
; - 遍歷原數組中的元素,以原數組中的元素作為
count
數組的索引,以原數組中的元素出現次數作為count
數組的元素值; - 創建結果數組
result
,起始索引index
; - 遍歷
count
數組,找出其中元素值大於0
的元素,將其對應的索引作為元素值填充到result
數組中去,每處理一次,count
中的該元素值減1
,直到該元素值不大於0
,依次處理count
中剩下的元素; - 返回結果數組
result
。
演算法圖解
問題解疑
計數排序的時間複雜度是多少?
計數排序的時間複雜度可以達到 \(O(n+k)\),其中 k 是 count
數組的長度。
從這裡可以知道,count
數組元素的取值越集中,演算法耗費的時間越短。
計數排序有什麼限制嗎?
計數排序有兩個前提需要滿足:
- 排序的元素必須是整數,否則無法對應數組的索引下標
- 排序元素的取值要在一定範圍內,並且比較集中,否則
count
數組將會非常大
只有這兩個條件都滿足,才能最大程度發揮計數排序的優勢。
程式碼實現
package cn.fatedeity.algorithm.sort;
/**
* 計數排序演算法
*/
public class CountSort {
public static int[] sort(int[] numbers) {
if (numbers.length == 0) {
return numbers;
}
int min = numbers[0], max = numbers[0];
for (int number : numbers) {
if (number < min) {
min = number;
} else if (number > max) {
max = number;
}
}
int[] count = new int[max - min + 1];
for (int number : numbers) {
int index = number - min;
count[index]++;
}
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
numbers[index++] = i + min;
count[i]--;
}
}
return numbers;
}
}