Radix sort

Description

The lower bound for Comparison based sorting algorithm, like Merge Sort, Heap Sort, Quick Sort .. etc, is O(nlgn) and they can’t do better than O(n).

Radix Sort(or Bucket Sort) is the answer. It can sort the array of total number n in time complexity O(n).

Code

class Solution {
    public void RadixSort(int[] nums) {
        int N = nums.length;
        if(N == 0){
            return ;
        }
        int max = nums[0];
        for(int i = 1; i < N; i ++){
            max = Math.max(max, nums[i]);
        }
        int[][] record = new int[10][N];
        int[] recordCount = new int[10];
        int divisor = 1;
        while(max > 0){
            max /= 10;
            for(int i = 0; i < N; i ++){
                int index = (nums[i] / divisor) % 10;
                record[index][recordCount[index]] = nums[i];
                recordCount[index] ++;
            }
            divisor *= 10;
            int id = 0;
            for(int i = 0; i < 10; i ++){
                for(int j = 0; j < recordCount[i]; j ++){
                    nums[id] = record[i][j];
                    id ++;
                }
                recordCount[i] = 0;
            }
        }
    }
}