前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >快排非递归版

快排非递归版

作者头像
名字是乱打的
发布2021-12-22 14:59:38
2250
发布2021-12-22 14:59:38
举报
文章被收录于专栏:软件工程软件工程

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

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

最后还是一句话提醒了我

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

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

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

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

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

我们每次可以利用栈保存一个成对的数据区,然后对每个分区进行一个partition,直到我们的数据全部排序完毕

贴上代码:
代码语言:javascript
复制
 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

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019/12/15 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 这里讲一下,如何让递归部分改成非递归:
  • 贴上代码:
    • 我的方法跟其他人的不太相同,但是总体来说是一种思路.大家的脑回路不一样最适合你的实现可能不太一致,这里参考了实现非递归快排的许多方法
      • 如果你的代码思路跟我不一样,那么可以参考他们的看看
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档