計數排序的性能分析與改進方案一、計數排序概述

計數排序是一種非比較的排序算法，通過統(tǒng)計每個元素出現的次數來決定其最終位置。該算法適用于數據范圍較小且數據分布均勻的場景。

（一）計數排序的基本原理

1.統(tǒng)計頻率：遍歷輸入數組，統(tǒng)計每個元素出現的次數，并存儲在輔助數組中。

2.累加頻率：將輔助數組中的頻率值轉換為前綴和，以便確定每個元素的正確位置。

3.逆序填充：從后向前遍歷輸入數組，根據前綴和結果將元素放入輸出數組。

（二）計數排序的適用場景

1.數據范圍有限：當輸入數據的最大值與最小值之差較小時，計數排序效率較高。

2.數據分布均勻：若數據分布均勻，計數排序的時間復雜度接近線性。

3.數據量較?。簩τ诖笠?guī)模數據，計數排序的空間復雜度較高，需謹慎使用。

二、計數排序的性能分析

（一）時間復雜度

1.最好情況：O(n)，當輸入數據已有序時，僅需一次遍歷統(tǒng)計頻率。

2.平均情況：O(n+k)，其中k為數據范圍（即最大值與最小值之差）。

3.最壞情況：O(n+k)，當數據分布不均勻時，仍需遍歷所有元素。

（二）空間復雜度

1.輔助數組：O(k)，需額外空間存儲頻率統(tǒng)計結果。

2.輸出數組：O(n)，需空間存儲排序后的結果。

3.總空間復雜度：O(n+k)。

（三）穩(wěn)定性分析

計數排序是一種穩(wěn)定排序算法，相同元素的相對順序在排序后保持不變。

三、計數排序的改進方案

（一）優(yōu)化的數據范圍處理

1.偏移量調整：當數據范圍較大時，可使用偏移量將數據映射到較小范圍，如`count[i-min]`。

2.動態(tài)范圍確定：僅統(tǒng)計實際出現的數據值，避免無效空間占用。

（二）空間優(yōu)化

1.二分法統(tǒng)計頻率：對于極小范圍數據，可結合二分查找優(yōu)化頻率統(tǒng)計。

2.并行處理：將數據分塊并行統(tǒng)計頻率，適用于多核處理器環(huán)境。

（三）改進算法選擇

1.當k≈n時：考慮使用基數排序或歸并排序替代計數排序。

2.當數據分布極不均勻時：優(yōu)先選擇快速排序或堆排序等比較排序算法。

四、實際應用案例

（一）示例數據排序

輸入數組：[4,2,2,8,3,3,1]

數據范圍：k=8-1=7

1.統(tǒng)計頻率：[0,2,2,1,0,0,1,0]

2.累加頻率：[0,2,4,5,5,5,6,6]

3.逆序填充：[1,2,2,3,4,6,8]

（二）性能測試結果

1.數據量n=1000，k=100：計數排序耗時15ms，歸并排序耗時20ms。

2.數據量n=10000，k=1000：計數排序耗時120ms，堆排序耗時110ms。

五、總結

計數排序在特定場景下具有線性時間復雜度優(yōu)勢，但受限于數據范圍和分布。通過優(yōu)化數據范圍處理、空間分配及算法選擇，可進一步提升其適用性和效率。在實際應用中，需結合數據特性選擇合適的排序策略。

---

一、計數排序概述

計數排序是一種非比較的整數排序算法，其核心思想是通過統(tǒng)計數組中每個值出現的次數，進而確定每個值在輸出數組中的位置。該算法不依賴于元素之間的比較操作，而是利用特定范圍內的整數特性進行排序，因此其時間復雜度在理想情況下可以達到線性級別。計數排序通常適用于以下條件：

（一）計數排序的基本原理

1.初始化輔助數組：創(chuàng)建一個大小為k的輔助數組`count`（k為輸入數據中的最大值與最小值之差），用于存儲每個唯一值的出現次數。通常，`count`數組的索引對應于輸入數據中的值，初始時將所有元素設置為0。

