java - Quicksort - 排序数组较慢？

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，未排序数组需要 20 毫秒，排序数组需要 30 毫秒。这是为什么？

Answer 1

到目前为止我能说的最好的是你应该仔细检查你的时间安排。一般来说，像这样的分析应该作为多次运行的平均值来完成。我根据您的代码制作了一个测试类并得到了这些结果:

这是使用 System.nanoTime() 作为我的分析工具完成的。没什么特别的。

编辑: Here's a link到我写的分析类。它以类似 CSV 的格式输出结果，因此我可以在电子表格程序中制作图表。