自定义排序算法性能(与Arrays.sort()和parallelSort()相比)

Question

我用Java实现了一个基本的排序算法，并将其性能与本机方法(Arrays.sort((和Arrays.sparallelSort(((进行了比较。程序如下。

public static void main(String[] args) {
// Randomly populate array
int[] array = new int[999999];
for (int i = 0; i < 999999; i++)
array[i] = (int)Math.ceil(Math.random() * 100);
long start, end;
start = System.currentTimeMillis();
Arrays.sort(array);
end = System.currentTimeMillis();
System.out.println("======= Arrays.sort: done in " + (end - start) + " ms ========");
start = System.currentTimeMillis();
Arrays.parallelSort(array);
end = System.currentTimeMillis();
System.out.println("======= Arrays.parallelSort: done in " + (end - start) + " ms ========");
start = System.currentTimeMillis();
orderArray(array);
end = System.currentTimeMillis();
System.out.println("======= My way: done in " + (end - start) + " ms ========");
}

private static int[] orderArray(int[] arrayToOrder) {
for (int i = 1; i < arrayToOrder.length; i++) {
int currentElementIndex = i;
while (currentElementIndex > 0 && arrayToOrder[currentElementIndex] < arrayToOrder[currentElementIndex-1]) {
int temp = arrayToOrder[currentElementIndex];
arrayToOrder[currentElementIndex] = arrayToOrder[currentElementIndex-1];
arrayToOrder[currentElementIndex-1] = temp;
currentElementIndex--;
}
}
return arrayToOrder;
}

当我运行这个程序时，我的自定义算法在我的机器上始终优于本机查询几个数量级。这是我得到的一个有代表性的输出：

======= Arrays.sort: done in 67 ms ========
======= Arrays.parallelSort: done in 26 ms ========
======= My way: done in 4 ms ========

这独立于：

• 数组中的元素数(在我的示例中为999999(
• 执行排序的次数(我在for循环中尝试并迭代了大量(
• 数据类型(我尝试使用double数组而不是int，但没有发现任何区别(
• 我调用每个排序算法的顺序(不影响性能的总体差异(

显然，我的算法不可能比Java提供的算法更好。我只能想到两种可能的解释：

• 我衡量性能的方式有缺陷
• 我的算法太简单了，遗漏了一些角落的情况

我认为后者是真的，因为我使用了一种相当标准的Java性能测量方法(使用System.currentTimeMillis(((。然而，我已经广泛测试了我的算法，到目前为止还没有发现任何谬误-int有预定义的边界(Integer.MIN_VALUE和MAX_VALUE(，不能为null，我想不出任何可能的角落情况我没有涵盖。

我的算法的时间复杂性(O(n^2((和本机方法的(O(n-log(n(((，这显然会造成影响。然而，我再次相信我的复杂性已经足够了。。。

我能得到一个局外人的看法吗，这样我就知道如何改进我的算法了？

非常感谢，

克里斯。

Answer 1

您正在对一个数组进行适当的排序，但没有在每个踪迹之间重新打乱数组。这意味着您正在对最佳情况进行排序。在每次调用数组排序方法之间，您可以重新创建数组。

for (int i = 0; i < TEST_SIZE; i++)
array[i] = (int)Math.ceil(Math.random() * 100);

这样做之后，你会注意到你的算法大约慢了100倍。

也就是说，这并不是比较两种方法的最佳方式。对于每个不同的算法，您至少应该对相同的原始数组进行排序。您还应该对每个算法执行多次迭代，并对响应求平均值。一次试验的结果将是虚假的，作为一个好的比较是不可靠的。