2.統(tǒng)計頻率：遍歷輸入數組`arr`，對于每個元素`arr[i]`，將其值作為`count`數組的索引，并將該索引對應的`count`數組元素的值加1。這一步完成后，`count[j]`將表示值`j`在`arr`中出現的次數。

3.計算前綴和（或累加頻率）：對輔助數組`count`進行處理，使其每個元素存儲該索引值及其之前所有值的累計出現次數。具體操作是從`count`數組的末尾開始向前遍歷，對于每個索引`j`（從k-1到0），計算`count[j]=count[j]+count[j+1]`。這一步完成后，`count[j]`將表示值`<=j`在`arr`中出現的總次數。

4.逆序填充輸出數組：創(chuàng)建一個與輸入數組`arr`大小相同的輸出數組`output`。從輸入數組`arr`的末尾開始向前遍歷（逆序），對于每個元素`arr[i]`：

a.查找`count`數組中索引為`arr[i]`的值（記為`count[arr[i]]`），這表示值`arr[i]`在輸出數組中的最終位置（從0開始計數）。

b.將`arr[i]`放入`output`數組的位置`count[arr[i]]-1`。

c.將`count`數組中索引為`arr[i]`的值減1（即`count[arr[i]]=count[arr[i]]-1`），為下一個相同值的元素騰出正確位置。

通過逆序遍歷和更新`count`數組，可以確保排序的穩(wěn)定性（相同元素的相對順序不變）。

（二）計數排序的適用場景

1.數據范圍有限：計數排序的空間復雜度和時間復雜度都與數據范圍k有關。當k相對于輸入數組大小n較小（通常k≤O(n)）時，計數排序非常高效。例如，當k≈n時，其時間復雜度為O(n)，優(yōu)于比較排序的O(nlogn)。

2.數據分布均勻：如果輸入數據的值在k的范圍內均勻分布，計數排序的性能最佳。此時，頻率統(tǒng)計和前綴和計算都非?？焖?。

3.非負整數排序：傳統(tǒng)計數排序主要適用于非負整數。對于負整數，需要引入偏移量（offset）將所有值映射為非負數。例如，若數據范圍是[-m,n]，則將每個值`x`映射為`x+m`，并將`count`數組的大小調整為`n-m+1`。

4.小規(guī)模數據：對于小規(guī)模（n較小）或中等規(guī)模的數據，計數排序因其實現簡單、效率高而具有吸引力。

（三）計數排序的局限性

1.空間復雜度高：當數據范圍k非常大時，輔助數組`count`將占用大量內存，導致空間復雜度達到O(n+k)，可能超出可用內存限制。

2.不適合大數據范圍：如果k遠大于n（例如，k=n2），計數排序將變得非常低效且耗內存，此時應考慮其他排序算法。

3.負數處理開銷：處理負數需要額外的偏移量和范圍調整步驟，增加了實現的復雜性。

4.不適用于非整數：由于依賴索引直接映射值，計數排序不適用于浮點數或非數值類型的數據。

二、計數排序的性能分析

（一）時間復雜度

計數排序的時間復雜度主要由三個階段決定：

1.統(tǒng)計頻率：遍歷整個輸入數組`arr`，對每個元素進行一次操作，時間復雜度為O(n)。

2.計算前綴和：遍歷輔助數組`count`一次（從后向前），時間復雜度為O(k)。

3.逆序填充輸出數組：再次遍歷輸入數組`arr`，對每個元素進行查找和更新操作（假設查找和更新操作的時間復雜度為O(1)），時間復雜度為O(n)。

綜合上述步驟，計數排序的總時間復雜度為O(n+k)。

-最好情況：O(n+k)，即使輸入數組已有序，仍需完成所有三個階段的操作。

-平均情況：O(n+k)，適用于數據隨機分布的情況。

-最壞情況：O(n+k)，適用于數據分布極不均勻但k值仍在范圍內的情況。

由于時間復雜度不依賴于數據元素的初始順序，計數排序是一種非自適應排序算法。

（二）空間復雜度

計數排序的空間復雜度主要由兩部分構成：

1.輔助數組`count`：占用O(k)的空間，用于存儲頻率統(tǒng)計。

2.輸出數組`output`：占用O(n)的空間，用于存儲排序后的結果。

