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

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

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

10^3和10^4都很好，但一旦我得到10^5的值，它只会对随机的、少数唯一的和随机的列表进行排序，但在对几乎排序和排序的列表进行分类时会出现堆栈溢出错误。

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

此外，我发现问题不太可能只是因为算法出于某种原因，必须在一个几乎排序和排序的列表中通过递归调用数组部分的分区，而不是其他列表类型，因为它可以对具有10^7值的随机列表进行排序，这将比具有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:

我已经用下面的代码替换了基本的递归调用，以便按照EJB的建议只调用两个分区中最小的一个，但它仍然没有解决这个问题。

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