java算法 -- 基数排序

基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机（Tabulation Machine）上的贡献[1]。

它是这样实现的：将所有待比较数值（正整数）统一为同样的数字长度，数字较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

import java.util.Arrays;

public class RadixSort {

    public int[] sort(int[] sourceArray) throws Exception {

        // 对 arr 进行拷贝，不改变参数内容

        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxDigit = getMaxDigit(arr);

        return radixSort(arr, maxDigit);

    }

    /**

     * 获取最高位数

     */

    private int getMaxDigit(int[] arr) {

        int maxValue = getMaxValue(arr);

        return getNumLenght(maxValue);

    }

    private int getMaxValue(int[] arr) {

        int maxValue = arr[0];

        for (int value : arr) {

            if (maxValue < value) {

                maxValue = value;

            }

        }

        return maxValue;

    }

    protected int getNumLenght(long num) {

        if (num == 0) {

            return 1;

        }

        int lenght = 0;

        for (long temp = num; temp != 0; temp /= 10) {

            lenght++;

        }

        return lenght;

    }

    private int[] radixSort(int[] arr, int maxDigit) {

        int mod = 10;

        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {

            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)

            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {

                int bucket = ((arr[j] % mod) / dev) + mod;

                counter[bucket] = arrayAppend(counter[bucket], arr[j]);

            }

            int pos = 0;

            for (int[] bucket : counter) {

                for (int value : bucket) {

                    arr[pos++] = value;

                }

            }

        }

        return arr;

    }

    /**

     * 自动扩容，并保存数据

     *

     * @param arr

     * @param value

     */

    private int[] arrayAppend(int[] arr, int value) {

        arr = Arrays.copyOf(arr, arr.length + 1);

        arr[arr.length - 1] = value;

        return arr;

    }

    public static void main(String[] args) {

        int[] array = {5, 7, 17, 3, 5, 22, 4, 15, 8, 6, 4, 1, 2};

        RadixSort radixSort = new RadixSort();

        try {

            int[] sortedArray = radixSort.sort(array);

            for (int i = 0; i < sortedArray.length; i++) {

                System.out.print(sortedArray[i] + "  ");

            }

        } catch (Exception e) {

            e.printStackTrace();

        }

    }

}

运行结果：

1 2 3 4 4 5 5 6 7 8 15 17 22

巴特西

java算法 -- 基数排序

最新文章

热门文章