时间戳

首页 > 解决方案 > 在快速排序中使用最后一个元素作为枢轴时无法解决错误

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

问题描述

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

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) 的线程“main”java.lang.StackOverflowError 中的异常 .... ... */

标签： javaalgorithmquicksort

解决方案

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

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

推荐阅读