面试问到了,很尴尬,之前完全没想过的,而且有面试官视频远程从摄像头看着自己,又监控自己屏幕代码的情况下,真的大脑完全空白,无法好好思考...

网上看了一下,但是基本都不是我之前快排的思路.
最后还是一句话提醒了我

递归=循环+栈
将递归的调用栈保存到栈中，保存的是数组的元素的下标：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