基数排序的 Java 程序
java 8server side programmingprogramming
基数排序是一种根据每个元素(或数字)中每个数字对元素进行排序的排序技术。元素将根据个位数字(也称为最低有效位)、十位数字(也称为最高有效位)、百位数字等等进行排序。
示例
以下是 Java 中基数排序的示例 −
import java.util.*;
public class my_radix_sorting {
static int get_max_val(int my_arr[], int arr_len) {
int max_val = my_arr[0];
for (int i = 1; i < arr_len; i++)
if (my_arr[i] > max_val)
max_val = my_arr[i];
return max_val;
}
static void countSort(int my_arr[], int arr_len, int exp) {
int result[] = new int[arr_len];
int i;
int count[] = new int[10];
Arrays.fill(count,0);
for (i = 0; i < arr_len; i++)
count[ (my_arr[i]/exp)%10 ]++;
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
for (i = arr_len - 1; i >= 0; i--) {
result[count[ (my_arr[i]/exp)%10 ] - 1] = my_arr[i];
count[ (my_arr[i]/exp)%10 ]--;
}
for (i = 0; i < arr_len; i++)
my_arr[i] = result[i];
}
static void radix_sort(int my_arr[], int arr_len) {
int m = get_max_val(my_arr, arr_len);
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(my_arr, arr_len, exp);
}
public static void main (String[] args) {
int my_arr[] = {56, 78, 102, 345, 67, 90, 102, 45, 78};
int arr_len = my_arr.length;
System.out.println("The array after performing radix sort is ");
radix_sort(my_arr, arr_len);
for (int i=0; i<arr_len; i++)
System.out.print(my_arr[i]+" ");
}
}
输出
The array after performing radix sort is 45 56 67 78 78 90 102 102 345
解释
在基数排序中，每个元素都根据其数字进行排序，其中每个元素的最低有效位首先排序，最高有效位最后排序。它使用计数排序作为子函数来执行其排序功能。
给定一个元素数组，第一步是根据最低有效位(即个位)对元素进行排序。接下来，数组中的元素根据十位进行排序。然后，根据百位进行排序，依此类推。这是借助‘get_max_val’函数完成的。在主函数中，定义数组，并将该数组作为参数传递给‘radix_sort’函数。