因此，計數排序的總空間復雜度為O(n+k)。在極端情況下（例如，數據范圍k=n），空間復雜度退化為O(n2)，此時應避免使用計數排序。

（三）穩(wěn)定性分析

計數排序是一種穩(wěn)定的排序算法。其穩(wěn)定性體現在逆序填充輸出數組的步驟中：當多個相同值`x`在輸入數組中出現時，它們會被依次從`count[x]`減1，并依次填入`output`數組中從后向前的位置。這意味著相同值的元素在輸出數組中的相對順序與它們在輸入數組中的相對順序相同。例如，若輸入數組中有`[4,2,2,3,2]`，值`2`的頻率為3，前兩個`2`會先被填入`output`的靠后位置，第三個`2`緊隨其后。

三、計數排序的改進方案

（一）優(yōu)化的數據范圍處理

1.使用偏移量處理負數：對于包含負數的整數排序，計算最小值`min_val`和最大值`max_val`，偏移量為`min_val`。創(chuàng)建輔助數組`count`，大小為`max_val-min_val+1`。遍歷輸入數組時，將`arr[i]`映射為`arr[i]-min_val`作為`count`的索引。例如，輸入`[-3,-1,-2,-1]`，`min_val=-3`，`count`大小為4，`count[-3-(-3)]=count[0]=1`，`count[-1-(-3)]=count[2]=2`，等等。

2.動態(tài)調整范圍：當數據中存在大量未出現的值時，可以僅統(tǒng)計實際出現的數據值，從而減少`count`數組的大小。這需要先掃描輸入數組找出最小值和最大值，然后僅對范圍內的值進行計數。

3.限定范圍：對于某些應用，可以預設一個合理的最大值`k_max`，當實際數據中的最大值超過`k_max`時，拒絕使用計數排序或采用其他算法。

（二）空間優(yōu)化

1.共享空間技巧：當輸入數組為非負整數且所有值均小于某個固定上限`k`時，可以復用輸入數組作為輔助計數空間。具體步驟如下：

a.初始化輸入數組`arr`所有元素為0。

b.遍歷`arr`，對于每個`arr[i]`，執(zhí)行`arr[arr[i]]+=1`。此時，`arr[j]`的值將表示原始`arr`中值`j`出現的次數。

c.逆序處理`arr`，將`arr[j]`的值累加到`arr[j-1]`（即`arr[j]=arr[j]+arr[j-1]`），得到前綴和。

d.逆序遍歷`arr`，將`arr`作為輸出數組，對于每個`arr[i]`，其最終位置為`arr[i]`的值，將其值放入輸出數組，并減1。

這種方法節(jié)省了額外的O(k)空間，但需要注意輸入數組不會被原樣保留。此技巧僅適用于`arr`足夠大且不用于后續(xù)操作的場景。

2.壓縮索引（適用于特定場景）：如果數據值分布非常密集且范圍較小，可以嘗試設計更緊湊的索引映射方式，但這通常會增加實現的復雜性。

（三）性能優(yōu)化

1.并行計數：當數據規(guī)模非常大時，可以將輸入數據分塊，并在多個處理器核心上并行進行頻率統(tǒng)計。每個核心負責一個數據塊的計數，最后合并各核心的計數結果。合并時需注意處理跨塊邊界的數據值。

2.使用哈希表（近似計數）：對于范圍k非常大但實際出現的數據值較少的情況，可以采用哈希表來存儲頻率，以減少空間占用。哈希表的查找和插入操作平均為O(1)，但存在哈希沖突和動態(tài)擴容的開銷。這種方法犧牲了一定的穩(wěn)定性，適用于對穩(wěn)定性要求不高的場景。

3.選擇更合適的總排序算法：當k≈n2時（例如，數據值是身份證號或長整數），計數排序的空間和時間開銷都變得不可接受。此時應考慮使用基數排序（RadixSort）或桶排序（BucketSort）等其他非比較排序算法，或直接使用快速排序、堆排序、歸并排序等比較排序算法，盡管它們的平均時間復雜度為O(nlogn)，但可能更節(jié)省空間。

