java - 在快速排序中使用最后一个元素作为枢轴时无法解决错误

Question

我已经用 Java 实现了 QuickSort。使用第一个元素作为枢轴的代码工作正常。我试图以类似的方式使用最后一个元素作为枢轴来实现它，但我无法找出它崩溃的原因。

partitionFirst() 函数使用第一个元素作为基准partitionLast() 函数使用最后一个元素作为基准

代码在我在代码中提到的第 75 行和第 77 行中断。使用 partitionLast()

时

如果您在 partitionLast() 中注意到，我以不同的方式返回了主元逻辑，请牢记主元始终小于元素的情况。例如。 { 7 8 9 4 5 6 |3| } 其中 3 是分区

如果有人能指出代码中的错误，将会很有帮助。如果有优化建议，也可以随意提出。

public class QuickSort {
public void swap(int[] arr, int i, int j)
{
    if(i!=j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

public int partitionFirst(int arr[], int start,int end)
{
    int j = start + 1;
    int pivot = arr[start]; 
    for(int i=start+1;i<end;i++)
    {
        if(pivot > arr[i])
        {
            swap(arr,i,j);
            j++;
        }
    }
    swap(arr,start,j-1);
    return (j-1);
}

public int partitionLast(int arr[], int start,int end)
{
    int j = start;
    int pivot = arr[(end - 1)]; 
    for(int i=start;i < end - 1  ;i++)
    {
        if(pivot > arr[i])
        {
            swap(arr,i,j);
            j++;
        }
    }
    if((j - 1) < 0)
    {
        swap(arr,end-1 ,j);
        return j;
    }
    else
    {
        swap(arr,end-1 ,(j-1));
        return (j-1);
    }
}

public void QuickSort(int arr[], int start,int end)
{
    if(end > start)
    {

        int p = partitionLast(arr, start, end); //75 line
        QuickSort(arr,start, p);
        QuickSort(arr,p+1,end); //77 line
    }
    return;
}

public static void main(String args[]) throws FileNotFoundException
{
    int[] brr = {1,6,8,2,3,4};
    QuickSort ob1 = new QuickSort();
    ob1.QuickSort(brr,0,brr.length);
}

/* QuickSort.QuickSort(QuickSort.java:75) 在 QuickSort.QuickSort(QuickSort.java:77) 在 QuickSort.QuickSort(QuickSort.java:77) 线程“主”java.lang.StackOverflowError 中的异常。 ...... */

Answer 1

这一切都归结为用枢轴交换正确的元素:

public int partitionLast(int arr[], int start,int end)
{
    int j = start;
    int pivot = arr[(end - 1)];
    for(int i=start;i < end - 1  ;i++)
    {
        if(pivot > arr[i])
        {
            swap(arr,i,j);
            j++;
        }
    }
    swap(arr,end-1,j);
    return (j);
}