通用快速排序导致 StackOverflowError

Question

这是我正在学习的 Java 书中的一道练习题。基本上，目标是使用 compareTo 按升序对泛型元素数组进行排序。

我正在尝试使用 QuickSort 来完成。这是我的代码：

public static <T extends Comparable<? super T>>
void sort (T[] arr)
{
    // If arr is null, empty,
    // or only has 1 element,
    // it is already sorted

    if (arr == null || arr.length == 0
            || arr.length == 1)
        return;

    // Call overloaded sort method

    sort(arr, 0, arr.length - 1);
}

// HELPER METHOD FOR SORT METHOD

public static <T extends Comparable<? super T>>
void sort(T[] arr, int left, int right)
{

    // To be used while sorting

    int i = left;
    int j = right;

    // Check if left and
    // right indices are out
    // of order. If they are,
    // nothing can be done

    if (right <= left)
        return;

    // Middle element used
    // as pivot

    T pivot = arr[(left + (right - left)) / 2];

    // temp will be used
    // to swap elements later

    T temp;

    // QuickSort algorithm

    while (i <= j)
    {
        // Look for values on
        // the left greater than
        // the pivot and values
        // on the right smaller
        // than the pivot

        // When you find both, swap them

        while (arr[i].compareTo(pivot) < 0)
        {
            i++;
        }

        while (arr[j].compareTo(pivot) > 0)
        {
            j--;
        }

        // Check that i hasn't
        // passed j already

        if (i <= j)
        {

            // Swap the items

            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;

            // Move both indices
            // to their next position

            i++;
            j--;
        }
    }

    // Recursive calls to the
    // sort method

    if (left < j)
        sort(arr, left, j);
    if (i < right)
        sort(arr, i, right);
}

问题是，当我使用以下数组进行测试时：

String[] wordArray = {"Droplet", "Blueberry", "Elephant",
            "Fate", "Apple", "Coconut", "Darjeeling"};

我在以下行收到 WhosebugError：

while (arr[i].compareTo(pivot) < 0)

然后在这一行有一堆重复的：

sort(arr, i, right);

上面一行的重复错误告诉我它可能与无限递归的发生有关，但我不知道为什么会这样。

我也不知道为什么它会在 while 循环行抛出错误...看起来我用来比较 arr[i] 和 pivot 的逻辑没问题？

Answer 1

为枢轴选择中间元素的行应该是：

    T pivot = arr[left + (right - left) / 2];

当前代码有效地使用了 T pivot = arr[right / 2]，其中索引 right / 2 可能小于左侧，导致从左到右的范围内不存在主元值。

考虑这样一种情况，其中使用的主元值小于从左到右范围内的所有元素值。这可能导致第一个循环前进 i 超过 right 甚至超过数组末尾，这可能导致堆栈溢出或分段错误。

通用快速排序导致 StackOverflowError

Generic QuickSort causing StackOverflowError

java

generics

quicksort