Java 中的基数排序是一种整数排序算法，它使用整数键并将键与共享相同有效位置和位值的各个数字进行分组。然后，根据升序/降序对元素进行排序。基数排序的主要思想是从最低有效数字到最高有效数字进行逐位排序。它使用计数排序作为子例程对数字数组进行排序。基数排序结合了计数排序，因此它可以对大数字和多数字进行排序，而不必通过增加算法排序的键范围来降低其效率。让我们更深入地研究基数排序，并通过一些示例来了解基数排序在 Java 中的工作原理。
开始您的免费软件开发课程
网络开发、编程语言、软件测试及其他
语法
基数排序包含有关如何执行排序的算法步骤或流程图。那么我们来看看基数排序的算法。
基数排序算法
第1步：首先，我们需要找到数组中最大的元素，即最大元素。让我们将 X 视为最大元素中的位数。
我们需要计算 X，因为我们需要遍历最大元素的位置值。
第2步：现在，我们需要遍历最大元素的每个位值。
第3步：我们需要使用任何稳定的排序算法对每个有效位值处的数字进行排序。
第 4 步： 元素现在根据单位位值 {X=0}
处的数字进行排序
第5步：然后，根据十位数字对元素进行排序{X=10}
第6步：然后，根据百位{X=100}的数字对元素进行排序
第 7 步： 如果数组中的元素还有更多位置值，即基于 X 值，则重复上述步骤。
Java 中基数排序是如何执行的？
让我们通过一些例子来看看基数排序是如何实现的。
示例#1
代码：
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]+" ");
}
}登录后复制
输出：
在这里，我们可以看到输入数组已使用基数排序和计数排序进行排序。
示例#2
代码：
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));
}
}登录后复制
输出：
所以在这里，我们使用不同的逻辑来使用基数排序对输入数组进行排序。
现在，让我向您解释或向您展示如何通过实例进行基数排序，
我们将输入数组作为 [72, 15, 30, 21, 13, 944, 417]
第 1 步： 从数组中获取最大值，即 944。因此，现在 X 值为 3，即 X = no。最大元素中的数字，这实际上意味着数组的排列将分三次进行
第2步：所以，现在我们将尝试根据最低有效数字来排列数字。
考虑到所有元素的单位位置值将重新排列数组，如下所示，
[30、21、72、13、944、15、417]
考虑到所有元素的十位值将重新排列数组，如下所示，
[13、15、417、21、30、944、72]
考虑到所有元素的百位值（如果有），将重新排列数组，如下所示，
[13、15、21、30、72、417、944]
第 3 步：数组已排序完毕。
结论
至此，我们将结束“Java 中的基数排序”一文。我们已经了解了基数排序是什么以及它是如何使用计数排序来实现的。它是最简单的排序形式之一，如果键很短，即元素的范围较小，则速度也会更快。在过去的几年里，排序技术已广泛应用于日常算法中。然而，也有一些缺点；基数排序在很大程度上取决于输入，即字母或数字，因此不如其他排序灵活。
以上是Java 基数排序的详细内容。更多信息请关注PHP中文网其他相关文章！
