Bagaimana untuk melaksanakan algoritma isihan radix menggunakan java

Bagaimana untuk melaksanakan algoritma isihan radix menggunakan Java?

Algoritma isihan radix ialah algoritma isihan bukan perbandingan yang mengisih berdasarkan nilai bit unsur. Idea terasnya adalah untuk mengumpulkan nombor yang akan diisih mengikut unit, puluh, ratusan dan digit lain, dan kemudian mengisih setiap digit secara bergilir-gilir untuk akhirnya mendapatkan urutan tertib. Berikut akan memperkenalkan secara terperinci cara melaksanakan algoritma isihan radix menggunakan Java dan memberikan contoh kod.

Pertama sekali, algoritma pengisihan radix perlu menyediakan tatasusunan dua dimensi untuk menyimpan nombor yang hendak diisih. Bilangan baris tatasusunan ditentukan oleh bilangan digit Contohnya, jika bilangan maksimum nombor yang hendak diisih ialah n, maka bilangan baris tatasusunan ialah log(n) + 1. Setiap lajur digunakan untuk menyimpan nombor yang sepadan dengan digit tersebut.

Seterusnya, anda perlu mencari nilai maksimum antara nombor yang hendak diisih untuk menentukan bilangan digit dalam pangkalan. Ini boleh dicapai dengan menggelung seluruh tatasusunan dan mengambil nilai maksimum.

Kemudian, mulakan pengisihan radix. Pertama, peruntukkan nombor ke dalam baldi yang sepadan mengikut digit tunggal. Anda boleh menggunakan jenis mengira untuk mencapai langkah ini. Kaedah khusus adalah untuk mencipta tatasusunan mengira dengan saiz 10, lelaran melalui nombor dalam tatasusunan yang hendak diisih, masukkan nombor ke dalam baldi yang sepadan mengikut digit tunggal, dan kemudian susun nombor dalam baldi. Selepas mengisih, letakkan semula nombor dalam baldi ke dalam tatasusunan untuk diisih mengikut tertib.

Seterusnya, peruntukkan nombor sekali lagi kepada baldi yang sepadan mengikut digit sepuluh, dan susun nombor dalam baldi. Selepas mengisih, letakkan semula nombor dalam baldi ke dalam tatasusunan untuk diisih mengikut urutan semula.

Ulang langkah di atas sehingga semua digit diperuntukkan dan diisih. Akhirnya, nombor dalam tatasusunan yang hendak diisih disusun.

Berikut ialah contoh kod menggunakan Java untuk melaksanakan isihan radix:

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 + " ");
        }
    }
}

Di atas ialah kaedah dan contoh kod menggunakan Java untuk melaksanakan algoritma isihan radix. Perlu diingatkan bahawa algoritma pengisihan radix sesuai untuk mengisih integer positif Untuk integer negatif atau tatasusunan yang mengandungi nombor negatif, ia perlu ditukar kepada nombor bukan negatif terlebih dahulu untuk mengisih.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma isihan radix menggunakan java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!