所以我正在复习我的算法知识并测试不同类型的运行时,我发现我的快速排序实现甚至比插入和选择排序要慢得多。 该算法对我来说看起来是正确的,并且在实践中看起来与我在网上找到的其他几种实现相同。 但它一定是错误的,因为它比 O(N^2) 排序慢 500 倍。 对随机 10000 个元素数组的 3 个(深度)副本进行排序计时可得到:
插入排序: (75355000 ns)
选择顺序:(287367000 ns)
快速排序:(44609075000 纳秒)
代码如下:
public static void quickSort(Thing [] theThings, int left, int right) {
int i= left; int j = right;
int pivot = theThings[(int)(left + (right-left)*0.5)].getValue();
while (i <= j) {
while (theThings[i].getValue() < pivot)
i++;
while (theThings[j].getValue() > pivot)
j--;
if (i <= j) {
Thing temp = theThings[i];
theThings[i] = theThings[j];
theThings[j] = temp;
i++;
j--;
}
if (left < j)
quickSort(theThings, left, j);
if (right > i)
quickSort(theThings, i, right);
}
}
Thing 类只是我在算法中玩的假人。 它在构造函数中有一个由 Random 生成的整数值,而不是其他值。
我已经验证了快速排序确实对数组进行了正确排序 - 只是比应有的慢得多。 我尝试了不同的枢轴选择方法。 我已经尝试了我能想到的一切。 也许我离得太近了,看不到它,但谁能告诉我是什么在扼杀我的算法?
while
循环完成后递归以快速排序数组的每个部分,而不是每次都通过 while
循环。