Radix Sort

Algorithm Thinking:

The number of passes in radix sort equals the length of the maximum number

Use 10 buckets to collect values, first count the digit values corresponding to the count array, then accumulate the count array

Through the accumulated array, we can determine which elements are at which positions As follows: count[5] = 7, there are 6 elements before it, and both indices 5 and 6 are numbers with 5 in the ones place count [2, 3, 4, 4, 5, 7, 7, 7, 7, 7] result [240, 430, 421, 532, 124, 115, 305] NOTE: The counting cumulative array and reverse backfilling of elements ensure the stability of the algorithm

package simpleAlgorithm;

import java.util.Arrays;

/**
 * @Author: WhaleFall541
 * @Date: 2021/6/12 22:59
 * [Video](https://www.bilibili.com/video/BV184411L79P?t=650)
 * Algorithm thinking:
 * The number of passes in radix sort equals the length of the maximum number
 * Use 10 buckets to collect values, first count the digit values corresponding to the count array, then accumulate the count array
 * Through the accumulated array, we can determine which elements are at which positions
 * As follows: count[5] = 7, there are 6 elements before it, and both indices 5 and 6 are numbers with 5 in the ones place

 * NOTE: The counting cumulative array and reverse backfilling of elements ensure the stability of the algorithm
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[]{444444224, 240, 115, 532, 305, 430, 124};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    static void radixSort(int[] arr) {

        int n = arr.length;
        if (n == 0) return;

        // 1. Find the maximum number
        int max = arr[0];
        for (int i = 0; i < n; i++)
            if (arr[i] > max)
                max = arr[i];

        // Calculate the number of digits in the maximum number
        int bit = String.valueOf(max).length();
        for (int i = 0; i < bit; i++) {
            int base = (int) Math.pow(10, i);

            int[] count = new int[10];
            int[] result = new int[arr.length];

            // Accumulate corresponding positions in count array based on digits 0-9
            for (int j = 0; j < n; j++) {
                // Value at the digit position
                int number = arr[j] / base % 10;
                count[number]++;
            }

            // Cumulative counting
            for (int j = 1; j < count.length; j++) {
                count[j] = count[j - 1] + count[j];
            }

            for (int j = n - 1; j >= 0; j--) {
                int number = arr[j] / base % 10;
                // Place elements back to result according to cumulative array
                //  count [2, 3, 4, 4, 5, 7, 7, 7, 7, 7]
                //  result [240, 430, 421, 532, 124, 115, 305]
                // --count[number] indicates how many elements are before the corresponding position in the array
                // For example, count[5] = 7, there are 6 elements before it, and both indices 5 and 6 are numbers with 5 in the ones place
                result[--count[number]] = arr[j];
            }

            // Put result set back to original array for next round of sorting
            System.arraycopy(result, 0, arr, 0, n);
            // Clear count array
            Arrays.fill(count, 0);
        }
    }

}