How to implement radix sort algorithm using java

How to implement the radix sorting algorithm using Java?

The radix sorting algorithm is a non-comparative sorting algorithm that sorts based on the bit value of elements. Its core idea is to group the numbers to be sorted according to units, tens, hundreds and other digits, and then sort each digit in turn to finally obtain an ordered sequence. The following will introduce in detail how to implement the radix sort algorithm using Java and provide code examples.

First of all, the radix sorting algorithm needs to prepare a two-dimensional array to save the numbers to be sorted. The number of rows of the array is determined by the number of digits. For example, if the maximum number of numbers to be sorted is n, then the number of rows of the array is log(n) 1. Each column is used to store the number corresponding to that digit.

Next, you need to find the maximum value among the numbers to be sorted to determine the number of digits in the base. This can be achieved by looping through the entire array and taking the maximum value.

Then, start radix sorting. First, allocate numbers into corresponding buckets according to single digits. You can use counting sort to achieve this step. The specific method is to create a counting array with a size of 10, iterate through the numbers in the array to be sorted, put the numbers into the corresponding buckets according to single digits, and then sort the numbers in the buckets. After sorting, put the numbers in the bucket back into the array to be sorted in order.

Next, allocate the numbers again to the corresponding buckets according to the tens digit, and sort the numbers in the buckets. After sorting, put the numbers in the bucket back into the array to be sorted in order again.

Repeat the above steps until all digits are allocated and sorted. Finally, the numbers in the array to be sorted are ordered.

The following is a code example of using Java to implement radix sorting:

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

The above is the method and code example of using Java to implement the radix sorting algorithm. It should be noted that the radix sorting algorithm is suitable for sorting positive integers. For negative integers or arrays containing negative numbers, they need to be converted into non-negative numbers first for sorting.

The above is the detailed content of How to implement radix sort algorithm using java. For more information, please follow other related articles on the PHP Chinese website!