最快的形成和排序正整数数组策略(Fastest strategy to form and sort

在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 ^2）时间，其中n是要放入数组元素的数量，而不管使用的算法。 排序做插入上即时将采取这里有望为O（n ^2）时间。

2. 建立未排序的数组，然后对其进行排序。 这可能会，如果你使用一个很好的排序算法，如以极快快速排序或基数排序 。 你应该想到这需要为O（n log n）的时间（快速排序），或者为O（n LG U）时间（基数排序），其中n是值的数目和U是最大的价值。

3. 逐步增加的数字，以一个优先级队列 ，然后从出列优先级队列中的所有元素。 这取决于你如何实现优先级队列，这可能是非常快的。 例如，使用二进制堆在这里会使这个过程中采取为O（n log n）的时间，并使用面包车昂德博阿斯树将采取为O（n LG LG U）时，其中U是你存储数量最多。 也就是说，这里的持续性因素可能会使得这种方法不只是排序值慢。

希望这可以帮助！

文章来源: Fastest strategy to form and sort an array of positive integers