Javaを使用して基数ソートアルゴリズムを実装する方法

Java を使用して基数ソート アルゴリズムを実装するにはどうすればよいですか?

基数ソート アルゴリズムは、要素のビット値に基づいてソートする非比較ソート アルゴリズムです。その中心的なアイデアは、並べ替える数値を単位、十、百、その他の桁に従ってグループ化し、各桁を順番に並べ替えて、最終的に順序付けられたシーケンスを取得することです。以下では、Java を使用して基数ソート アルゴリズムを実装する方法とコード例を詳しく紹介します。

まず、基数ソ​​ート アルゴリズムでは、ソートする数値を保存するための 2 次元配列を準備する必要があります。配列の行数は桁数によって決まります。たとえば、並べ替えられる数値の最大数が n の場合、配列の行数は log(n) 1 になります。各列は、その桁に対応する数値を格納するために使用されます。

次に、底の桁数を決定するために、並べ替える数値の最大値を見つける必要があります。これは、配列全体をループして最大値を取得することで実現できます。

次に、基数ソートを開始します。まず、1 桁ごとに対応するバケットに番号を割り当てます。このステップを実行するには、カウントソートを使用できます。具体的な方法は、サイズ 10 の計数配列を作成し、並べ替える配列内の数値を反復処理し、1 桁に従って対応するバケットに数値を入れ、バケット内の数値を並べ替えます。並べ替えた後、バケット内の数値を配列に戻し、順番に並べ替えます。

次に、十の位に応じて対応するバケットに番号を再度割り当て、バケット内の番号を並べ替えます。並べ替えた後、バケット内の数値を配列に戻し、再度順番に並べ替えます。

すべての桁が割り当てられ、並べ替えられるまで、上記の手順を繰り返します。最後に、並べ替えられる配列内の数値が順序付けされます。

次は、Java を使用して基数ソートを実装するコード例です。

public class RadixSort {
    public static void radixSort(int[] arr) {
        // 找到待排序数组中的最大值，确定需要进行排序的位数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
      
        // 计算需要进行排序的位数
        int digit = 1;
        while (max / 10 > 0) {
            max /= 10;
            digit++;
        }
      
        // 创建桶和计数数组
        int[][] bucket = new int[10][arr.length];
        int[] count = new int[10];
      
        // 进行基数排序
        for (int i = 0; i < digit; i++) {
            for (int j = 0; j < arr.length; j++) {
                int num = (arr[j] / (int) Math.pow(10, i)) % 10;
                bucket[num][count[num]++] = arr[j];
            }
          
            int k = 0;
            for (int j = 0; j < count.length; j++) {
                if (count[j] != 0) {
                    for (int l = 0; l < count[j]; l++) {
                        arr[k++] = bucket[j][l];
                    }
                    count[j] = 0;
                }
            }
        }
    }
  
    public static void main(String[] args) {
        int[] arr = {432, 524, 236, 679, 321, 546, 457};
        radixSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

上記は、Java を使用して基数ソート アルゴリズムを実装する方法とコード例です。基数ソート アルゴリズムは正の整数のソートに適していることに注意してください。負の整数または負の数値を含む配列の場合は、ソートのために最初に非負の数値に変換する必要があります。

以上がJavaを使用して基数ソートアルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。