在Java中，快速排序比插入排序和选择排序慢得多？

Question

所以我正在复习我的算法知识并测试不同类型的运行时间，但我发现我的快速排序实现甚至比插入排序和选择排序还要慢得多。虽然这个算法看起来没有问题，而且在实践中它看起来与我在网上找到的其他几个实现完全相同。但它必须有什么地方出了问题，因为它的速度比O(N^2)排序慢500倍左右。对于一个随机化的10000元素数组的3个（深度）副本，计时排序结果如下:

插入排序: (75355000 ns)

选择排序: (287367000 ns)

快速排序: (44609075000 ns)

以下是代码:

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类只是我为了在算法中使用而创建的一个虚拟类。它的构造函数中生成一个整数值，除此之外没有太多功能。

我已验证快速排序确实可以正确地对数组进行排序，只是速度比预期要慢得多。我尝试了不同的枢轴选择方法，也尝试了我能想到的一切。也许我离得太近了，看不清问题所在，但是否有人可以告诉我是什么原因导致了我的算法效率低下？

- user2725525

Answer 1

在while循环完成后，应该递归地对数组的每个部分进行快速排序，而不是在每次while循环中进行。

- Louis Wasserman

---

这完全正确。天啊，谢谢您先生！我离它太近了，没看到。新的运行时间是（9411000纳秒）。 - user2725525