快速排序递归Java

Question

我正在尝试使用递归编写快速排序代码，但我得到一个堆栈溢出错误。第二个递归函数给出了连续误差。我只是想不通。

public class QuickSortRec {
public static void quicksort(int input[],int a,int b)
{
    if(a<b)
    {
        int pivotpos=partition(input,a,b);
        quicksort(input, a,pivotpos-1);
        quicksort(input, pivotpos+1,b);
    }
}
private static int partition(int input[],int a,int b)
{
    int pivot=input[a];
    int count=0;
    for(int i=a+1;i< input.length;i++)
    {
        if(input[i]<pivot)
        {
            count++;
        }
    }
    int temp=input[a];
    input[a]=input[count];
    input[count]=temp;
    for(int i=0;i<count;i++)
    {
        if(input[i]>pivot)
        {
            for(int j=input.length-1;j>pivot;j--)
            {
                if(input[j]<pivot)
                {
                    temp=input[i];
                    input[i]=input[j];
                    input[j]=temp;
                }
            }
        }
    }
    return count;
}
public static void main(String[]args)
{
    int arr[]={6,2,10,8,15,3,4};
    int a=0;
    int b=arr.length-1;
    quicksort(arr,a,b);
    for(int i=0;i<arr.length;i++)
    {
        System.out.print(arr[i]+" ");
    }
  }
}

Answer 1

你有些错误。例如，您从未在pivot函数中使用b。您必须更改partition函数，如下所示：

public class QuickSortRec {
    public static void quicksort(int input[],int a,int b)
    {
        if(a<b)
        {
            int pivotpos=partition(input, a,b);
            quicksort(input, a,pivotpos-1);
            quicksort(input, pivotpos+1,b);
        }
    }

    private static int partition(int arr[],int low,int high)
    {
        int pivot = arr[high];
        int i = (low-1); // index of smaller element
        for (int j=low; j<high; j++)
        {
            // If current element is smaller than or
            // equal to pivot
            if (arr[j] <= pivot)
            {
                i++;

                // swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // swap arr[i+1] and arr[high] (or pivot)
        int temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;

        return i+1;
    }

    public static void main(String[]args)
    {
        int arr[]={6,2,10,8,15,3,4};
        int a=0;
        int b=arr.length-1;
        quicksort(arr,a,b);
        for(int i=0;i<arr.length;i++)
        {
            System.out.print(arr[i]+" ");
        }
    }
}