如果数组有,则在O(n)中进行排序

Question

O(n)如果数组只包含k ? ?>0(k是常量)不同的元素,那么在最坏的情况下运行时可以对数组进行排序吗？

假设它需要恒定的时间来比较其中包含n元素的数组.

首先,我想了解任务,他们想要什么？我理解这个假设.但是k ? ?>0(k是一个常数)不同的元素究竟是什么意思呢？

这是否意味着我们得到了一个数组,它的大小是k因为它说?>0数组大小不能0？那是对的吗？如果是这样,我不太明白为什么他们不只是用n元素代替数组而不是它.

无论如何,这就是我理解它的方式,我会说在最坏的情况下运行时不可能对这个数组进行排序,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]

正如JF Sebastian和Steve314所提到的,执行此操作的alghoritms称为Radix sort(更广义的alghorithm)或Counting sort(不是"强",但更简单,可用于此示例).