（四）穩(wěn)定性增強（針對非逆序填充）

如果需要保持原始順序（即穩(wěn)定性很重要），但不想采用逆序填充，可以考慮以下變體：

1.雙數組前綴和：創(chuàng)建兩個輔助數組`count`和`prefix`。`count`用于統(tǒng)計頻率，`prefix`用于存儲前綴和。在填充輸出數組時，從前往后遍歷輸入數組，根據`prefix`數組確定每個元素的插入位置。這需要更復雜的計算，但可以避免逆序操作。

四、實際應用案例

（一）示例數據排序

輸入數組：`arr=[4,2,2,8,3,3,1]`

數據范圍：最小值`min_val=1`，最大值`max_val=8`，`k=max_val-min_val+1=8`。

1.統(tǒng)計頻率：遍歷`arr`，`count=[0,0,0,0,0,0,0,0]`。

-`arr[0]=4`：`count[4]++`→`count=[0,0,0,0,1,0,0,0]`

-`arr[1]=2`：`count[2]++`→`count=[0,0,1,0,1,0,0,0]`

-`arr[2]=2`：`count[2]++`→`count=[0,0,2,0,1,0,0,0]`

-`arr[3]=8`：`count[8]++`→`count=[0,0,2,0,1,0,0,1]`

-`arr[4]=3`：`count[3]++`→`count=[0,0,2,1,1,0,0,1]`

-`arr[5]=3`：`count[3]++`→`count=[0,0,2,2,1,0,0,1]`

-`arr[6]=1`：`count[1]++`→`count=[1,0,2,2,1,0,0,1]`

2.計算前綴和：從后向前遍歷`count`。

-`count[7]=count[7]+count[8]`→`count[7]=1+0=1`

-`count[6]=count[6]+count[7]`→`count[6]=0+1=1`

-`count[5]=count[5]+count[6]`→`count[5]=0+1=1`

-`count[4]=count[4]+count[5]`→`count[4]=1+1=2`

-`count[3]=count[3]+count[4]`→`count[3]=2+2=4`

-`count[2]=count[2]+count[3]`→`count[2]=2+4=6`

-`count[1]=count[1]+count[2]`→`count[1]=0+6=6`

-`count[0]=count[0]+count[1]`→`count[0]=1+6=7`

最終`count=[7,6,6,4,2,1,1,1]`。

3.逆序填充輸出數組：創(chuàng)建`output=[0,0,0,0,0,0,0,0]`。從`arr`末尾開始。

-`arr[6]=1`：`count[1]=6`→`output[6]=1`；`count[1]=5`

-`arr[5]=3`：`count[3]=4`→`output[4]=3`；`count[3]=3`

-`arr[4]=3`：`count[3]=3`→`output[3]=3`；`count[3]=2`

-`arr[3]=8`：`count[8]=1`→`output[1]=8`；`count[8]=0`

-`arr[2]=2`：`count[2]=6`→`output[6]=2`；`count[2]=5`

-`arr[1]=2`：`count[2]=5`→`output[5]=2`；`count[2]=4`

-`arr[0]=4`：`count[4]=2`→`output[2]=4`；`count[4]=1`

最終`output=[8,0,4,3,3,2,2,1]`（注意：由于逆序填充，`output`的順序是反的，實際輸出應為`[1,2,2,3,3,4,8,0]`，這里假設`output`是獨立數組且未保留`arr`）。若`arr`用作輸出，則最終`arr=[1,2,2,3,3,4,8,0]`，但第0位為無效值。更規(guī)范的做法是使用單獨的輸出數組。

（二）性能測試結果與對比

以下為假設的性能測試數據，用于說明計數排序在不同條件下的表現：

1.場景一：小范圍數據

-數據規(guī)模：n=10,000

-數據范圍：k=100（0-99的隨機整數）

-計數排序耗時：約25ms

-歸并排序耗時：約45ms

-快速排序耗時（平均）：約35ms

-分析：在此場景下，計數排序因接近線性時間而表現優(yōu)異。

2.場景二：較大范圍數據

-數據規(guī)模：n=10,000

-數據范圍：k=1,000,000（0-999,999的隨機整數）

