java - 自定义快速排序在java中不起作用

Question

我已经实现了QuickSort，但由于某些奇怪的原因，我的代码给出了 StackOverflow 异常。 我一直在绞尽脑汁地想了解为什么我的代码会破坏任何想法，为什么我的代码会被破坏？ 还有其他方法可以优化这个吗？ 递归导致我的堆栈溢出；但无法确定发生这种情况的位置!

   import java.io.*;
   import java.util.*;
   import java.text.*;
   import java.math.*;
   import java.util.regex.*;

public class Solution {

    static void quickSort(int[] arr,int low,int high) {
        // Complete this function
        int p =partition(arr,low,high);
         System.out.println("partiion at p[]"+p); 
        if(low<p){

            System.out.println("starging quickSort at low[]"+low+" hgh["+(p-1)); 
            quickSort(arr,low,p-1);    
        }

        if(p<high){
            System.out.println("starging quickSort at low[]"+p+1+" hgh["+high); 
            quickSort(arr,p+1,high);    
        }


    }
    static void swap(int []a,int x,int y){
        int tmp = a[y];
        a[y]=a[x];
        a[x]=tmp;
    }

    static int partition(int[] arr,int low,int high){
        int pivot = arr [low+ (high-low)/2];
        int left  = low;
        int right = high;
        System.out.println("pivot["+pivot+"] left ["+left+"]right["+right+"]");


        while(left<= right)
        {

            while(arr[left] < pivot){
                left++;
            }
            System.out.println("**..done now left ["+left+"]");


            while(arr[right] >pivot){
                right--;
            }

            System.out.println("##..done now right ["+right+"]");

            if(left <=right){
                swap(arr,left,right);
                right--;
                left++;
            }

                        System.out.println("#swapping");


            for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + (i != arr.length - 1 ? " " : ""));
        }

            System.out.println("done#swapping");
        }            

        return left;
    }
    static int[] quickSort(int[] arr) {
        quickSort(arr,0,arr.length-1);
        return arr;

    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int arr_i = 0; arr_i < n; arr_i++){
            arr[arr_i] = in.nextInt();
        }
        System.out.println("ubsoted ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + (i != arr.length - 1 ? " " : ""));
        }
        System.out.println("");

        int[] result = quickSort(arr);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + (i != result.length - 1 ? " " : ""));
        }
        System.out.println("");


        in.close();
    }
}

Answer 1

您没有指定 return 语句，这就是递归调用快速排序时堆栈溢出的原因。

所以，在快速排序方法中添加一个像这样的返回条件作为第一条语句。

static void quickSort(int[] arr,int low,int high) {

     if (high <=low) {
         return;
     }