QuickSort中递归调用partitionStep导致的stackoverflow异常

Question

我尝试为 int[] 实现快速排序算法。我对分区步骤进行了正确编码，但后来我想递归调用分区步骤方法来对数组进行排序，不幸的是，我将错误的索引传递给递归调用，我得到了 Whosebug 异常。

我基于：https://www.youtube.com/watch?v=y_G9BkAm6B8

public class Quicksort {

    public static void partition(int[] t, int i, int j) {

        int start = i, end = j;
        int pivot = t[(i + j) / 2]; // select the pivot as the middle value
        System.out.println("pivot: " + pivot);
        int temp;
        while (i < j) {
            while (t[i] < pivot) { // looking for value greater or equal to the
                                    // pivot
                i++;
            }
            while (t[j] > pivot) { // looking for value lower or equal to the
                                    // pivot
                j--;
            }
            System.out.println("i = " + i + " j = " + j + " swaps " + t[i] + " with " + t[j]);
            temp = t[i]; // swap
            t[i] = t[j];
            t[j] = temp;
            i++; // move to the next element
            j--; // move to the prev element
            display(t);
        }
        // I CALL THEM WRONG
        partition(t, start, j); // partition for the left part of the array
        partition(t, i, end); // partiion for the right part of the array
    }

    public static void display(int[] t) {
        for (int el : t)
            System.out.print(el + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] t = { 6, 4, 1, 32, 5, 7, 8, 6, 9, 1 };
        display(t);
        partition(t, 0, t.length - 1);
    }
}

Answer 1

根本问题是你的递归没有退出条件。您的 partition 方法中没有单个 return 语句。当您的 while 循环退出时，它只会再次调用 partition 方法。但是代码里面没什么好说的，"stop making recursive calls into partition"。因此，堆栈溢出。

我想你至少要在分区函数的顶部说这个。这应该清除堆栈溢出。

public static void partition(int[] t, int i, int j) {
    if (i >= j)  {
        return;
    }

我也不确定，但这行不应该：

partition(t, j, end); //partiion for the right part of the array

真的是这样：

partition(t, i+1, end); //partiion for the right part of the array

Answer 2

您缺少用于检查 i 是否小于或等于 j 的 if 语句...

public class QuickSort {

public static void display(int[] arr){
    for(int i = 0; i < arr.length; i++) {
        System.out.println( arr[i] );

    }
}

public static void main( String[] args ) {
    int[] data = new int[]{ 5, 10, 1, 9, 4, 8, 3, 6, 2, 6,7 };
    System.out.println("Unsorted array : " );
    display( data );
    quickSort( data, 0, data.length - 1 );
    System.out.println( "Sorted array: " );
    display( data );
}

public static void quickSort( int[] arr, int left, int right ) {
    int i = left;
    int j = right;
    int temp;
    int pivot = arr[( left + right ) / 2];
    while( i <= j ) {
        while( arr[i] < pivot ) {
            i++;
        }
        while( arr[j] > pivot ) {
            j--;
        }
        // You forgot to test here...
        if( i <= j ) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    if( left < j ) {
        quickSort( arr, left, j );
    }
    if( i < right ) {
        quickSort( arr, i, right );
    }
}

}

Answer 3

此外，如果您正在进行深度递归调用，您可能需要考虑使用 -Xss 参数来扩大堆栈大小。您可以在这里找到完整的答案：How to increase the Java stack size?

我知道您的代码有问题，而不是堆栈的实际大小，但是一旦您修复了代码，这可能会很有用。

QuickSort中递归调用partitionStep导致的stackoverflow异常

Stackoverflow exception caused by recursive call of partitionStep in QuickSort

java

recursion

quicksort