計數排序（Counting Sort）是一種非比較排序算法，其核心思想是通過計數每個元素的出現次數來進行排序，適用于整數或有限范圍內的非負整數排序。這個算法的特點是速度快且穩定，適用于某些特定場景。在本文中，我們將深入探討計數排序的原理、步驟以及性能分析。D6028資訊網——每日最新資訊28at.com

算法原理

計數排序的基本思想是：D6028資訊網——每日最新資訊28at.com

1. 計數：遍歷待排序的數組，統計每個元素出現的次數，并將統計結果存儲在一個計數數組中。計數數組的索引對應著元素的值，而計數數組中的值表示該元素出現的次數。
   
2. 累積計數：對計數數組進行累積計數，即將每個元素的計數值加上前一個元素的計數值，得到每個元素在排序后數組中的位置。這一步確保相同元素的相對順序不變。
   
3. 排序：創建一個與待排序數組大小相同的結果數組，然后遍歷待排序數組，根據元素的值在累積計數數組中找到其在結果數組中的位置，將元素放置在結果數組中的正確位置。
   

算法步驟

計數排序的具體步驟如下：D6028資訊網——每日最新資訊28at.com

1. 掃描待排序數組，確定數組的最大值（max）和最小值（min）。
   
2. 創建一個計數數組（count），長度為max - min + 1。
   
3. 第一次遍歷待排序數組，統計每個元素出現的次數，將結果存儲在計數數組中。
   
4. 對計數數組進行累積計數，確保計數數組中的每個元素表示小于等于該元素值的元素個數。
   
5. 創建一個與待排序數組大小相同的結果數組（result）。
   
6. 第二次遍歷待排序數組，根據元素的值在累積計數數組中找到其在結果數組中的位置，將元素放置在結果數組中的正確位置。
   
7. 將結果數組復制回原始數組，完成排序。
   

Java 實現

以下是使用Java語言實現計數排序算法的示例代碼：D6028資訊網——每日最新資訊28at.com

public class Test {    public static void main(String[] args) {        int[] arr = new int[]{5,2,3,1,6,7,1,3};        countingSort(arr);    }    public static void countingSort(int[] arr){        System.out.println("原始數組："+ Arrays.toString(arr));        //獲取排序數組的長度        int len=  arr.length;        //獲取數組最大元素        int max = Arrays.stream(arr).max().getAsInt();        //獲取數組最小元素        int min = Arrays.stream(arr).min().getAsInt();        //計算計數數組的長度        int rang = max-min+1;        //創建計數數組        int count[] = new int[rang];        //創建排序后的目標數組        int result[] = new int[len];        //計數:統計每個元素出現的次數        for(int i = 0; i < len; i++){            count[arr[i]-min]++;        }        System.out.println("計數數組："+ Arrays.toString(count));        //累計計數:計算每個元素在排序后數組中的位置        for(int j = 1 ;j < rang; j++){            count[j]+=count[j-1];        }        System.out.println("累計計數數組："+ Arrays.toString(count));        //排序：根據累計計數數組將元素放置到正確的位置        for(int k = len -1 ; k >= 0; k--){            result[count[arr[k] - min] -1] = arr[k];            count[arr[k] - min]--;        }        System.arraycopy(result, 0, arr, 0, len);        System.out.println("排序完成的數組："+ Arrays.toString(arr));    }}

運行結果為：D6028資訊網——每日最新資訊28at.com

原始數組：[5, 2, 3, 1, 6, 7, 1, 3]計數數組：[2, 1, 2, 0, 1, 1, 1]累計計數數組：[2, 3, 5, 5, 6, 7, 8]排序完成的數組：[1, 1, 2, 3, 3, 5, 6, 7]

這段代碼演示了如何使用計數排序算法對整數數組進行排序。計數排序是一種穩定的排序算法，適用于整數范圍不大的情況，它的時間復雜度為O(n + k)，其中n是待排序數組的大小，k是整數范圍(數組中最大元素與最小元素的差值)。D6028資訊網——每日最新資訊28at.com

性能分析

計數排序的性能分析如下：D6028資訊網——每日最新資訊28at.com

• 平均時間復雜度：O(n + k)，其中n是待排序數組的大小，k是整數范圍。
  
• 最壞時間復雜度：O(n + k)。
  
• 最佳時間復雜度：O(n + k)。
  
• 空間復雜度：O(n + k)，需要額外的計數數組和結果數組。
  
• 穩定性：計數排序是一種穩定的排序算法，不改變相同元素的相對順序。
  

使用場景

計數排序適用于以下情況：D6028資訊網——每日最新資訊28at.com

• 需要排序的數據是整數或有限范圍內的非負整數。
  
• 待排序數據中存在大量重復元素。
  
• 對穩定性排序有要求，即相同元素的相對順序不變。
  

總結

計數排序是一種高效的非比較排序算法，適用于整數排序和穩定性排序的場景。盡管它對整數范圍有一定要求，但在合適的情況下，計數排序能夠提供線性時間復雜度的排序性能，相對于其他復雜排序算法來說，它具有獨特的優勢。因此，在選擇排序算法時，應根據數據特點和性能需求來決定是否使用計數排序。D6028資訊網——每日最新資訊28at.com

本文鏈接：http://www.www897cc.com/showinfo-26-12136-0.html計數排序（Counting Sort）詳解

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com

上一篇： 池化技術：如何減少頻繁創建數據庫連接的性能損耗？

下一篇： GO 比較兩個對象是否相同