我已经在java中实现了quicksort。使用第一个元素作为轴心的代码工作正常。我试图以类似的方式使用最后一个元素作为轴心来实现它,但无法找出它崩溃的原因。
partitionFirst()函数使用第一个元素作为轴心
partitionLast()函数使用最后一个元素作为轴心
代码在我在代码中提到的第75行和第77行中断。当使用partitionLast()
如果您注意到在partitionLast()中,我以不同的方式返回了pivot逻辑,请记住pivot总是小于elements的情况。例如。{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);
}

}
/*线程“main”java.lang.StackOverflowError在QuickSort.QuickSort(QuickSort.java:75)在QuickSort.QuickSort(QuickSort.java:77)在QuickSort.QuickSort(QuickSort.java:77)处出现异常*/

最佳答案

所有这些都归结为使用轴交换正确的元素:

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

关于java - 在快速排序中使用最后一个元素作为枢轴时无法解决错误,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/56108019/

10-14 05:10