計數排序

這是用於整數數組或以整數為鍵的結構的排序演算法。當整數範圍與輸入大小相同時特別有用。

主要思想是決定整數出現的頻率，並用它來決定排序順序。

範例：假設我們得到陣列 {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中文網其他相關文章！