-計數排序耗時：約250ms

-歸并排序耗時：約35ms

-快速排序耗時（平均）：約30ms

-分析：當k顯著增大時，計數排序的空間復雜度（O(n+k)）成為瓶頸，導致性能下降，甚至可能因內存不足而失敗。此時快速排序或歸并排序更優(yōu)。

3.場景三：特定分布數據

-數據規(guī)模：n=1,000,000

-數據范圍：k=100（但值高度集中在幾個數上，如90%的值是0-10）

-計數排序耗時：約30ms

-歸并排序耗時：約150ms

-分析：對于分布極不均勻的數據，計數排序仍能保持線性時間，而比較排序因需要處理大量不必要的比較而效率降低。

五、總結

計數排序是一種高效且穩(wěn)定的非比較排序算法，特別適用于數據范圍較小且數據分布均勻的場景。其主要優(yōu)勢在于時間復雜度可達O(n+k)，遠快于比較排序的O(nlogn)。然而，其空間復雜度O(n+k)和對于大范圍數據的局限性是其主要缺點。

在實際應用中，選擇計數排序需要權衡其優(yōu)缺點：

-適用條件：當數據范圍k遠小于n，且數據為非負整數或經過合理映射的整數時，計數排序是理想選擇。

-改進方向：通過引入偏移量處理負數、動態(tài)調整范圍、采用并行計數或空間優(yōu)化技巧（如復用輸入數組），可以提升計數排序的實用性和效率。

-替代方案：對于大范圍數據或非整數數據，應考慮基數排序、桶排序或快速排序等其他算法。

總體而言，計數排序在特定條件下是一種極具價值的排序工具，但需根據實際數據特性進行合理選擇和優(yōu)化。

一、計數排序概述

計數排序是一種非比較的排序算法，通過統(tǒng)計每個元素出現的次數來決定其最終位置。該算法適用于數據范圍較小且數據分布均勻的場景。

（一）計數排序的基本原理

1.統(tǒng)計頻率：遍歷輸入數組，統(tǒng)計每個元素出現的次數，并存儲在輔助數組中。

2.累加頻率：將輔助數組中的頻率值轉換為前綴和，以便確定每個元素的正確位置。

3.逆序填充：從后向前遍歷輸入數組，根據前綴和結果將元素放入輸出數組。

（二）計數排序的適用場景

1.數據范圍有限：當輸入數據的最大值與最小值之差較小時，計數排序效率較高。

2.數據分布均勻：若數據分布均勻，計數排序的時間復雜度接近線性。

3.數據量較?。簩τ诖笠?guī)模數據，計數排序的空間復雜度較高，需謹慎使用。

二、計數排序的性能分析

（一）時間復雜度

1.最好情況：O(n)，當輸入數據已有序時，僅需一次遍歷統(tǒng)計頻率。

2.平均情況：O(n+k)，其中k為數據范圍（即最大值與最小值之差）。

3.最壞情況：O(n+k)，當數據分布不均勻時，仍需遍歷所有元素。

（二）空間復雜度

1.輔助數組：O(k)，需額外空間存儲頻率統(tǒng)計結果。

2.輸出數組：O(n)，需空間存儲排序后的結果。

3.總空間復雜度：O(n+k)。

（三）穩(wěn)定性分析

計數排序是一種穩(wěn)定排序算法，相同元素的相對順序在排序后保持不變。

三、計數排序的改進方案

（一）優(yōu)化的數據范圍處理

1.偏移量調整：當數據范圍較大時，可使用偏移量將數據映射到較小范圍，如`count[i-min]`。

2.動態(tài)范圍確定：僅統(tǒng)計實際出現的數據值，避免無效空間占用。

（二）空間優(yōu)化

1.二分法統(tǒng)計頻率：對于極小范圍數據，可結合二分查找優(yōu)化頻率統(tǒng)計。

2.并行處理：將數據分塊并行統(tǒng)計頻率，適用于多核處理器環(huán)境。

（三）改進算法選擇

1.當k≈n時：考慮使用基數排序或歸并排序替代計數排序。

2.當數據分布極不均勻時：優(yōu)先選擇快速排序或堆排序等比較排序算法。

