Question

小弟正在学习java，现在遇到一个问题，快速排序的栈溢出的问题，希望大家能够帮一下，谢谢。

/*
关于快速排序的。
求帮忙，不知道哪里错了。这是我学习的视频教材上边的代码。
谢谢大家。
*/
public class Sort
{
public static void main(String[] args)
{
int arr[]={3,0,3,3,7,2,2,5}; //为什么arr[3]=3 的时候系统报错，错误为java.lang.StackOverflowError。
//而将arr[3]=4,则没有错误。
QuickSort qs=new QuickSort();
qs.quickSort(0,arr.length-1,arr);
System.out.print("快速排序后的数据为：");
for (int i=0;i<arr.length ;i++ )
{
System.out.print(arr[i]+" ");
}
System.out.println();
}
}
class QuickSort
{
public void quickSort(int left,int right,int arr[])
{
int l=left;
int r=right;
int pivot=arr[(left+right)/2];
int temp=0;

while(l<r)
{
while(arr[l]<pivot) l++;
while(arr[r]>pivot) r--;

if (l>=r) break;

temp=arr[l];
arr[l]=arr[r];
arr[r]=temp;

if (arr[l]==pivot) --r;
if (arr[r]==pivot) ++l;

if (l==r)
{
l++;
r--;
}

if (left<r) quickSort(left,r,arr);
if (right>l) quickSort(l,right,arr); //这行报告有错误。
}
}
}
出错图片

Answer 1

我帮你调了半天还是没有看出来具体是哪点出错了。
不过你大概的算法我看出来了，是从左右两边同时与关键数进行对比，而且对比成功后还是进行的交换，而不是更换位置（这个很有可能是出错的原因）。我觉得 可能是在两边 交换的过程造成了无限循环。

其实对比的时候只从一个方向同关键数对比就行了，而且若某个数字满足移动的条件，应当把它取出放到队首或队尾，而不是进行交换。比如从第一个数开始查看，每个数字做以下判断：
1、若它是最后一个数字，则结束一轮对比；
2、若它等于关键数字，则跳过它；
3、若它比关键数字小，且在其左边，则直接跳过；
4、若它比关键数字小，且在右边，则将它从队列中取出，并放到队首；（注意，是取出放到队首，而不是与某个元素交换，你的算法可能问题就出在这个上边）
5、若它比关键数字大，且在左边，则将它从队列中取出，并放到队尾；
6、若它比关键数字大，且在右边，则直接跳过。

你可以先修改 交换的那部分，换成取出并放到队首或队尾试试，应该就没问题了。