形成和排序正整数数组的最快策略

在 Java 中，什么更快：创建、填充然后排序一个整数数组，如下所示

int[] a = int[1000];
for (int i = 0; i < a.length; i++) {
    // not sure about the syntax
    a[i] = Maths.rand(1, 500) // generate some random positive number less than 500
}
a.sort(); // (which algorithm is best?)

或动态插入排序

int[] a = int[1000];
for (int i = 0; i < a.length; i++) {
    // not sure about the syntax
    int v = Maths.rand(1, 500) // generate some random positive number less than 500
    int p = findPosition(a, v); // where to insert
    if (a[p] == 0) a[p] = v;
    else {
        shift a by 1 to the right
        a[p] = v;
    }
}

有很多方法可以做到这一点：

1. Build the array and sort as you go. This is likely to be very slow, since the time required to move array elements over to make space for the new element will almost certainly dominate the sorting time. You should expect this to take at best Ω(n²) time, where n is the number of elements that you want to put into the array, regardless of the algorithm used. Doing insertion sort on-the-fly will take expected O(n²) time here.

2. 构建未排序的数组，然后对其进行排序。如果您使用良好的排序算法，这可能会非常快，例如快速排序 or 基数排序。您应该期望这需要 O(n log n) 时间（对于快速排序）或 O(n lg U) 时间（对于基数排序），其中 n 是值的数量，U 是最大值。

3. 将数字逐渐添加到优先队列，然后将所有元素从优先级队列中出列。根据您实现优先级队列的方式，这可能会非常快。例如，使用二叉堆这里会导致这个过程花费 O(n log n) 时间，并且使用范恩德博阿斯树需要 O(n lg lg U) 时间，其中 U 是您存储的最大数字。也就是说，这里的常数因素可能会使这种方法比仅仅对值进行排序慢。

希望这可以帮助！