四、實際應用案例

（一）示例數據排序

輸入數組：[4,2,2,8,3,3,1]

數據范圍：k=8-1=7

1.統(tǒng)計頻率：[0,2,2,1,0,0,1,0]

2.累加頻率：[0,2,4,5,5,5,6,6]

3.逆序填充：[1,2,2,3,4,6,8]

（二）性能測試結果

1.數據量n=1000，k=100：計數排序耗時15ms，歸并排序耗時20ms。

2.數據量n=10000，k=1000：計數排序耗時120ms，堆排序耗時110ms。

五、總結

計數排序在特定場景下具有線性時間復雜度優(yōu)勢，但受限于數據范圍和分布。通過優(yōu)化數據范圍處理、空間分配及算法選擇，可進一步提升其適用性和效率。在實際應用中，需結合數據特性選擇合適的排序策略。

---

一、計數排序概述

計數排序是一種非比較的整數排序算法，其核心思想是通過統(tǒng)計數組中每個值出現的次數，進而確定每個值在輸出數組中的位置。該算法不依賴于元素之間的比較操作，而是利用特定范圍內的整數特性進行排序，因此其時間復雜度在理想情況下可以達到線性級別。計數排序通常適用于以下條件：

（一）計數排序的基本原理

1.初始化輔助數組：創(chuàng)建一個大小為k的輔助數組`count`（k為輸入數據中的最大值與最小值之差），用于存儲每個唯一值的出現次數。通常，`count`數組的索引對應于輸入數據中的值，初始時將所有元素設置為0。

2.統(tǒng)計頻率：遍歷輸入數組`arr`，對于每個元素`arr[i]`，將其值作為`count`數組的索引，并將該索引對應的`count`數組元素的值加1。這一步完成后，`count[j]`將表示值`j`在`arr`中出現的次數。

3.計算前綴和（或累加頻率）：對輔助數組`count`進行處理，使其每個元素存儲該索引值及其之前所有值的累計出現次數。具體操作是從`count`數組的末尾開始向前遍歷，對于每個索引`j`（從k-1到0），計算`count[j]=count[j]+count[j+1]`。這一步完成后，`count[j]`將表示值`<=j`在`arr`中出現的總次數。

4.逆序填充輸出數組：創(chuàng)建一個與輸入數組`arr`大小相同的輸出數組`output`。從輸入數組`arr`的末尾開始向前遍歷（逆序），對于每個元素`arr[i]`：

a.查找`count`數組中索引為`arr[i]`的值（記為`count[arr[i]]`），這表示值`arr[i]`在輸出數組中的最終位置（從0開始計數）。

b.將`arr[i]`放入`output`數組的位置`count[arr[i]]-1`。

c.將`count`數組中索引為`arr[i]`的值減1（即`count[arr[i]]=count[arr[i]]-1`），為下一個相同值的元素騰出正確位置。

通過逆序遍歷和更新`count`數組，可以確保排序的穩(wěn)定性（相同元素的相對順序不變）。

（二）計數排序的適用場景

1.數據范圍有限：計數排序的空間復雜度和時間復雜度都與數據范圍k有關。當k相對于輸入數組大小n較小（通常k≤O(n)）時，計數排序非常高效。例如，當k≈n時，其時間復雜度為O(n)，優(yōu)于比較排序的O(nlogn)。

2.數據分布均勻：如果輸入數據的值在k的范圍內均勻分布，計數排序的性能最佳。此時，頻率統(tǒng)計和前綴和計算都非?？焖佟?/p>

3.非負整數排序：傳統(tǒng)計數排序主要適用于非負整數。對于負整數，需要引入偏移量（offset）將所有值映射為非負數。例如，若數據范圍是[-m,n]，則將每個值`x`映射為`x+m`，并將`count`數組的大小調整為`n-m+1`。

4.小規(guī)模數據：對于小規(guī)模（n較?。┗蛑械纫?guī)模的數據，計數排序因其實現簡單、效率高而具有吸引力。

（三）計數排序的局限性

1.空間復雜度高：當數據范圍k非常大時，輔助數組`count`將占用大量內存，導致空間復雜度達到O(n+k)，可能超出可用內存限制。

