面试算法:数组相对排序

2023-12-28 14:14:10

题目

计数排序是一种线性时间的整数排序算法。如果数组的长度为n,整数范围(数组中最大整数与最小整数的差值)为k,对于k远小于n的场景(如对某公司所有员工的年龄排序),那么计数排序的时间复杂度优于其他基于比较的排序算法(如归并排序、快速排序等)。

分析

计数排序的基本思想是先统计数组中每个整数在数组中出现的次数,然后按照从小到大的顺序将每个整数按照它出现的次数填到数组中。例如,如果输入整数数组[2,3,4,2,3,2,1],扫描一次整个数组就能知道数组中1出现了1次,2出现了3次,3出现了2次,4出现了1次,于是先后在数组中填入1个1、3个2、2个3及1个4,就可以得到排序后的数组[1,2,2,2,3,3,4]。

public class Test {
    public static void main(String[] args) {
        int[] nums = {2, 3, 4, 2, 3, 2, 1};
        int[] result = sortArray(nums);
        for (int item : result) {
            System.out.println(item);
        }
    }

    public static int[] sortArray(int[] nums) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }

        int[] counts = new int[max - min + 1];
        for (int num : nums) {
            counts[num - min]++;
        }

        int i = 0;
        for (int num = min; num <= max; num++) {
            while (counts[num - min] > 0) {
                nums[i++] = num;
                counts[num - min]--;
            }
        }

        return nums;
    }
}

文章来源:https://blog.csdn.net/GoGleTech/article/details/135266118
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。