用于Radix Sort的Java程序

基数排序是一种排序技术，可根据每个元素（或数字）中的每个数字对元素进行排序。基于一个位数（也称为最低有效位数）和十位数（也称为最高有效位数），数百个位数等等，对元素进行排序。

示例

以下是Java中Radix Sort的示例-

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”功能完成的。在main函数中，定义了数组，并将该数组作为参数传递给“ radix_sort”函数。