この記事では、カウントソート (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 サイトの他の関連記事を参照してください。