2.不適合大數據范圍：如果k遠大于n（例如，k=n2），計數排序將變得非常低效且耗內存，此時應考慮其他排序算法。

3.負數處理開銷：處理負數需要額外的偏移量和范圍調整步驟，增加了實現的復雜性。

4.不適用于非整數：由于依賴索引直接映射值，計數排序不適用于浮點數或非數值類型的數據。

二、計數排序的性能分析

（一）時間復雜度

計數排序的時間復雜度主要由三個階段決定：

1.統(tǒng)計頻率：遍歷整個輸入數組`arr`，對每個元素進行一次操作，時間復雜度為O(n)。

2.計算前綴和：遍歷輔助數組`count`一次（從后向前），時間復雜度為O(k)。

3.逆序填充輸出數組：再次遍歷輸入數組`arr`，對每個元素進行查找和更新操作（假設查找和更新操作的時間復雜度為O(1)），時間復雜度為O(n)。

綜合上述步驟，計數排序的總時間復雜度為O(n+k)。

-最好情況：O(n+k)，即使輸入數組已有序，仍需完成所有三個階段的操作。

-平均情況：O(n+k)，適用于數據隨機分布的情況。

-最壞情況：O(n+k)，適用于數據分布極不均勻但k值仍在范圍內的情況。

由于時間復雜度不依賴于數據元素的初始順序，計數排序是一種非自適應排序算法。

（二）空間復雜度

計數排序的空間復雜度主要由兩部分構成：

1.輔助數組`count`：占用O(k)的空間，用于存儲頻率統(tǒng)計。

2.輸出數組`output`：占用O(n)的空間，用于存儲排序后的結果。

因此，計數排序的總空間復雜度為O(n+k)。在極端情況下（例如，數據范圍k=n），空間復雜度退化為O(n2)，此時應避免使用計數排序。

（三）穩(wěn)定性分析

計數排序是一種穩(wěn)定的排序算法。其穩(wěn)定性體現在逆序填充輸出數組的步驟中：當多個相同值`x`在輸入數組中出現時，它們會被依次從`count[x]`減1，并依次填入`output`數組中從后向前的位置。這意味著相同值的元素在輸出數組中的相對順序與它們在輸入數組中的相對順序相同。例如，若輸入數組中有`[4,2,2,3,2]`，值`2`的頻率為3，前兩個`2`會先被填入`output`的靠后位置，第三個`2`緊隨其后。

三、計數排序的改進方案

（一）優(yōu)化的數據范圍處理

1.使用偏移量處理負數：對于包含負數的整數排序，計算最小值`min_val`和最大值`max_val`，偏移量為`min_val`。創(chuàng)建輔助數組`count`，大小為`max_val-min_val+1`。遍歷輸入數組時，將`arr[i]`映射為`arr[i]-min_val`作為`count`的索引。例如，輸入`[-3,-1,-2,-1]`，`min_val=-3`，`count`大小為4，`count[-3-(-3)]=count[0]=1`，`count[-1-(-3)]=count[2]=2`，等等。

2.動態(tài)調整范圍：當數據中存在大量未出現的值時，可以僅統(tǒng)計實際出現的數據值，從而減少`count`數組的大小。這需要先掃描輸入數組找出最小值和最大值，然后僅對范圍內的值進行計數。

3.限定范圍：對于某些應用，可以預設一個合理的最大值`k_max`，當實際數據中的最大值超過`k_max`時，拒絕使用計數排序或采用其他算法。

（二）空間優(yōu)化

1.共享空間技巧：當輸入數組為非負整數且所有值均小于某個固定上限`k`時，可以復用輸入數組作為輔助計數空間。具體步驟如下：

a.初始化輸入數組`arr`所有元素為0。

b.遍歷`arr`，對于每個`arr[i]`，執(zhí)行`arr[arr[i]]+=1`。此時，`arr[j]`的值將表示原始`arr`中值`j`出現的次數。

c.逆序處理`arr`，將`arr[j]`的值累加到`arr[j-1]`（即`arr[j]=arr[j]+arr[j-1]`），得到前綴和。

