カウントソート（CountingSort）のJava実装のコード例

この記事では、カウントソート (CountingSort) の Java 実装に関するコード例を紹介します。必要な方は参考にしてください。

カウントソートは、特殊なタイプのバケットソートです。

n 個のデータを並べ替える場合、範囲が大きくなければ、最大値 K をとり、データを K 個のバケットに分散できます。

各バケット内のデータはすべて同じようにして（これにより、バケット内で分類する時間が節約されます）、順番に取り出されます。

もちろん、数えたり並べ替えたりするのは、言葉で言うのは簡単ですが、書くとわかりにくいところもあります。

たとえば、現在 8 つの数値があります: 2、5、3、0、2、3、0、3。それらを並べ替えるには、まずその最大値の 5 を取得し、次に範囲を決定します。 0-5,

0-5 のメモリ空間を適用して、各位置に対応する各数値の数を計算します。

下の図は、メモリ空間 0 ～ 5 のデータを示しています。0 が 2 回、1 が 0 回、2 が 3 回、4 が 0 回、5 回出現していることがわかります。一度登場した。

同時に、いくつかのルールを要約することもできます。たとえば、位置 c[2] には 2 が 2 回表示され、c[0] c は合計 2 つあります。 [1] が 2. 要素の前にあるため、c[2] は元の配列内の 2 つの 2 の位置 (2 と 3) に対応します。 c[2] の位置 = c[ という規則を引くことができます。 0] c[1]、および次の c[3] Position = 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 配列からソートされたインデックスを取得します。

以上がカウントソート（CountingSort）のJava実装のコード例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。