我已经在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/