Java版计数排序

分析&回答

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

实现代码

/**
 * 计数排序
 * <p>
 * 找出待排序的数组中最大和最小的元素;
 * 统计数组中每个值为我的元素出现的次数，存入数组Ç的第我项;
 * 对所有的计数累加（从ç中的第一个元素开始，每一项和前一项相加）;
 * 反向填充目标数组：将每个元素我放在新数组的第C（ⅰ）项，每放一个元素就将C（ⅰ）减去1。
 *
 * @param arr
 * @return
 */
public static int[] countingSort(int[] arr) {
    int minV = arr[0], maxV = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (minV > arr[i]) {
            minV = arr[i];
        }
        if (maxV < arr[i]) {
            maxV = arr[i];
        }
    }
    int gap = maxV - minV + 1;
    int[] countArr = new int[gap];
    for (int i = 0; i < arr.length; i++) {
        countArr[arr[i] - minV] += 1;
    }
    for (int i = 1; i < gap; i++) {
        countArr[i] += countArr[i - 1];
    }
    int[] result = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        /**
         * countArr[arr[i] - minV] - 1 当前arr[i]可以放的最右的位置,每放一次往前移一位
         */
        result[countArr[arr[i] - minV] - 1] = arr[i];
        countArr[arr[i] - minV] -= 1;
    }
    return result;
}

性能分析

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

反思&扩展

Java版常用排序算法复杂度

喵呜面试助手： 一站式解决面试问题，你可以搜索微信小程序 [喵呜面试助手] 或关注 [喵呜刷题] -> 面试助手 免费刷题。如有好的面试知识或技巧期待您的共享！