为什么这种快速排序会导致在几乎排序的列表和排序的列表上出现堆栈溢出？

Question

我目前正在用Java编写一种快速排序算法，以对整数的随机数组进行排序，然后使用System.nanoTime（）对它们进行计时。这些数组的大小是10的幂，从10
^ 3到10 ^
7结束。此外，随机列表具有不同的属性。我正在对纯随机列表进行排序，具有一些相同值的列表（fewUnique），反向排序的列表，已排序的列表和几乎已排序的列表。

排序有效。它对数组进行递归快速排序，直到需要对数组中的30个或更少的元素进行排序，在这种情况下，它将执行插入排序。

对于10 ^ 3和10 ^ 4来说一切都很好，但是一旦我获得10 ^
5的值，它只会对随机，很少的唯一和随机列表进行排序，但是在对几乎排序和排序的列表进行排序时会产生堆栈溢出错误。

我不认为问题在于列表的生成方式，因为堆栈溢出发生在排序算法内（编译器引用的行是findPivot（）方法中的第一行）。同样，它在崩溃前通常会在1到6个列表之间排序。因此，算法本身必须以某种方式与几乎已排序和已排序的列表进行交互。同样，生成反向列表涉及调用代码以创建排序列表（然后反向）。

另外，我发现问题不太可能是由于某种原因，算法必须通过递归在几乎排序和排序的列表中而不是其他列表类型，通过递归调用数组部分的划分，因为它可以对具有10 ^
5个值的随机列表进行排序，这比具有10 ^ 5个值的几乎已排序的列表需要更多的分区。

我意识到这一定与这些列表类型如何与我的快速排序的递归交互有关，但是如果有人可以阐明它，那就太好了。我已经将代码完整地放入了快速排序算法中，并在下面将它们放入了随机列表生成器中。

快速排序算法

/**
 * Performs a quick sort given the indexes of the bounds of an integer array
 * @param arr The array to be sorted
 * @param highE The index of the upper element
 * @param lowE The index of the lower element
 */
public static void quickSort(int[] arr, int highE, int lowE)
{       
    //Only perform an action if arr.length > 30, otherwise insertion sort [recursive base case])
    if (lowE + 29 < highE)
    {
        //Get the element and then value of the pivot
        int pivotE = findPivot(arr, highE, lowE);
        int pivotVal = arr[pivotE], storeE = lowE;

        //Swap the pivot and the last value.
        swapElements(arr, pivotE, highE);

        //For each element in the selection that is not the pivot, check to see if it is lower than the pivot and if so, move it to the leftmost untouched element.
        for (int i = lowE; i < highE; i++)
        {
            if (arr[i] < pivotVal)
            {
                swapElements(arr, storeE, i);

                //Increment storeE so that the element that is being switched moves to the right location
                storeE++;
            }
        }

        //Finally swap the pivot into its proper position and recrusively call quickSort on the lesser and greater portions of the array
        swapElements(arr, storeE, highE);                   
        //Lesser
        quickSort(arr, storeE - 1, lowE);
        //Greater
        quickSort(arr, highE, storeE + 1);
    }
    else
    {
        insertSort(arr, highE, lowE);
    }
}




/**
 * Finds the pivot element
 * @param arr The array to be sorted
 * @param highE The index of the top element
 * @param lowE The index of the bottom element
 * @return The index of the pivot.
 */
public static int findPivot(int[] arr, int highE, int lowE)
{
    //Finds the middle element
    int mid = (int) Math.floor(lowE + (highE - lowE) / 2);

    //Returns the value of the median of the first, middle and last elements in the array.
    if ((arr[lowE] >= arr[mid]) && (arr[lowE] >= arr[highE])) 
    {
        if (arr[mid] > arr[highE]) {return mid;}
        else {return highE;}
    }
    else if ((arr[mid] >= arr[lowE]) && (arr[mid] >= arr[highE])) 
    {
        if (arr[lowE] > arr[highE]) {return lowE;}
        else {return highE;}
    }
    else 
    {
        if (arr[lowE] > arr[mid]) {return lowE;}
    }

    return mid;
}




/**
 *Performs an insertion sort on part of an array
 * @param arr The array to be sorted.
 * @param highE The index of the top element.
 * @param lowE The index of the low element.
 */
public static void insertSort(int[] arr, int highE, int lowE)
{
    //Sorts elements lowE to i in array, with i being gradually incremented.
    for (int i = lowE + 1; i <= highE; i++)
    {
        for (int j = i; j > lowE; j--)
        {
            if (arr[j] < arr[j - 1])
            {
                swapElements(arr, j, j-1);
            }
            else {break;}
        }
    }
}

随机列表生成器

/**
 * Creates a random list
 * @param arr The array to place the list inside of
 */
public static void randomList(int[] arr)
{
    //Places a random number at each element of the array

    for (int i = 0; i < arr.length; i++)
    {
        arr[i] = (int) Math.floor(Math.random() * RAND_MAX);
    }
}




/**
 * Creates a nearly sorted list of random numbers
 * @param arr the array to place the list inside of
 */
