快速排序 - 在已排序的数组上速度较慢？

Question

我正在尝试一些排序算法。

private static void quicksort(int[] list, int low, int high){
    int pivot = list[low + (high-low)/2];
    int i = low; 
    int j = high;
    while (i <= j) {
      while (list[i] < pivot) {
        i++;
      }
      while (list[j] > pivot) {
        j--;
      }
      if (i <= j) {
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
        i++;
        j--;
      }
    }
    if (low < j){
        quicksort(list, low, j);
    }
    if (i < high){
        quicksort(list, i, high);
    }

}

这段代码运行在两个整数数组上，每个数组有x个条目（假设为10亿）。第一个数组已排序，第二个数组是对数组1的排列，其中n对随机选择并交换。

我选择中间元素作为枢轴，因此它应该对于已排序的情况是最优的，对吧？

我正在测量算法对每个数组进行排序所需的时间，并计算出发生多少次交换和递归步骤。正如预期的那样，这些值在对带有随机排列的数组2进行排序时都更高。

但是：直到我达到较高数量的排列之前，算法仍需要较长的时间来处理已排序的数组。当n=10000时，我得到未排序数组的20ms和已排序数组的30ms。为什么会这样？

- user3601374

---

在Java中衡量效率是一个棘手的问题，程序的速度取决于许多因素。 - Reinstate Monica

有时候，你对某段代码进行基准测试的方式会影响它的优化效果。我会多次运行测试。 - Peter Lawrey

请查看此帖子：https://dev59.com/fnE95IYBdhLWcg3wMrAB - Kostas Kryptos

我想知道为什么有这么多人错误地谈论快速排序的最坏情况是已经排序好的序列。他在代码中将中间元素作为枢轴，因此对于他的代码来说，排序并不是最坏情况（实际上它应该接近最优）。 - AliciaBytes

我的第一猜测是你只是在调用周围包裹了一些 System.currentTimeMillis() 或者 System.nanoTime() 的方法，并计算时间差。如果确实是这样的话：Java 有一个即时编译器（JIT），要测量特定方法的性能非常困难。同时请参阅 https://dev59.com/hHRB5IYBdhLWcg3wz6UK。 - Marco13

Answer 1

我能提供的最好建议是您需要仔细检查您的时间设置。通常情况下，像这样的性能分析应该是对多次运行的平均值。我基于您的代码编写了一个测试类，并得到了以下结果：

这是使用System.nanoTime()作为性能分析工具完成的。没有什么花哨的东西。 编辑：这里是我编写的性能分析类的链接。它以类似CSV的格式输出结果，因此我可以在电子表格程序中制作图表。

- wrongu

---

好的，非常感谢你。我认为第一次对数组进行排序需要更多时间。也许这个差异来自于Java需要创建对象之类的东西。如果我在更大的样本上运行代码，我会得到和你一样的结果。 - user3601374

Answer 2

快速排序算法的最坏情况是数组已经排序或几乎排序。这很可能是为什么对已经排序的数组进行排序需要更长时间的原因。

- Jakkra

---

只有在我选择左侧或右侧的元素作为枢轴时，才会出现这种情况，对吗？ - user3601374

@user3601374 是的，你选择中间元素作为枢轴，因此排序实际上应该接近最优。 - AliciaBytes