Introduction to the

Radix sort was invented by Herman Holery in 1887. Radix sort belongs to “distribution sort”, also known as “bucket sort” or bin sort, as its name implies, it allocates the elements to be sorted to some “buckets” by the values of each bit of the key value. Radix sort is a sort of stability. In some cases, the efficiency of radix sort is higher than that of other stability sort.

Time complexity

O(n*k) k: indicates the number of buckets

Thought analysis

All the values to be compared are unified into the same digit length, and zeros are added in front of the shorter digit. Then, sort the order one by one, starting with the lowest order. So from the lowest order to the highest order, the sequence becomes an ordered sequence.

Code implementation

/** * < base sort > **@date: 2020/12/29 11:18 下午
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {53.3.542.748.14.214};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void radixSort(int[] arr) {
        // Take the length of the largest number = the number of times the bucket needs to be loaded
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(arr[i] > max) { max = arr[i]; }}int maxLength = (max + "").length();

        / / data
        int[][] bucket = new int[10][arr.length];

        // The current index of each bucket
        int[] bucketIndex = new int[10];
        // loop through each digit
        for (int i = 0, m = 1; i < maxLength; i++, m *= 10) {
            // Loop each element into the bucket
            for (int k = 0; k < arr.length; k++) {
                / / base
                int radix = arr[k] / m % 10;
                // Access the cardinality to the corresponding bucket
                bucket[radix][bucketIndex[radix]++] = arr[k];
            }
            // Fetch the data in the bucket into the original array
            int arrIndex = 0;
            for (int b = 0; b < bucket.length; b++) {
                for (int bi = 0; bi < bucketIndex[b]; bi++) {
                    arr[arrIndex++] = bucket[b][bi];
                }
                bucketIndex[b] = 0; }}}}Copy the code

Run output:

[3, 14, 53, 214, 542, 748]

conclusion

  1. Radix sort is a fast extension of traditional bucket sort.
  2. Radix sort is a classic space-for-time method, which takes up a lot of memory and is prone to cause OutofMemoryErrors when sorting massive data.