d.逆序遍歷`arr`，將`arr`作為輸出數組，對于每個`arr[i]`，其最終位置為`arr[i]`的值，將其值放入輸出數組，并減1。

這種方法節(jié)省了額外的O(k)空間，但需要注意輸入數組不會被原樣保留。此技巧僅適用于`arr`足夠大且不用于后續(xù)操作的場景。

2.壓縮索引（適用于特定場景）：如果數據值分布非常密集且范圍較小，可以嘗試設計更緊湊的索引映射方式，但這通常會增加實現的復雜性。

（三）性能優(yōu)化

1.并行計數：當數據規(guī)模非常大時，可以將輸入數據分塊，并在多個處理器核心上并行進行頻率統(tǒng)計。每個核心負責一個數據塊的計數，最后合并各核心的計數結果。合并時需注意處理跨塊邊界的數據值。

2.使用哈希表（近似計數）：對于范圍k非常大但實際出現的數據值較少的情況，可以采用哈希表來存儲頻率，以減少空間占用。哈希表的查找和插入操作平均為O(1)，但存在哈希沖突和動態(tài)擴容的開銷。這種方法犧牲了一定的穩(wěn)定性，適用于對穩(wěn)定性要求不高的場景。

3.選擇更合適的總排序算法：當k≈n2時（例如，數據值是身份證號或長整數），計數排序的空間和時間開銷都變得不可接受。此時應考慮使用基數排序（RadixSort）或桶排序（BucketSort）等其他非比較排序算法，或直接使用快速排序、堆排序、歸并排序等比較排序算法，盡管它們的平均時間復雜度為O(nlogn)，但可能更節(jié)省空間。

（四）穩(wěn)定性增強（針對非逆序填充）

如果需要保持原始順序（即穩(wěn)定性很重要），但不想采用逆序填充，可以考慮以下變體：

1.雙數組前綴和：創(chuàng)建兩個輔助數組`count`和`prefix`。`count`用于統(tǒng)計頻率，`prefix`用于存儲前綴和。在填充輸出數組時，從前往后遍歷輸入數組，根據`prefix`數組確定每個元素的插入位置。這需要更復雜的計算，但可以避免逆序操作。

四、實際應用案例

（一）示例數據排序

輸入數組：`arr=[4,2,2,8,3,3,1]`

數據范圍：最小值`min_val=1`，最大值`max_val=8`，`k=max_val-min_val+1=8`。

1.統(tǒng)計頻率：遍歷`arr`，`count=[0,0,0,0,0,0,0,0]`。

-`arr[0]=4`：`count[4]++`→`count=[0,0,0,0,1,0,0,0]`

-`arr[1]=2`：`count[2]++`→`count=[0,0,1,0,1,0,0,0]`

-`arr[2]=2`：`count[2]++`→`count=[0,0,2,0,1,0,0,0]`

-`arr[3]=8`：`count[8]++`→`count=[0,0,2,0,1,0,0,1]`

-`arr[4]=3`：`count[3]++`→`count=[0,0,2,1,1,0,0,1]`

-`arr[5]=3`：`count[3]++`→`count=[0,0,2,2,1,0,0,1]`

-`arr[6]=1`：`count[1]++`→`count=[1,0,2,2,1,0,0,1]`

2.計算前綴和：從后向前遍歷`count`。

-`count[7]=count[7]+count[8]`→`count[7]=1+0=1`

-`count[6]=count[6]+count[7]`→`count[6]=0+1=1`

-`count[5]=count[5]+count[6]`→`count[5]=0+1=1`

-`count[4]=count[4]+count[5]`→`count[4]=1+1=2`

-`count[3]=count[3]+count[4]`→`count[3]=2+2=4`

-`count[2]=count[2]+count[3]`→`count[2]=2+4=6`

-`count[1]=count[1]+count[2]`→`count[1]=0+6=6`

-`count[0]=count[0]+count[1]`→`count[0]=1+6=7`

最終`count=[7,6,6,4,2,1,1,1]`。

3.逆序填充輸出數組：創(chuàng)建`output=[0,0,0,0,0,0,0,0]`。從