Java實(shí)現(xiàn)計(jì)數(shù)排序的方法

Java實(shí)現(xiàn)計(jì)數(shù)排序的方法？這個問題可能是我們?nèi)粘W(xué)習(xí)或工作經(jīng)常見到的。希望通過這個問題能讓你收獲頗深。下面是小編給大家?guī)淼膮⒖純?nèi)容，讓我們一起來看看吧！

涉縣網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián),涉縣網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為涉縣超過千家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站建設(shè)公司要多少錢，請找那個售后服務(wù)好的涉縣做網(wǎng)站的公司定做！

計(jì)數(shù)排序，屬于桶排序特殊的一種。

當(dāng)要排序n個數(shù)據(jù)的時候，如果所處的范圍不大，我們可以取其中的最大值K，并將數(shù)據(jù)分散在K個桶里面，

每個桶里面的數(shù)據(jù)都是相同的（這樣省去了桶內(nèi)排序的時間），然后順序取出就好啦。

當(dāng)然計(jì)數(shù)排序說起來簡單，寫起來有些地方不好理解。

比如我們現(xiàn)在有2，5，3，0，2，3，0，3這8個數(shù)，要對它排序，我們就可以先取到它的最大值5，然后確定范圍在0-5，

我們申請一個0-5的內(nèi)存空間去分別計(jì)算每個位置對應(yīng)的每個數(shù)的個數(shù)。

下圖表示的就是0-5這個內(nèi)存空間的數(shù)據(jù)，我們可以看到其中0出現(xiàn)了兩次，1出現(xiàn)了0次，2出現(xiàn)了兩次，3出現(xiàn)了三次，4出現(xiàn)了0次，5出現(xiàn)了一次。

同時還可以總結(jié)一些規(guī)律出來，比如我們現(xiàn)在看到c[2]這個位置，2出現(xiàn)了兩次，在2前面c[0] + c[1]總共有2個元素，所以c[2]對應(yīng)這兩個2在原數(shù)組中的位置是2，3，我們可以得出規(guī)律c[2]所在位置 = c[0] + c[1]，后面的c[3]的位置 = c[2] + c[1]，我們就這樣挨著順序和：然后我們掃描原數(shù)組2，5，3，0，2，3，0，3，每遇到一個數(shù)，就將該數(shù)代入c數(shù)組的索引中取出當(dāng)前元素在排序之后真正的索引。

我的Java實(shí)現(xiàn)如下：

package com.structure.sort;
/**
 * @author zhangxingrui
 * @create 2019-01-30 13:45
 **/
public class CountingSort {
    public static void main(String[] args) {
        int[] numbers = {3, 9, 2, 1, 8, 7, 6, 10, 9};
        // 假設(shè)數(shù)組中存儲的都是非負(fù)整數(shù)
        countingSort(numbers);
        for (int number : numbers) {
            System.out.println(number);
        }
    }
    /**
     * @Author: xingrui
     * @Description: 計(jì)數(shù)排序
     * @Date: 13:57 2019/1/30
     */
    private static void countingSort(int[] numbers){
        int n = numbers.length;
        int maxNumber = numbers[0];
        for(int i = 1; i < n; ++i){
            if(numbers[i] > maxNumber)
                maxNumber = numbers[i];
        }
        int[] r = new int[n];
        int[] c = new int[maxNumber + 1];
        for(int i = 0; i < n; ++i){
            c[numbers[i]]++;
        }
        for(int i = 1; i <= maxNumber; ++i){
            c[i] = c[i-1] + c[i];
        }
        for (int i = n - 1; i >= 0; --i){
            int index = c[numbers[i]];
            r[index - 1] = numbers[i];
            c[index]--;
        }
        for(int i = 0; i < n; ++i){
            numbers[i] = r[i];
        }
    }
}

其中關(guān)鍵的代碼：

for (int i = n - 1; i >= 0; --i){
            int index = c[numbers[i]];
            r[index - 1] = numbers[i];
            c[index]--;5         
            }

從c數(shù)組中取出排序之后的索引。

感謝各位的閱讀！看完上述內(nèi)容，你們對Java實(shí)現(xiàn)計(jì)數(shù)排序的方法大概了解了嗎？希望文章內(nèi)容對大家有所幫助。如果想了解更多相關(guān)文章內(nèi)容，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

文章標(biāo)題：Java實(shí)現(xiàn)計(jì)數(shù)排序的方法
本文來源：http://bm7419.com/article4/gocsie.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供Google、網(wǎng)站內(nèi)鏈、關(guān)鍵詞優(yōu)化、網(wǎng)站改版、網(wǎng)頁設(shè)計(jì)公司、靜態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)