Java實作計數排序（CountingSort）的程式碼範例

這篇文章帶給大家的內容是關於Java實作計數排序（CountingSort）的程式碼範例，有一定的參考價值，有需要的朋友可以參考一下，希望對你有所幫助。

計數排序，屬於桶排序特殊的一種。

當要排序n個資料的時候，如果所處的範圍不大，我們可以取其中的最大值K，並將資料分散在K個桶裡面，

每個桶裡面的資料都是相同的（這樣省去了桶內排序的時間），然後依序取出就好啦。

當然計數排序說起來簡單，寫起來有些地方不好理解。

例如我們現在有2，5，3，0，2，3，0，3這8個數，要對它排序，我們就可以先取到它的最大值5，然後確定範圍在0-5，

我們申請一個0-5的記憶體空間去分別計算每個位置對應的每個數的個數。

下圖表示的就是0-5這個記憶體空間的數據，我們可以看到其中0出現了兩次，1出現了0次，2出現了兩次，3出現了三次，4出現了0次，5出現了一次。

同時還可以總結一些規律出來，例如我們現在看到c[2]這個位置，2出現了兩次，在2前面c[0] c[1]總共有2個元素，所以c[2]對應這兩個2在原數組中的位置是2，3，我們可以得到規律c[2]所在位置= c[0] c[1]，後面的c[3]的位置= c[2] c[1]，我們就這樣挨著順序和：然後我們掃描原數組2，5，3，0，2，3，0，3，每遇到一個數，就將該數代入c數組的索引中取出當前元素在排序之後的真正索引。

 我的Java實作如下：

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};
        // 假设数组中存储的都是非负整数
        countingSort(numbers);
        for (int number : numbers) {
            System.out.println(number);
        }
    }
    /**
     * @Author: xingrui
     * @Description: 计数排序
     * @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];
        }
    }
}

其中關鍵的程式碼：

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

從c陣列中取出排序之後的索引。

以上是Java實作計數排序（CountingSort）的程式碼範例的詳細內容。更多資訊請關注PHP中文網其他相關文章！