Java版基数排序

分析&回答

动态演示 -> 跳转到博客查看

实现代码

/**
 * 基数排序
 * <p>
 * 实现基数排序 LSD-从最低位开始排 MSD-从最高位开始排
 * 取得数组中的最大数，并取得位数;
 * ARR为原始数组，从最低位开始取每个位组成基数数组;
 * 对基数进行计数排序（利用计数排序适用于小范围数的特点）;
 * @param data
 */
public static void radixSort(int[] data) {
    int maxBin = maxBin(data);
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    for (int i = 0; i < 10; i++) {
        list.add(new ArrayList<Integer>());
    }
    for (int i = 0, factor = 1; i < maxBin; factor *= 10, i++) {
        for (int j = 0; j < data.length; j++) {
            list.get((data[j] / factor) % 10).add(data[j]);
        }
        for (int j = 0, k = 0; j < list.size(); j++) {
            while (!list.get(j).isEmpty()) {
                data[k] = list.get(j).get(0);
                list.get(j).remove(0);
                k++;
            }
        }
    }
}

//计算数组里元素的最大位数
public static int maxBin(int[] data) {
    int maxLen = 0;
    for (int i = 0; i < data.length; i++) {
        int size = Integer.toString(data[i]).length();
        maxLen = size > maxLen ? size : maxLen;
    }
    return maxLen;
}

性能分析

• 稳定 
• 平均时间复杂度O(n + k)
• 空间复杂度O(n + k)

反思&扩展

Java版常用排序算法复杂度