這是用於整數數組或以整數為鍵的結構的排序演算法。當整數範圍與輸入大小相同時特別有用。
主要思想是決定整數出現的頻率，並用它來決定排序順序。
範例：假設我們得到陣列 {1,3,1,2}。
先決定此輸入的整數範圍，最大值和最小值，1 和 3。
接下來建立一個數組，稱為 counts 數組，即整數範圍的大小+1，因此在本例中為 3 (3-1+1)。
迭代輸入數組，增加對應條目的計數。給定輸入值的計數將放置在 counts[value - min] 處。對於給定的輸入，counts[0] 將保存值 1 的計數。
這會產生計數數組：{2,1,1}
現在確定累計計數，本質上是 counts[i] = counts[i-1]+counts[i]。
這會產生累積計數數組：{2,3,4}
為排序後的輸入建立輸出數組。
現在，以相反的順序迭代輸入。
在每個步驟中，檢索輸入數組中值的累積計數。該值將被放置在與檢索到的計數 - 1 相對應的輸出陣列索引處。然後遞減累積計數值。
在第一步驟中，檢索值 2 且累積計數為 3。該值應放置在輸出中的索引 2 (3-1) 處。
下次迭代時，值1，累計計數2；所以這個「1」被放置在輸出的索引 1 (2-1) 處。
繼續，數值3，累計次數4；將其放置在輸出的索引 3 處。
最後，第二次值為1，累計計數為1（因為第一次看到計數就遞減了）；所以這個「1」被放置在輸出的索引 0 處。
，了解反向迭代如何保留相等元素的順序，從而使排序「穩定」
排序後的陣列為 {1,1,2,3}
func CountingSort(in []int) []int {
// find the min/max values
min := slices.Min(in)
max := slices.Max(in)
// create the count array
counts := make([]int, max-min+1)
for _, v := range in {
counts[v-min]++
}
// determine cumulative counts
for i := 1; i < len(counts); i++ {
counts[i] = counts[i-1] + counts[i]
}
// create the output array
out := make([]int, len(in))
for i := range in {
v := in[len(in)-1-i]
out[counts[v-min]-1] = v
counts[v-min]--
}
return out
}
可以提高效率嗎？在下面留下您的意見和建議。
謝謝！
這篇文章以及本系列所有文章的程式碼可以在這裡找到
以上是計數排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！
