Radix Sort Java-javaTutorial-php.cn

Isih Radix dalam Java ialah algoritma pengisihan integer yang menggunakan kekunci integer dan mengumpulkan kekunci dengan digit individu yang berkongsi kedudukan penting dan nilai tempat yang sama. Kemudian, elemen diisih mengikut susunan yang semakin meningkat/mengurang. Idea utama isihan Radix adalah untuk melakukan isihan digit demi digit bermula daripada digit paling kecil hingga digit paling ketara. Ia menggunakan pengisihan mengira sebagai subrutin untuk mengisih tatasusunan nombor. Isih Radix menggabungkan isihan mengira supaya ia boleh mengisih digit besar dan berbilang tanpa perlu mengurangkan kecekapannya dengan meningkatkan julat algoritma kunci yang akan disusun. Mari kita gali lebih dalam tentang isihan Radix dan lihat Cara isihan Radix berfungsi dalam Java dengan beberapa contoh.

Mulakan Kursus Pembangunan Perisian Percuma Anda

Pembangunan web, bahasa pengaturcaraan, ujian perisian & lain-lain

Sintaks

Isih Radix mempunyai langkah-langkah Algoritma atau Carta Alir tentang Cara Isih dilakukan. Jadi mari kita lihat Algoritma Isih Radix.

Algoritma Isih Radix

Langkah 1: Mula-mula, kita perlu mencari elemen terbesar dalam tatasusunan, iaitu, elemen maks. Dan mari kita anggap X sebagai bilangan digit dalam elemen maksimum.

Kita perlu mengira X kerana kita perlu melalui nilai tempat bagi unsur maksimum.

Langkah 2: Sekarang, kita perlu melalui setiap nilai tempat bagi elemen maksimum.

Langkah 3: Kita perlu menggunakan sebarang algoritma pengisihan yang stabil untuk mengisih digit pada setiap nilai tempat yang penting.

Langkah 4: Elemen kini diisih berdasarkan digit pada nilai tempat unit {X=0}

Langkah 5: Kemudian, susun elemen berdasarkan digit di tempat sepuluh {X=10}

Langkah 6: Kemudian, susun elemen berdasarkan digit di tempat Ratusan {X=100}

Langkah 7: Langkah di atas berulang jika terdapat lagi nilai tempat untuk elemen dalam tatasusunan, iaitu, berdasarkan nilai X.

Bagaimana Isih Radix Dilakukan di Jawa?

Mari kita semak Cara isihan Radix dilaksanakan dengan beberapa contoh.

Contoh #1

Kod:

import java.util.*;
public class radixSorting {
static int get_maxVal(int radixArr[], int arrLen) {
int maxVal = radixArr[0];
for (int i = 1; i < arrLen; i++)
if (radixArr[i] > maxVal)
maxVal = radixArr[i];
return maxVal;
}
static void countSorting(int radixArr[], int arrLen, int exp) {
int resultArray[] = new int[arrLen];
int i;
int countVal[] = new int[10];
Arrays.fill(countVal,0);
for (i = 0; i < arrLen; i++)
countVal[ (radixArr[i]/exp)%10 ]++;
for (i = 1; i < 10; i++)
countVal[i] += countVal[i - 1];
for (i = arrLen - 1; i >= 0; i--) {
resultArray[countVal[ (radixArr[i]/exp)%10 ] - 1] = radixArr[i];
countVal[ (radixArr[i]/exp)%10 ]--;
}
for (i = 0; i < arrLen; i++)
radixArr[i] = resultArray[i];
}
static void radix_array_sort(int radixArr[], int arrLen) {
int m = get_maxVal(radixArr, arrLen);
for(int exp = 1; m/exp > 0; exp *= 10)
countSorting(radixArr, arrLen, exp);
}
public static void main (String[] args) {
int radixArr[] = {32,456,71,10,9,892,55,90,23,667};
int arrLen = radixArr.length;
System.out.println("Array after radix sort is ");
radix_array_sort(radixArr, arrLen);
for (int i=0; i<arrLen; i++)
System.out.print(radixArr[i]+" ");
}
}

Salin selepas log masuk

Output:

Radix Sort Java

Jadi di sini, kita dapat melihat bahawa tatasusunan input telah diisih menggunakan isihan Radix bersama-sama dengan Isihan Pengiraan.

