Java怎么實現(xiàn)count排序

這篇文章主要講解了“Java怎么實現(xiàn)count排序”，文中的講解內(nèi)容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Java怎么實現(xiàn)count排序”吧！

簡介

count排序是一種空間換時間的算法，我們借助一個外部的count數(shù)組來統(tǒng)計各個元素出現(xiàn)的次數(shù)，從而最終完成排序。

count排序的例子

count排序有一定的限制，因為外部的count數(shù)組長度是和原數(shù)組的元素范圍是一致的，所以count排序一般只適合數(shù)組中元素范圍比較小的情況。

我們舉一個0-9的元素的排序的例子：3,4,2,5,6,2,4,9,1,3,5。

先看一個動畫，看看是怎么排序的：

count數(shù)組里面存放的是從0到9這些元素出現(xiàn)的次數(shù)。

我們遍歷原始數(shù)組，遇到相應的數(shù)字就給相應的count+1。

等所有的元素都count之后，再根據(jù)count數(shù)組中的值還原排序過后的數(shù)組。

count排序的java實現(xiàn)

count排序很簡單，我們主要掌握下面兩個大的步驟：

1. 遍歷原始數(shù)組，構(gòu)建count數(shù)組。

2. 根據(jù)count數(shù)組中的count值，重新構(gòu)建排序數(shù)組。

public class CountingSort {

    public void doCountingSort(int[] array){
        int n = array.length;

        // 存儲排序過后的數(shù)組
        int output[] = new int[n];

        // count數(shù)組，用來存儲統(tǒng)計各個元素出現(xiàn)的次數(shù)
        int count[] = new int[10];
        for (int i=0; i<10; ++i) {
            count[i] = 0;
        }
        log.info("初始化count值:{}",count);

        // 將原始數(shù)組中數(shù)據(jù)出現(xiàn)次數(shù)存入count數(shù)組
        for (int i=0; i<n; ++i) {
            ++count[array[i]];
        }
        log.info("count之后count值:{}",count);

        //遍歷count，將相應的數(shù)據(jù)插入output
        int j=0;
        for(int i=0; i<10; i++){
            while(count[i]-- > 0){
                output[j++]=i;
            }
        }
        log.info("構(gòu)建output之后的output值:{}",output);

        //將排序后的數(shù)組寫回原數(shù)組
        for (int i = 0; i<n; ++i)
            array[i] = output[i];
    }

    public static void main(String[] args) {
        int[] array= {3,4,2,5,6,2,4,9,1,3,5};
        CountingSort countingSort=new CountingSort();
        log.info("countingSort之前的數(shù)組為:{}",array);
        countingSort.doCountingSort(array);
    }
}

上面的注釋應該很清楚了。

運行的結(jié)果如下：

count排序的第二種方法

在我們獲得count數(shù)組中每個元素的個數(shù)之后，其實我們還有另外一個生成結(jié)果數(shù)組的辦法：

// 這里是一個小技巧，我們根據(jù)count中元素出現(xiàn)的次數(shù)計算對應元素第一次應該出現(xiàn)在output中的下標。
        //這里的下標是從右往左數(shù)的
        for (int i=1; i<10; i++) {
            count[i] += count[i - 1];
        }
        log.info("整理count對應的output下標:{}",count);
        // 根據(jù)count中的下標，構(gòu)建排序后的數(shù)組
        //插入一個之后，相應的count下標要減一
        for (int i = n-1; i>=0; i--)
        {
            output[count[array[i]]-1] = array[i];
            --count[array[i]];
        }
        log.info("構(gòu)建output之后的output值:{}",output);

主要分為兩步:

第一步我們根據(jù)count中元素出現(xiàn)的次數(shù)計算對應元素第一次應該出現(xiàn)在output中的下標。這里的下標是從右往左數(shù)的。

第二步根據(jù)count中的下標，構(gòu)建排序后的數(shù)組，插入一個之后，相應的count下標要減一。

感謝各位的閱讀，以上就是“Java怎么實現(xiàn)count排序”的內(nèi)容了，經(jīng)過本文的學習后，相信大家對Java怎么實現(xiàn)count排序這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！