建站
咨詢
售后
建站咨詢
新聞中心
計數(shù)排序（Counting Sort）是一種非比較排序算法，其核心思想是通過計數(shù)每個元素的出現(xiàn)次數(shù)來進行排序，適用于整數(shù)或有限范圍內(nèi)的非負(fù)整數(shù)排序。這個算法的特點是速度快且穩(wěn)定，適用于某些特定場景。在本文中，我們將深入探討計數(shù)排序的原理、步驟以及性能分析。
十載的平橋網(wǎng)站建設(shè)經(jīng)驗，針對設(shè)計、前端、開發(fā)、售后、文案、推廣等六對一服務(wù)，響應(yīng)快，48小時及時工作處理。成都全網(wǎng)營銷的優(yōu)勢是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動調(diào)整平橋建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計，從而大程度地提升瀏覽體驗。創(chuàng)新互聯(lián)公司從事“平橋網(wǎng)站設(shè)計”,“平橋網(wǎng)站推廣”以來，每個客戶項目都認(rèn)真落實執(zhí)行。
算法原理
計數(shù)排序的基本思想是：
- 計數(shù)：遍歷待排序的數(shù)組，統(tǒng)計每個元素出現(xiàn)的次數(shù)，并將統(tǒng)計結(jié)果存儲在一個計數(shù)數(shù)組中。計數(shù)數(shù)組的索引對應(yīng)著元素的值，而計數(shù)數(shù)組中的值表示該元素出現(xiàn)的次數(shù)。
- 累積計數(shù)：對計數(shù)數(shù)組進行累積計數(shù)，即將每個元素的計數(shù)值加上前一個元素的計數(shù)值，得到每個元素在排序后數(shù)組中的位置。這一步確保相同元素的相對順序不變。
- 排序：創(chuàng)建一個與待排序數(shù)組大小相同的結(jié)果數(shù)組，然后遍歷待排序數(shù)組，根據(jù)元素的值在累積計數(shù)數(shù)組中找到其在結(jié)果數(shù)組中的位置，將元素放置在結(jié)果數(shù)組中的正確位置。
算法步驟
計數(shù)排序的具體步驟如下：
- 掃描待排序數(shù)組，確定數(shù)組的最大值（max）和最小值（min）。
- 創(chuàng)建一個計數(shù)數(shù)組（count），長度為max - min + 1。
- 第一次遍歷待排序數(shù)組，統(tǒng)計每個元素出現(xiàn)的次數(shù)，將結(jié)果存儲在計數(shù)數(shù)組中。
- 對計數(shù)數(shù)組進行累積計數(shù)，確保計數(shù)數(shù)組中的每個元素表示小于等于該元素值的元素個數(shù)。
- 創(chuàng)建一個與待排序數(shù)組大小相同的結(jié)果數(shù)組（result）。
- 第二次遍歷待排序數(shù)組，根據(jù)元素的值在累積計數(shù)數(shù)組中找到其在結(jié)果數(shù)組中的位置，將元素放置在結(jié)果數(shù)組中的正確位置。
- 將結(jié)果數(shù)組復(fù)制回原始數(shù)組，完成排序。
Java 實現(xiàn)
以下是使用Java語言實現(xiàn)計數(shù)排序算法的示例代碼：
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ù)組的長度
int len= arr.length;
//獲取數(shù)組最大元素
int max = Arrays.stream(arr).max().getAsInt();
//獲取數(shù)組最小元素
int min = Arrays.stream(arr).min().getAsInt();
//計算計數(shù)數(shù)組的長度
int rang = max-min+1;
//創(chuàng)建計數(shù)數(shù)組
int count[] = new int[rang];
//創(chuàng)建排序后的目標(biāo)數(shù)組
int result[] = new int[len];
//計數(shù):統(tǒng)計每個元素出現(xiàn)的次數(shù)
for(int i = 0; i < len; i++){
count[arr[i]-min]++;
}
System.out.println("計數(shù)數(shù)組："+ Arrays.toString(count));
//累計計數(shù):計算每個元素在排序后數(shù)組中的位置
for(int j = 1 ;j < rang; j++){
count[j]+=count[j-1];
}
System.out.println("累計計數(shù)數(shù)組："+ Arrays.toString(count));
//排序：根據(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));
}
}運行結(jié)果為：
原始數(shù)組：[5, 2, 3, 1, 6, 7, 1, 3]
計數(shù)數(shù)組：[2, 1, 2, 0, 1, 1, 1]
累計計數(shù)數(shù)組：[2, 3, 5, 5, 6, 7, 8]
排序完成的數(shù)組：[1, 1, 2, 3, 3, 5, 6, 7]這段代碼演示了如何使用計數(shù)排序算法對整數(shù)數(shù)組進行排序。計數(shù)排序是一種穩(wěn)定的排序算法，適用于整數(shù)范圍不大的情況，它的時間復(fù)雜度為O(n + k)，其中n是待排序數(shù)組的大小，k是整數(shù)范圍(數(shù)組中最大元素與最小元素的差值)。
性能分析
計數(shù)排序的性能分析如下：
- 平均時間復(fù)雜度：O(n + k)，其中n是待排序數(shù)組的大小，k是整數(shù)范圍。
- 最壞時間復(fù)雜度：O(n + k)。
- 最佳時間復(fù)雜度：O(n + k)。
- 空間復(fù)雜度：O(n + k)，需要額外的計數(shù)數(shù)組和結(jié)果數(shù)組。
- 穩(wěn)定性：計數(shù)排序是一種穩(wěn)定的排序算法，不改變相同元素的相對順序。
使用場景
計數(shù)排序適用于以下情況：
- 需要排序的數(shù)據(jù)是整數(shù)或有限范圍內(nèi)的非負(fù)整數(shù)。
- 待排序數(shù)據(jù)中存在大量重復(fù)元素。
- 對穩(wěn)定性排序有要求，即相同元素的相對順序不變。
總結(jié)
計數(shù)排序是一種高效的非比較排序算法，適用于整數(shù)排序和穩(wěn)定性排序的場景。盡管它對整數(shù)范圍有一定要求，但在合適的情況下，計數(shù)排序能夠提供線性時間復(fù)雜度的排序性能，相對于其他復(fù)雜排序算法來說，它具有獨特的優(yōu)勢。因此，在選擇排序算法時，應(yīng)根據(jù)數(shù)據(jù)特點和性能需求來決定是否使用計數(shù)排序。
分享題目：計數(shù)排序（CountingSort）詳解
文章轉(zhuǎn)載：http://www.5511xx.com/article/cojdoio.html
