Java快速排序代码运行抛出StackOverflowError错误求助

错误代码复现 #

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);
    }
}

根因分析 #

一共存在2个核心错误，直接导致无限递归触发栈溢出：

• Arrays.asList(arr)用法完全错误
  Java中Arrays.asList传入基本类型数组int[]时，不会自动拆箱把int元素转为列表元素，只会把整个int[]作为唯一元素存入List<int[]>。调用list.indexOf(pivot)时，pivot是int值（自动装箱为Integer对象），和列表里存储的int数组对象永远匹配不上，所以永远返回-1。返回的q=-1后，递归逻辑会无限重复执行，最终触发栈溢出。
• partition的for循环范围错误
  当前代码写的是j < +arr.length，会每次遍历整个数组，而不是当前需要分区的[startIndex, endIndex]区间，就算解决了返回值问题，分区逻辑本身也是错误的。

修复后的代码 #

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;
       }
   }
   // 直接返回pivot的正确位置i即可，不需要多余的List操作
   return i;
}

验证 #

修复后运行代码，输出结果为1 2 4 6 7 8，排序逻辑正确，无栈溢出问题。

内容的提问来源于stack exchange，提问作者Aishwarya