public static void nearSortList(int[] arr)
{
    //Creates a sorted list in arr
    sortList(arr);



    int swaps = (int) (Math.ceil(Math.pow((Math.log(arr.length)), 2.0)));

    //The two values to be switched each time
    int a, b;

    //Performs a number of swaps equal to swaps [log(N) ^ 2] rounded up, with numbers switched no more than ln(N) places away
    for (int i = 0; i < swaps; i++)
    {
        a = (int) Math.floor(Math.random() * arr.length);

        b = (int) (a + Math.random() * 2 * Math.log(arr.length) - Math.log(arr.length));

        //Accounts for cases in which b is either greater or smaller than the array bounds
        if (b < 0)
        {
            b = -b;
        }
        else if (b >= arr.length)
        {
            b = -1 * (arr.length - b);
        }

        swapElements(arr, a, b);
    }
}




/**
 * Creates a random list with many unique values in
 * @param arr the array to place the list inside of
 */
public static void fewUniqueList(int[] arr)
{
    int[] smallArr = new int[(int) Math.floor(Math.pow(arr.length, 9.0 / 10.0))];


    //Creates a smaller array of random values
    randomList(smallArr);



    //Fills the larger list up with values from the smaller list, ensuring aproximately N / N ^ (9/10) instances of each number in the array and ensuring, at most, there are N ^ (9/10) (rounded down) unique values in the large array
    for (int i = 0; i < arr.length; i++)
    {
        arr[i] = smallArr[(int) Math.floor(Math.random() * smallArr.length)];
    }
}




/**
 * Creates a reversed list of random numbers
 * @param arr the array to place the list inside of
 */
public static void reversedList(int[] arr)
{
    //Creates a sorted list in arr
    sortList(arr);




    //Switches each ith elements with its mirror on the other end of the array until the value of i reaches the middle of the array
    for (int i = 0; i < (int) (arr.length / 2.0); i++)
    {
        swapElements(arr, i, arr.length - 1 - i);
    }
}




/**
 * Creates a sorted list of random numbers using a merge sort
 * @param arr the array to place the list inside of
 */
public static void sortList(int[] arr)
{
    //Creates a random list in arr
    randomList(arr);

    Arrays.sort(arr);
}

编辑： [已取消]

编辑2：

我已将以下基本递归调用替换为以下代码，以便仅按EJP建议使用两个分区中的最小分区，并且仍无法解决问题。

if (storeE - 1 - lowE < highE - storeE + 1)
{
    //Lesser
    quickSort(arr, storeE - 1, lowE);
    //Greater
    quickSort(arr, highE, storeE + 1);
}
else
{
    //Greater
    quickSort(arr, highE, storeE + 1);
    //Lesser
    quickSort(arr, storeE - 1, lowE);
}

编辑3：

好的，现在很明显，递归深度远大于我为几乎已排序和已排序列表指定的深度。但是现在我需要弄清楚为什么会这样，为什么随机列表的深度为10 ^
7的值只有28，而几乎已排序和已排序的列表的深度却超过3000

Answer 1

对于随机数组，您可以划分出大量数据。
但是对于一个（几乎）排序的数组，您通常一次要划分一个元素。

因此，对于排序后的数组，您的堆栈大小最终将与该数组的大小相同，而对于一个随机数组，则更可能是该大小的对数。

因此，即使随机数组比几乎排序的数组大得多，较小的数组引发异常也就不足为奇了，而较大的数组则不会。

修改您的代码

在修复方面，如EJP所指出的那样，您应该首先进行较小的分区以限制堆栈的增长。但这本身不能解决问题，因为Java不支持尾部调用优化（嗯，据我所知，它对于实现是可选的）。

一个相当简单的解决方法是将您的函数放入while循环中，本质上是对尾调用优化进行硬编码。

为了更好地理解我的意思：

public static void quickSort(int[] arr, int highE, int lowE)
{
    while (true)
    {
        if (lowE + 29 < highE)
        {
            ...
            quickSort(arr, storeE - 1, lowE);

            // not doing this any more
            //quickSort(arr, highE, storeE + 1);

            // instead, simply set the parameters to their new values
            // highE = highE;
            lowE = storeE + 1;
        }
        else
        {
            insertSort(arr, highE, lowE);
            return;
        }
    }
}

好了，既然您已经有了基本的想法，这看起来会更好（在功能上等同于上面，更加简洁）：

public static void quickSort(int[] arr, int highE, int lowE)
{
    while (lowE + 29 < highE)
    {
        ...
        quickSort(arr, storeE - 1, lowE);
        lowE = storeE + 1;
    }
    insertSort(arr, highE, lowE);
}

当然，这实际上并不是先做较小的事情，但我将留给您去弄清楚（似乎您已经对如何做到这一点有了一个很清楚的想法）。

如何运作

对于一些虚构的价值…

您当前的代码执行此操作：（缩进指示该函数调用内发生了什么-因此增加缩进意味着递归）

quickSort(arr, 100, 0)
   quickSort(arr, 49, 0)
      quickSort(arr, 24, 0)
         insertion sort
      quickSort(arr, 49, 26)
         insertion sort
   quickSort(arr, 100, 51)
      quickSort(arr, 76, 0)
         insertion sort
      quickSort(arr, 100, 74)
         insertion sort

修改后的代码将执行以下操作：

quickSort(arr, 100, 0)
   quickSort(arr, 49, 0)
      quickSort(arr, 24, 0)
         break out of the while loop
         insertion sort
   lowE = 26
   break out of the while loop
      insertion sort
lowE = 51
run another iteration of the while-loop
    quickSort(arr, 76, 0)
      break out of the while loop
      insertion sort
lowE = 74
break out of the while loop
   insertion sort

增加堆栈大小

不知道您是否考虑过这个问题，或者它是否可以与您的参数一起使用，但是您始终可以考虑使用-Xss命令行参数简单地增加堆栈大小。