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

Question

在Java中,更快的是:创建,填充然后对下面的一组int进行排序

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. 将数字递增地添加到优先级队列,然后从优先级队列中取出所有元素.根据您实现优先级队列的方式,这可能非常快.例如,在这里使用二进制堆将导致此过程花费O(n log n)时间,并且使用van Emde Boas树将花费O(n lg lg U)时间,其中U是您存储的最大数字.也就是说,这里的常数因素可能会使这种方法比仅对值进行排序更慢.

希望这可以帮助!