計(jì)數(shù)排序（Counting Sort）是一種非比較排序算法，其核心思想是通過(guò)計(jì)數(shù)每個(gè)元素的出現(xiàn)次數(shù)來(lái)進(jìn)行排序，適用于整數(shù)或有限范圍內(nèi)的非負(fù)整數(shù)排序。這個(gè)算法的特點(diǎn)是速度快且穩(wěn)定，適用于某些特定場(chǎng)景。在本文中，我們將深入探討計(jì)數(shù)排序的原理、步驟以及性能分析。nAX28資訊網(wǎng)——每日最新資訊28at.com

算法原理

計(jì)數(shù)排序的基本思想是：nAX28資訊網(wǎng)——每日最新資訊28at.com

1. 計(jì)數(shù)：遍歷待排序的數(shù)組，統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)，并將統(tǒng)計(jì)結(jié)果存儲(chǔ)在一個(gè)計(jì)數(shù)數(shù)組中。計(jì)數(shù)數(shù)組的索引對(duì)應(yīng)著元素的值，而計(jì)數(shù)數(shù)組中的值表示該元素出現(xiàn)的次數(shù)。
   
2. 累積計(jì)數(shù)：對(duì)計(jì)數(shù)數(shù)組進(jìn)行累積計(jì)數(shù)，即將每個(gè)元素的計(jì)數(shù)值加上前一個(gè)元素的計(jì)數(shù)值，得到每個(gè)元素在排序后數(shù)組中的位置。這一步確保相同元素的相對(duì)順序不變。
   
3. 排序：創(chuàng)建一個(gè)與待排序數(shù)組大小相同的結(jié)果數(shù)組，然后遍歷待排序數(shù)組，根據(jù)元素的值在累積計(jì)數(shù)數(shù)組中找到其在結(jié)果數(shù)組中的位置，將元素放置在結(jié)果數(shù)組中的正確位置。
   

算法步驟

計(jì)數(shù)排序的具體步驟如下：nAX28資訊網(wǎng)——每日最新資訊28at.com

1. 掃描待排序數(shù)組，確定數(shù)組的最大值（max）和最小值（min）。
   
2. 創(chuàng)建一個(gè)計(jì)數(shù)數(shù)組（count），長(zhǎng)度為max - min + 1。
   
3. 第一次遍歷待排序數(shù)組，統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)，將結(jié)果存儲(chǔ)在計(jì)數(shù)數(shù)組中。
   
4. 對(duì)計(jì)數(shù)數(shù)組進(jìn)行累積計(jì)數(shù)，確保計(jì)數(shù)數(shù)組中的每個(gè)元素表示小于等于該元素值的元素個(gè)數(shù)。
   
5. 創(chuàng)建一個(gè)與待排序數(shù)組大小相同的結(jié)果數(shù)組（result）。
   
6. 第二次遍歷待排序數(shù)組，根據(jù)元素的值在累積計(jì)數(shù)數(shù)組中找到其在結(jié)果數(shù)組中的位置，將元素放置在結(jié)果數(shù)組中的正確位置。
   
7. 將結(jié)果數(shù)組復(fù)制回原始數(shù)組，完成排序。
   

Java 實(shí)現(xiàn)

以下是使用Java語(yǔ)言實(shí)現(xiàn)計(jì)數(shù)排序算法的示例代碼：nAX28資訊網(wǎng)——每日最新資訊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("原始數(shù)組："+ Arrays.toString(arr));        //獲取排序數(shù)組的長(zhǎng)度        int len=  arr.length;        //獲取數(shù)組最大元素        int max = Arrays.stream(arr).max().getAsInt();        //獲取數(shù)組最小元素        int min = Arrays.stream(arr).min().getAsInt();        //計(jì)算計(jì)數(shù)數(shù)組的長(zhǎng)度        int rang = max-min+1;        //創(chuàng)建計(jì)數(shù)數(shù)組        int count[] = new int[rang];        //創(chuàng)建排序后的目標(biāo)數(shù)組        int result[] = new int[len];        //計(jì)數(shù):統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)        for(int i = 0; i < len; i++){            count[arr[i]-min]++;        }        System.out.println("計(jì)數(shù)數(shù)組："+ Arrays.toString(count));        //累計(jì)計(jì)數(shù):計(jì)算每個(gè)元素在排序后數(shù)組中的位置        for(int j = 1 ;j < rang; j++){            count[j]+=count[j-1];        }        System.out.println("累計(jì)計(jì)數(shù)數(shù)組："+ Arrays.toString(count));        //排序：根據(jù)累計(jì)計(jì)數(shù)數(shù)組將元素放置到正確的位置        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("排序完成的數(shù)組："+ Arrays.toString(arr));    }}

運(yùn)行結(jié)果為：nAX28資訊網(wǎng)——每日最新資訊28at.com

原始數(shù)組：[5, 2, 3, 1, 6, 7, 1, 3]計(jì)數(shù)數(shù)組：[2, 1, 2, 0, 1, 1, 1]累計(jì)計(jì)數(shù)數(shù)組：[2, 3, 5, 5, 6, 7, 8]排序完成的數(shù)組：[1, 1, 2, 3, 3, 5, 6, 7]

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

性能分析

計(jì)數(shù)排序的性能分析如下：nAX28資訊網(wǎng)——每日最新資訊28at.com

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

使用場(chǎng)景

計(jì)數(shù)排序適用于以下情況：nAX28資訊網(wǎng)——每日最新資訊28at.com

• 需要排序的數(shù)據(jù)是整數(shù)或有限范圍內(nèi)的非負(fù)整數(shù)。
  
• 待排序數(shù)據(jù)中存在大量重復(fù)元素。
  
• 對(duì)穩(wěn)定性排序有要求，即相同元素的相對(duì)順序不變。
  

總結(jié)

計(jì)數(shù)排序是一種高效的非比較排序算法，適用于整數(shù)排序和穩(wěn)定性排序的場(chǎng)景。盡管它對(duì)整數(shù)范圍有一定要求，但在合適的情況下，計(jì)數(shù)排序能夠提供線性時(shí)間復(fù)雜度的排序性能，相對(duì)于其他復(fù)雜排序算法來(lái)說(shuō)，它具有獨(dú)特的優(yōu)勢(shì)。因此，在選擇排序算法時(shí)，應(yīng)根據(jù)數(shù)據(jù)特點(diǎn)和性能需求來(lái)決定是否使用計(jì)數(shù)排序。nAX28資訊網(wǎng)——每日最新資訊28at.com

本文鏈接：http://www.tebozhan.com/showinfo-26-12136-0.html計(jì)數(shù)排序（Counting Sort）詳解

聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com

上一篇： 池化技術(shù)：如何減少頻繁創(chuàng)建數(shù)據(jù)庫(kù)連接的性能損耗？

下一篇： GO 比較兩個(gè)對(duì)象是否相同