十大经典排序算法-基数排序

编程算法

发布日期: 2020-12-03

文章字数: 603

阅读时长: 2 分

前言

本文重点讲解十大经典排序算法的基数排序

要点

基数排序（Radix Sort）属于分配式排序算法。
在计算机科学中，基数排序是一种非比较的整数排序算法，它通过用分享相同重要的位置和值方法分类得来的整数键来对数据进行排序。
该排序需要位置表示法，但是由于整数可以表示字符串(例如名称或日期) 和特殊格式化的浮点数，基数排序的对象可以不限于整数。
基数排序可以追溯到1887年赫尔曼·霍勒里斯在制表机上的工作。

代码实现

以下代码由java实现

public class RadixSort {

    /**
     * 基数排序
     * @param arr
     * @return
     */
    public static int[] sort(int[] arr) {
        if (arr.length <= 0) {
            return null;
        }
        int maxLenght = getMaxLenght(arr);
        // 初始长度
        int initialLenght = 10;
        // 初始化位数
        int initialDigit = 1;
        for (int i = 0; i < maxLenght; i++, initialDigit *= 10) {
            // 第一维表示排序对应的位数 initialLenght * 2 为了防止有负数情况 0-9 为负数 10-19 为正数
            int[][] counterArr = new int[initialLenght * 2][0];
            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] / initialDigit) % initialLenght) + initialLenght;
                // 扩容
                counterArr[bucket] = Arrays.copyOf(counterArr[bucket], counterArr[bucket].length + 1);
                // 当前桶位置赋值
                counterArr[bucket][counterArr[bucket].length - 1] = arr[j];
            }
            int o = 0;
            for (int[] bucket : counterArr) {
                for (int num : bucket) {
                    arr[o++] = num;
                }
            }
        }
        return arr;
    }

    /**
     * 获取最高位数
     */
    public static int getMaxLenght(int[] arr) {
        int max = 0;
        for (int num : arr) {
            if (max < num) {
                max = num;
            }
        }
        if (max == 0) {
            return 1;
        }
        int lenght = 0;
        for (; max != 0; max /= 10) {
            lenght++;
        }
        return lenght;
    }

    public static void main(String[] args) {
        int[] arr = {9, 5, 3, 6, 8, 1, 2, 3, 11, 52, 32, 11, 23, -9, -5};
        System.out.println(Arrays.toString(sort(arr)));
    }
}