5

在 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;
    }
}
4

1 回答 1

10

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

  1. 构建数组并随时排序。这可能非常慢，因为移动数组元素为新元素腾出空间所需的时间几乎肯定会支配排序时间。您应该期望这最多花​​费 Ω(n 2 ) 时间，其中 n 是您要放入数组中的元素数，而与使用的算法无关。即时进行插入排序将在此处花费预期的 O(n 2 ) 时间。

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

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

希望这可以帮助！

于 2012-08-21T22:18:40.543 回答