面试问到了,很尴尬,之前完全没想过的,而且有面试官视频远程从摄像头看着自己,又监控自己屏幕代码的情况下,真的大脑完全空白,无法好好思考...
网上看了一下,但是基本都不是我之前快排的思路.
最后还是一句话提醒了我
递归=循环+栈
将递归的调用栈保存到栈中，保存的是数组的元素的下标：low 和 high，且相互对应，既可以头(low)尾(high)呼应，也可以一次弹出两个分别是low和high。
partition分区部分跟普通快排一样
详情可以见我的递归快排版.https://www.jianshu.com/p/f4c8f2aeb607
这里讲一下,如何让递归部分改成非递归:
总体来说用到的思路我上面引用的话一样,采用栈的方式来保存之前的调用栈.
我们每次可以利用栈保存一个成对的数据区,然后对每个分区进行一个partition,直到我们的数据全部排序完毕
贴上代码:
public void NonRecursiveQuickSort(int[] arr){
Stack<Integer> stack=new Stack<>();
stack.push(arr.length-1);
stack.push(0);
while (!stack.isEmpty()){
int l = stack.pop();//左边界
int r=stack.pop();//右边界
int[] partition = partition(arr, l, r);//根据左右边界分区
if (partition[0]>l){
stack.push(partition[0]);
stack.push(l);
}
if (partition[1]<r){
stack.push(r);
stack.push(partition[1]);
}
}
}
public int[] partition(int[] arr, int L, int R){
int less= L -1;
int more=R;
int curr= L;
while (curr<more){
if (arr[curr]<arr[R]){
swap(arr,++less,curr++);
}else if (arr[curr]>arr[R]){
swap(arr,--more,curr);
}else {
curr++;
}
}
swap(arr,curr,R);//让最后一个比较的基准数和more的第一个数交换
return new int[]{less,curr};//返回小于区最后一个数位置和大于区第一个数位置
}
//交换数组array上,ab两个位置的值
public static void swap(int [] array,int a,int b){ //a,b为数组下标
int temp=array[a];
array[a]=array[b];
array[b]=temp;
}
我的方法跟其他人的不太相同,但是总体来说是一种思路.大家的脑回路不一样最适合你的实现可能不太一致,这里参考了实现非递归快排的许多方法
如果你的代码思路跟我不一样,那么可以参考他们的看看
https://www.jianshu.com/p/84a7c8b8fe4b
https://blog.csdn.net/Hadas_Wang/article/details/50917058
https://www.cnblogs.com/xinyuyu/p/4788160.html
