quickSort - 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是否