java - 快速排序 - StackOverflowException

Question

我正在尝试编写一个快速排序算法。请看下面的代码：

public static void quickSort(int[] tab, int lowIndex, int highIndex) {
    if (tab.length == 0 || tab == null) {
        return;
    }

    int i = lowIndex;
    int j = highIndex;

    int pivot = tab[tab.length / 2];

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

        if (i <= j) {
            int c = tab[i];
            tab[i] = tab[j];
            tab[j] = c;
            i++;
            j--;
        }

        if (lowIndex < j) {
            quickSort(tab, lowIndex, j); // error !!!
        }
        if (i < highIndex) {
            quickSort(tab, i, highIndex);
        }
    }

}

问题是线程“main”java.lang.StackOverflowError 中的异常。怎么了 ？

Answer 1

这是错误的：

int pivot = tab[tab.length / 2];

您必须在提供的切片中找到枢轴，而不是在tab.

int pivot = tab[lowIndex + (highIndex - lowIndex)/ 2];

此外，您终止递归的条件是错误的。桌子的长度不会改变。你必须检查是否lowIndex >= highIndex