Contoh #2

Kod:

import java.util.Arrays;
public class RadixSorting {
public static void sorting(int[] inputArray) {
RadixSorting.sorting(inputArray, 10);
}
public static void sorting(int[] inputArray, int radix) {
if (inputArray.length == 0) {
return;
}
int minVal = inputArray[0];
int maxVal = inputArray[0];
for (int i = 1; i < inputArray.length; i++) {
if (inputArray[i] < minVal) {
minVal = inputArray[i];
} else if (inputArray[i] > maxVal) {
maxVal = inputArray[i];
}
}
int exponentVal = 1;
while ((maxVal - minVal) / exponentVal >= 1) {
RadixSorting.countingSort_by_digit(inputArray, radix, exponentVal, minVal);
exponentVal *= radix;
}
}
private static void countingSort_by_digit(
int[] inputArray, int radix, int exponentVal, int minVal) {
int bucket_index;
int[] bucket = new int[radix];
int[] output = new int[inputArray.length];
for (int i = 0; i < radix; i++) {
bucket[i] = 0;
}
for (int i = 0; i < inputArray.length; i++) {
bucket_index = (int)(((inputArray[i] - minVal) / exponentVal) % radix);
bucket[bucket_index]++;
}
for (int i = 1; i < radix; i++) {
bucket[i] += bucket[i - 1];
}
for (int i = inputArray.length - 1; i >= 0; i--) {
bucket_index = (int)(((inputArray[i] - minVal) / exponentVal) % radix);
output[--bucket[bucket_index]] = inputArray[i];
}
for (int i = 0; i < inputArray.length; i++) {
inputArray[i] = output[i];
}
}
public static void main(String args[])
{
RadixSorting rs = new RadixSorting();
int radix_input[] = {72, 15, 30, 21, 13, 944, 417};
System.out.println("Original Input Array:");
System.out.println(Arrays.toString(radix_input));
rs.sorting(radix_input);
System.out.println("Sorted Array using Radix Sort:");
System.out.println(Arrays.toString(radix_input));
}
}

Salin selepas log masuk

Output:

Radix Sort Java

Jadi di sini, kami menggunakan logik yang berbeza untuk mendapatkan tatasusunan input yang diisih menggunakan Isih Radix.

Sekarang, izinkan saya menerangkan kepada anda atau menunjukkan kepada anda cara isihan Radix dilakukan dengan Contoh langsung,

Kami akan mengambil tatasusunan input sebagai [72, 15, 30, 21, 13, 944, 417]

Langkah 1: Dapatkan nilai maksimum daripada tatasusunan, iaitu, 944. Jadi, kini nilai X ialah 3, iaitu, X = tidak. daripada digit dalam elemen Maksimum, yang sebenarnya bermakna susunan tatasusunan akan dilakukan dalam tiga kali

Langkah 2: Jadi, sekarang kita akan cuba menyusun nombor berdasarkan digit terkecil.

Memandangkan nilai tempat unit bagi semua elemen akan menyusun semula tatasusunan seperti di bawah,

[30, 21, 72, 13, 944, 15, 417]

Memandangkan nilai tempat puluhan bagi semua elemen akan menyusun semula tatasusunan seperti di bawah,

[13, 15, 417, 21, 30, 944, 72]

Memandangkan nilai tempat Ratusan semua elemen, jika ada, akan menyusun semula tatasusunan seperti di bawah,

[13, 15, 21, 30, 72, 417, 944]

Langkah 3: Itu sahaja tatasusunan telah diisih.

Kesimpulan

Dengan ini, kami akan menyimpulkan artikel ‘Isih Radix di Jawa.’ Kami telah melihat apakah jenis Radix dan cara ia dilaksanakan menggunakan jenis pengiraan. Ia adalah salah satu bentuk pengisihan yang paling mudah dan juga lebih pantas jika kekuncinya pendek, iaitu julat elemen adalah kurang. Sejak beberapa tahun kebelakangan ini, teknik pengisihan telah digunakan secara meluas dalam penggunaan Algoritma harian. Walau bagaimanapun, terdapat juga beberapa kelemahan; Isih Radix banyak bergantung pada input, iaitu, huruf atau digit, dan oleh itu kurang fleksibel berbanding jenis lain.

Atas ialah kandungan terperinci Radix Sort Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!