快速排序中的 StackOverflowError

Question

package arrays;

import java.util.Arrays;
import java.util.List;

public class QuickSort {

    public static void main(String[] args){
        int[] arr = {7,2,4,8,1,6};
        int[] result = quick(arr,0, arr.length-1);
        for(int i=0; i< result.length; i++) {
            System.out.println(result[i]);
        }
    }

    private static int[] quick(int[] arr, int startIndex, int endIndex){
        if(startIndex<endIndex){
            int q= partition(arr,startIndex,endIndex);
            quick(arr, startIndex,q-1);
            quick(arr,q+1, endIndex);
        }
      return arr;
    }

    private static int partition(int[] arr, int startIndex, int endIndex){
       int pivot = arr[endIndex];
       int i = startIndex-1;
       for(int j=startIndex; j<+arr.length;j++){
           if(arr[j]<=pivot){
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
           }
       }
       List<int[]> list = Arrays.asList(arr);
       return list.indexOf(pivot);
    }
}

我得到 WhosebugError 以上代码。我已经干了运行代码，它看起来不错。请有人帮助我了解问题所在吗？

Answer 1

首先，你有几个小的语法错误：

分区中的 For 循环：有一个多余的 +，循环应该达到 endIndex。应该是

for(int j = startIndex; j < endIndex; j++) {

if(arr[j]<=pivot){ => 应该是 if(arr[j] < pivot) {（因为您正在寻找一个严格小于主元的数字，尽管您的示例也应该在没有此更改的情况下工作。
最后，您的 parition 总是 returns -1，因为您在单例列表上调用 indexOf`，该列表从不包含主元。正确的获取方式是：

int temp = arr[endIndex];
arr[endIndex] = arr[i + 1];
arr[i + 1] = temp;
return i + 1;

完整修改代码：

import java.util.Arrays;
import java.util.List;

public class QuickSort {

    public static void main(String[] args){
        int[] arr = {7,2,4,8,1,6};
        int[] result = quick(arr,0, arr.length-1);
        for(int i=0; i< result.length; i++) {
            System.out.println(result[i]);
        }
    }

    private static int[] quick(int[] arr, int startIndex, int endIndex){
        if(startIndex<endIndex){
            int q= partition(arr,startIndex,endIndex);
            quick(arr, startIndex,q-1);
            quick(arr,q+1, endIndex);
        }
      return arr;
    }

    private static int partition(int[] arr, int startIndex, int endIndex){
       int pivot = arr[endIndex];
       int i = startIndex-1;
       for(int j=startIndex; j<endIndex;j++){
           if(arr[j]<=pivot){
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
           }
       }
       int temp = arr[endIndex];
       arr[endIndex] = arr[i + 1];
       arr[i + 1] = temp;
       return i + 1;
    }
}

您可以在此处查看伪代码实现：https://www.geeksforgeeks.org/quick-sort/

快速排序中的 StackOverflowError

StackOverflowError in quick sort

java

quicksort