Java递归快速排序出现StackOverflowError问题求助

你的快速排序出现StackOverflowError，核心问题出在切片函数的数组长度计算错误和递归调用的切片范围错误，导致递归无法终止，不断调用自身直到栈溢出。下面逐个拆解问题：

1. 切片函数的致命错误 #

你的slice函数创建数组时长度计算错误：

static int[] slice(int []a, int b, int c){
     int[]temp=new int[c-b+2]; // 长度多算，导致数组存在多余默认值0
     int ind=0;
     for(int i=b;i<c;i++,ind++){
         temp[ind]=a[i];
        }
      return(temp);
}

• 正确长度应为c - b：你要截取的是索引b到c-1的元素（循环条件i < c），总共有c - b个元素。
• 当前错误的长度会让数组末尾填充默认值0，这些多余的0会使递归的数组长度永远大于1，无法触发if(a.length<=1)的终止条件，最终无限递归导致栈溢出。

修正后的切片函数：

static int[] slice(int []a, int b, int c){
     int[] temp = new int[c - b]; // 正确计算截取元素的数量
     int ind = 0;
     for(int i = b; i < c; i++, ind++){
         temp[ind] = a[i];
     }
     return temp;
}

2. 递归调用的切片范围错误 #

排序函数中第二个递归调用的结束位置错误：

sort(slice(a,temp+1,a.length+1));

• 原数组的有效索引范围是0到a.length-1，切片结束位置应设为a.length（循环i < c会遍历到a.length-1），而非a.length+1。
• 使用a.length+1会导致遍历到数组不存在的索引a.length，触发数组越界异常，同时进一步加剧递归无法终止的问题。

修正后的排序函数：

static int[] sort(int[]a){
    if(a.length <= 1){
        return a;
    }
    part(a);
    int temp = j; // j为全局变量
    sort(slice(a, 0, temp));
    sort(slice(a, temp + 1, a.length)); // 修正结束位置为a.length
    return a;
}

3. 分区函数的优化（可选） #

你的part函数逻辑可行，但可以简化并提升可读性：

static void part(int[] a){
    int n = a.length;
    j = -1;
    int pivot = a[n-1]; // 提前取出基准值，减少重复数组访问
    for(int i = 0; i < n; i++){
        if(a[i] > pivot){
            continue;
        }
        j++;
        // 仅当j和i不同时交换，避免无意义的自交换
        if(j != i){
            int t = a[j];
            a[j] = a[i];
            a[i] = t;
        }
    }
}

额外规范建议 #

全局变量j虽然能运行，但不符合Java编码规范，容易引发潜在问题。建议让part函数直接返回分区后的基准值索引：

static int part(int[] a){
    int n = a.length;
    int j = -1;
    int pivot = a[n-1];
    for(int i = 0; i < n; i++){
        if(a[i] > pivot){
            continue;
        }
        j++;
        if(j != i){
            int t = a[j];
            a[j] = a[i];
            a[i] = t;
        }
    }
    return j;
}

之后排序函数直接用int temp = part(a);即可，无需依赖全局变量。

完成上述修改后，递归就能正常终止，不会再出现StackOverflowError。

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