import java.util.Arrays;

public class RadixSort {

    public static void main(String[] args) {
        int[] array = new int[]{5, 3, 9, 1, 6, 4, 10, 2, 8, 7, 15, 3, 2};

        System.out.println("Before: " + Arrays.toString(array));
        sort1(array);
        System.out.println("After:  " + Arrays.toString(array));

        array = new int[]{-5, 3, 9, 1, 6, 4, 10, 2, 8, 7, 15, 3, 2};
        sort2(array);
        System.out.println("After:  " + Arrays.toString(array));
    }

    public static void sort1(int[] arr) {

        // This method doesn't support negative values

        if (arr.length <= 1) {
            return;
        }

        int max = 0;

        // sort out the max element
        for (int i = 0; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }

        // Bucket numbers, here we adopt 10 buckets, also known as decimal base.
        // More buckets, more efficient, but more memory space.
        int bucketNum = 10;

        int maxLen = 1;

        // sort out the length of max element
        while (max / bucketNum > 0) {
            maxLen++;
            max = max / bucketNum;
        }

        int[][] buckets = new int[bucketNum][arr.length];

        // base is determined by allocated bucket number
        int base = bucketNum;

        for (int i = 0; i < maxLen; i++) {

            // keep track of the size of each bucket for later insertion
            int[] bktSize = new int[bucketNum];

            // allocate the elements to corresponding buckets according to the ith digit counting from tail
            for (int j = 0; j < arr.length; j++) {

                // find out the jth digit counting from the tail
                // base=10, arr[j]=172; arr[j] % base=2, base/10=1; 2/1=2
                int bktId = (arr[j] % base) / (base / bucketNum);

                // Even element arr[x] and arr[y] share same bucket, arr[x] will be put into the bucket first
                // if arr[x]'s (j-1)th digit is larger than arr[y]'s because of previous round sorting on (j-1)th digit.
                buckets[bktId][bktSize[bktId]] = arr[j];

                bktSize[bktId]++;
            }

            int count = 0;

            // collect the elements in order which are sorted by the ith digit
            for (int b = 0; b < buckets.length; b++) {
                for (int p = 0; p < bktSize[b]; p++) {
                    arr[count++] = buckets[b][p];
                }
            }

            base *= bucketNum;
        }
    }

    public static void sort2(int[] arr) {

        // This supports negative values, just double the quantity of buckets.

        if (arr.length <= 1) {
            return;
        }

        int max = 0;

        // sort out the max element
        for (int i = 0; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }

        // Bucket numbers, here we adopt 10 buckets, also known as decimal base.
        // More buckets, more efficient, but more memory space.
        int bucketNum = 10;

        int maxLen = 1;

        // sort out the length of max element
        while (max / bucketNum > 0) {
            maxLen++;
            max = max / bucketNum;
        }

        int[][] buckets = new int[bucketNum * 2][arr.length];

        // base is determined by allocated bucket number
        int base = bucketNum;

        for (int i = 0; i < maxLen; i++) {

            // keep track of the size of each bucket for later insertion
            int[] bktSize = new int[bucketNum * 2];

            // allocate the elements to corresponding buckets according to the ith digit counting from tail
            for (int j = 0; j < arr.length; j++) {

                // find out the jth digit counting from the tail
                // base=10, arr[j]=172; arr[j] % base=2, base/10=1; 2/1=2
                int bktId = (arr[j] % base) / (base / bucketNum) + bucketNum;

                // Even element arr[x] and arr[y] share same bucket, arr[x] will be put into the bucket first
                // if arr[x]'s (j-1)th digit is larger than arr[y]'s because of previous round sorting on (j-1)th digit.
                buckets[bktId][bktSize[bktId]] = arr[j];

                bktSize[bktId]++;
            }

            int count = 0;

            // collect the elements in order which are sorted by the ith digit
            for (int b = 0; b < buckets.length; b++) {
                for (int p = 0; p < bktSize[b]; p++) {
                    arr[count++] = buckets[b][p];
                }
            }

            base *= bucketNum;
        }
    }
}
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-07 09:23:30

results matching ""

    No results matching ""