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

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

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

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

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

當(dāng)然計(jì)數(shù)排序說(shuō)起來(lái)簡(jiǎn)單，寫(xiě)起來(lái)有些地方不好理解。

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

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

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

同時(shí)還可以總結(jié)一些規(guī)律出來(lái)，比如我們現(xiàn)在看到c[2]這個(gè)位置，2出現(xiàn)了兩次，在2前面c[0] + c[1]總共有2個(gè)元素，所以c[2]對(duì)應(yīng)這兩個(gè)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，每遇到一個(gè)數(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ù)組中存儲(chǔ)的都是非負(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)容，你們對(duì)Java實(shí)現(xiàn)計(jì)數(shù)排序的方法大概了解了嗎？希望文章內(nèi)容對(duì)大家有所幫助。如果想了解更多相關(guān)文章內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道。