java - 如何优化java中的计数排序？

Question

学习编码并进行计数排序。但是在调试时，即使我注意到 N (N = maxValue-minValue) 的运行时复杂度。在调试器中，我注意到它实际上并不是最优的，可能会更好，因为有时某些步骤似乎是不必要的。

这是我的代码：

    public static void countingSort(int[] arr) {
    int low = Integer.MAX_VALUE, high = Integer.MIN_VALUE;

    for (int x : arr) {
        if (x < low) {
            low = x;
        }
        if (x > high) {
            high = x;
        }
    }
    
    System.out.println("L:" + low + "/H:" + high);
    int[] count = new int[high - low + 1];
    

    for (int x = 0; x<arr.length; x++) {
        count[arr[x] - low]++;
    }

    int countIndex = 0, arrIndex = 0;
    Arrays.fill(arr, 0);
   
    while (countIndex < count.length) {
        int currentVal = countIndex + low; //8

        for (int i = 0; i < count[countIndex]; i++) {
            arr[arrIndex++] = currentVal;
        }
        countIndex++;
    }

}

我在调试时注意到的是：

• 它有时在 while 循环中有步骤，实际上它并没有做任何有用的事情来检查 for 循环和增加 countIndex 的值。
• 我的代码中 currentVal 的值也可能会被优化，但我不知道如何。

（我做了 Arrays.fill() 以获得更轻松的生活调试）。

有人对优化有任何想法吗？

这可能是一个愚蠢的问题，但似乎可以跳过步骤。我尝试制作一些额外的索引，但无济于事。是否可以将其推低到 N（运行时复杂度）= arr.length？

提前致谢！

标签： javaarrayssortingintegercounting-sort