QuickSort 因项目较少而失败，而在降序排序良好的数组上处理更多项目

Question

我写了一个 quickSort 方法，我用它来尝试对已经几乎排序的数组进行排序 - 反向排序。所以 quickSort 尝试按升序对它进行排序，而数组已经几乎按降序排序：

    private static void switchPlaces(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void quickSort(int[] a, int low, int high)  {
        int i = low;
        int j = high;
        int pivot = a[low];

        while (i <= j) {

            while (a[i] < pivot) {
                i++;
            }
            while (a[j] > pivot) {
                j--;
            }

            if (i <= j) {
                switchPlaces(a, i, j);
                i++;
                j--;
            }
        }

        if (low < j) {
            quickSort(a, low, j);
        }
        if (i < high) {
            quickSort(a, i, high);
        }
    }

我使用我的自定义方法生成这样一个数组 - 20% 的元素比它们之前的元素大。

然而，当我在 100,000 长数组上调用 qucsort 时，出现计算器错误：

int[] a = generateArray(100_000);

quickSort(a, 0 , a.length - 1); //Whosebug

1,000,000 长数组不会发生的事情：

int[] a = generateArray(1_000_000);

quickSort(a, 0 , a.length - 1); //quickly works: all elements inside a are sorted

在 1_000_000 排序后：

a 在 100_000 排序的开头：

a 在 1_000_000 排序的开头：

我不明白为什么它适用于较大的数组但不适用于较小的数组。

编辑:

public static void main(String[] args) {
        int[] a = generateArray(1_000_000);
        quickSort(a, 0 , a.length - 1);
        System.out.println();
    }

    public static int[] generateArray(int N) {
        Random random = new Random();
        int max = 1_000_000;
        int[] result = new int[N];

        int prev =  max - random.nextInt(100);
        result[0] = prev;
        for (int i = 1; i < N; i++) {
            boolean toSort = random.nextInt(10) < 8;

            int number;
            if (toSort) {
                number = Math.max(0, prev - random(5, 10));
                prev = number;
            } else {
                number = prev + random(5, 10);
            }

            result[i] = number;
        }

        return result;
    }

Answer 1

我也可以转载。自然地，你有一个 WhosebugError 因为 quickSort(...); 被递归调用的次数与数组中元素的数量没有直接关系。尽管如此，数组越大，方法 quickSort(...); 被递归调用的可能性就越大。但是，它与元素在数组上的分布方式有关。

例如：

  int[] a = new int [100_000];
    for(int i = 0; i < a.length; i++)
        a[i] = i;

    quickSort(a, 0 , a.length - 1); //Whosebug

将产生 java.lang.WhosebugError 而

int[] a = new int [100_000];
for(int i = 0; i < a.length; i+=2) {
    a[i] = i;
    a[i + 1] = 0;
}

quickSort(a, 0 , a.length - 1);

不会，即使对于 new int [1000000];.

的数组也是如此

Answer 2

不要使用范围内的第一个值作为枢轴，使用中间值。

如果数据已经完全排序，结果是quickSort(a, start, end)递归调用quickSort(a, start + 1, end)，所以你得到一个递归调用堆栈深度等于数组大小，这肯定会导致 WhosebugError 在更大的数据集上。

为了说明，我们可以添加一个print语句来在方法被调用时显示start和end。为了提供更多帮助，我们可以使打印语句使用缩进显示调用深度。如果我们然后例如排序数组 {0,1,2,3,4,5,6,7,8,9}，我们得到 (maxCallDepth = 9):

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
0, 9
 1, 9
  2, 9
   3, 9
    4, 9
     5, 9
      6, 9
       7, 9
        8, 9

类似地，如果数据是反向排序的，例如我们对数组 {9,8,7,6,5,4,3,2,1,0} 进行排序，我们还得到一个非常深的调用堆栈 (maxCallDepth = 9):

{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
0, 9
 0, 8
  1, 8
   1, 7
    2, 7
     2, 6
      3, 6
       3, 5
        4, 5

相比之下，如果我们将枢轴更改为范围的中间值，则最大调用堆栈深度（即最大缩进）会大大减少（maxCallDepth = 3, 在两者上):

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
0, 9
 0, 3
  2, 3
 5, 9
  5, 6
  8, 9

{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
0, 9
 0, 4
  0, 1
  3, 4
 5, 9
  5, 6
  8, 9

结论：改代码使用：

int pivot = a[(start + end) / 2];

Answer 3

我对你的算法（以及我的）进行了一些分析，它们都表现出相同的行为。我写了自己的数据生成器，一切正常。这意味着您对较低数组的数据分布是这样的，它没有针对所选的主元进行有效排序。

所以我放入了一些计数器来计算递归过程中达到的最大深度。对于 1_000_000 值数组，深度在 100 以内（低于 1000）。对于 100_000 范围值，深度接近 15000 并导致堆栈溢出。原因是不同大小的数组的数据分布。

我一直使用的算法是这里建议使用最左边的值作为基准的算法。

WikiPedia 中的这段摘录讨论了枢轴的选择。

Choice of pivot

In the very early versions of quicksort, the leftmost element of the partition would often be chosen as the pivot element. Unfortunately, this causes worst-case behavior on already sorted arrays, which is a rather common use-case. The problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot (as recommended by Sedgewick).[18] This "median-of-three" rule counters the case of sorted (or reverse-sorted) input, and gives a better estimate of the optimal pivot (the true median) than selecting any single element, when no information about the ordering of the input is known.

通过将枢轴更改为 arr[(p + r)/2]，一切都变得更好了。这也是 Andreas answer

中的最终建议

QuickSort 因项目较少而失败，而在降序排序良好的数组上处理更多项目

QuickSort fails with less items and works with more items on descending well sorted array

java

arrays

sorting

quicksort