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

Question

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

Answer 1

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

1. 构建数组并随时排序。这可能会非常慢，因为移动数组元素为新元素腾出空间所需的时间几乎肯定会占据排序时间。您应该预计这最多需要 Ω(n²) 时间，其中 n 是您要放入数组的元素数，无论使用何种算法。此处即时执行插入排序将花费预期的 O(n²) 时间。

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

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

希望这对您有所帮助!