快排非递归版

名字是乱打的

发布于 2021-12-22 14:59:38

2380

发布于 2021-12-22 14:59:38

文章被收录于专栏：软件工程

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

网上看了一下,但是基本都不是我之前快排的思路.

最后还是一句话提醒了我

递归=循环+栈将递归的调用栈保存到栈中，保存的是数组的元素的下标：low 和 high，且相互对应，既可以头(low)尾(high)呼应，也可以一次弹出两个分别是low和high。

partition分区部分跟普通快排一样

详情可以见我的递归快排版.https://cloud.tencent.com/developer/article/2002206

这里讲一下,如何让递归部分改成非递归:

总体来说用到的思路我上面引用的话一样,采用栈的方式来保存之前的调用栈.

我们每次可以利用栈保存一个成对的数据区,然后对每个分区进行一个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;
    }