请选择 进入手机版 | 继续访问电脑版

随机快排

[复制链接]
冰宇 发表于 2020-12-31 18:59:58 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
思路


  • 随机找数组中一个数做基准数;
  • 颠末一个partition操纵,到达基准数左边的数都比它小,右边的数都比它大。以此固定基准数的位置;
  • 基准数左侧部门递归做partition操纵;
  • 基准数右侧部门递归做partition操纵;
  • 递归的出口是只剩一个元素。
partition

功能:颠末一系列比力交换后,使base基准数左边的数都比它小,右边的数都比它大
流程:

  • 规定less下标的左边为小于base的区域,more下标的右边为大于base的区域
  • 用index指针遍历元素,从数组的L遍历到R
  • 遍历到的数小于base,less右移,less位置和index位置元素交换,index右移
  • 遍历到的数便是base index右移
  • 遍历到的数大于base,more左移,more位置与index位置元素交换,index不动
代码

  1.         /**     * 随机快排     */        public static void quickSort(int[] arr, int left, int right) {        if (left >= right) {            return;        }        int base = arr[new Random().nextInt(arr.length)];        int[] cut = partition(arr, base, left, right);        quickSort(arr, left, cut[0]);        quickSort(arr, cut[1], right);    }    /**     * partition,即荷兰国旗问题     */    public static int[] partition(int[] arr, int base, int left, int right) {        int less = left - 1;        int more = right + 1;        int index = left;        while (index < more) {            if (arr[index] < base) {                less++;                exchange(arr, less, index);                index++;            } else if (arr[index] == base) {                index++;            } else {                more--;                exchange(arr, more, index);            }        }        return new int[]{less, more};    }    public static void exchange(int[] arr, int minIndex, int index) {        int temp = arr[minIndex];        arr[minIndex] = arr[index];        arr[index] = temp;    }
复制代码
来源:https://blog.csdn.net/weixin_44713050/article/details/111992591
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )