arrays - 如果数组有，则可以在 O(n) 中排序

Question

如果数组仅包含k ∈ ℕ>0(k 是常量)个不同的元素，则可以在最坏情况下运行时间 O(n) 对数组进行排序？

假设需要常数时间来比较其中包含 n 元素的数组。

首先我想了解任务，他们想要什么？我理解这个假设。但是 k ∈ ℕ>0(k 是常数)不同元素的确切含义是什么？

这是否意味着我们得到了一个数组并且它的大小是 k 并且因为它说 ℕ>0 数组大小不能是 0?那是对的吗？如果是这样，我不太明白为什么他们不直接说 array with n elements 而不是它。

无论如何，这就是我的理解方式，我会说在最坏的运行时间 O(n) 中不可能对这个数组进行排序，因为如果我们看一下桶排序/基数排序等. 它可以在 O(n*logn) 中完成。

Answer 1

如果您知道这些值，则可以通过将数字放入“桶”来对数组进行排序。对于每个值，您创建存储桶，并在遍历该存储桶时将数字添加到该存储桶。你用所有的数字，而且只有一次，因此它在 O(n)

中完成

---

例如只有0-9的数字，你可以按如下排序

public class SortInBucket {
    public static void main(String[] args) {
        int[] x = {0,5,1,1,1,1,7,9,3,2,1,2,5,6};
        System.out.println("Result of sorting: " + Arrays.toString(sortInBuckets(x)));
    }

    public static int[] sortInBuckets(int[] arr) {
        List<List<Integer>> sortedNumbers = new ArrayList<>();
        int[] sortedArr = new int[arr.length];
        // create buckets 0 - 9
        for (int i = 0; i < 10; i++) {
            sortedNumbers.add(new ArrayList<>());
        }

        for (int i = 0; i < arr.length; i++) {
            System.out.println("Found number " + arr[i] + " puting index " + i + " to bucket " + arr[i]);
            sortedNumbers.get(arr[i]).add(i);
            System.out.println("Bucket " + arr[i] + " is having " +sortedNumbers.get(arr[i]).size() + " numbers now." );
        }

        System.out.println();
        System.out.println("The sortedNumbers (list with buckets) looks like following: " +sortedNumbers );

        //just going through buckets and adding its numbers to sortedArr
        int sortedIndex = 0;
        for (List<Integer> bucket : sortedNumbers){
            for (Integer num : bucket){
                sortedArr[sortedIndex] = arr[num];
                sortedIndex++;
            }
        }

        return sortedArr;
    }
}

上面的代码有这样的输出

Found number 0 puting index 0 to bucket 0
Bucket 0 is having 1 numbers now.
Found number 5 puting index 1 to bucket 5
Bucket 5 is having 1 numbers now.
Found number 1 puting index 2 to bucket 1
Bucket 1 is having 1 numbers now.
Found number 1 puting index 3 to bucket 1
Bucket 1 is having 2 numbers now.
Found number 1 puting index 4 to bucket 1
Bucket 1 is having 3 numbers now.
Found number 1 puting index 5 to bucket 1
Bucket 1 is having 4 numbers now.
Found number 7 puting index 6 to bucket 7
Bucket 7 is having 1 numbers now.
Found number 9 puting index 7 to bucket 9
Bucket 9 is having 1 numbers now.
Found number 3 puting index 8 to bucket 3
Bucket 3 is having 1 numbers now.
Found number 2 puting index 9 to bucket 2
Bucket 2 is having 1 numbers now.
Found number 1 puting index 10 to bucket 1
Bucket 1 is having 5 numbers now.
Found number 2 puting index 11 to bucket 2
Bucket 2 is having 2 numbers now.
Found number 5 puting index 12 to bucket 5
Bucket 5 is having 2 numbers now.
Found number 6 puting index 13 to bucket 6
Bucket 6 is having 1 numbers now.

The sortedNumbers (list with buckets) looks like following: [[0], [2, 3, 4, 5, 10], [9, 11], [8], [], [1, 12], [13], [6], [], [7]]
Result of sorting: [0, 1, 1, 1, 1, 1, 2, 2, 3, 5, 5, 6, 7, 9]

---

正如 J.F. Sebastian 和 Steve314 所提到的，执行此操作的算法称为基数排序(更通用的算法)或计数排序(不是“强”，但更简单，可用于此示例)。