快速排序算法的递归和非递归-Toy模板网

这篇具有很好参考价值的文章主要介绍了快速排序算法的递归和非递归。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

基本思路

选择一个基准值，将数组划分三个区域，小于基准值的区域位于左侧，等于基准值的区域位于中间，大于基准值的区域位于右侧。将大于和小于区域继续进行分区，周而复始，不断进行分区和交换，直到排序完成

递归

思路：

步骤1:

在当前分区范围[l,r]中随机选中一个数作为基准值，交换到分区范围的最右侧，即r位置

步骤2:

以r位置基准值进行分区

步骤3:

对所以小于区域和大于区域继续进行步骤1操作，直到范围为1结束

单次分区过程：

less 代表小于基准值分区范围，more代表大于分区值范围，index代表当前待比较位置，r为当前分区范围最右位置

比较当前index位置和基准位置

如果 arr[index] == arr[r] ，则index向右移动

如果大于，则 more向左移动，并将index位置的数与more位置的数进行交换

如果小于，则将 less右侧位置的数与index数交换；即less范围扩大 less++，交换less和index位置数，index右移

快速排序算法的递归和非递归,算法,排序算法,算法,java,数据结构

code：

    //递归
    public static void quickSortRecursive(int [] arr){
        if(arr == null || arr.length < 2)return;
        progress(arr,0,arr.length-1);
    }
    //让arr在[l,r]上有序
    public static void progress(int [] arr,int l,int r){
        if(l >= r){
            return;
        }
        //swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
        //指定一个[l,r]范围随机位置放到最右侧作为基准值
        // math.random: [0,1)
        // math.random * x : [0,x)
        // Math.random() * (r -l + 1) : l到r长度范围内的一个随机数， + l则定位到数组的索引上
        swap(arr,l + (int)(Math.random() * (r -l + 1)),r);
        int [] equalArea = partition(arr,l,r);
        progress(arr,l,equalArea[0] -1);
        progress(arr,equalArea[1] + 1,r);
    }
//让arr以r位置数为基准，<arr[r]位置的数放左边，>arr[r]位置的数放右边 ==arr[r]位置的数位于中间
    //返回==arr[r]位置的数最左和最右位置
    public static int[] partition(int [] arr,int l,int r){
        //如果l > r，则数组不合规，返回一个无效值索引
        if(l > r) return new int[] { -1, -1 };
        //如果l == r，则说明只有一个值,那么等于分区也就是当前一个位置的索引
        if(l == r) return new int[] {l,r};

        //l < r

        //基准位置 r
        //less代表 <分区 的最右一个位置索引
        int less = l -1;
        //more代表 >分区 的最左一个位置的索引
        int more = r;
        //index代表待分区数最左位置索引
        int index = l;

        //进行分区，越界条件是待分区索引来到以分区区域[大于分区]
        while (index < more){
            //System.out.println("less,index,more:"+less+","+index + ","+more);
            //如果待分区数 == 基准值，那么说明该数不是大于分区的数，index向右移动
            if(arr[index] == arr[r]){
                index++;

            }
            //如果待分区数 < 基准值，那么说明该位置数是属于小于分区的数，则将该数交换到小于分区去
            if(arr[index] < arr[r]){

                //小于分区范围扩大
                less++;
                //将当前位置交换到小于分区
                //此时当前位置是等于或者小于分区的数
                swap(arr,index,less);
                //索引index需要向右移动
                index++;
                //等价于
                //swap(arr,index++,++less);
            }
            //如果待分区数 > 基准值，那么说明该位置数是属于大于分区的数,则将该数交换到大于分区去
            //此时index不移动，因为将位置的数交换到index位置上了
            if(arr[index] > arr[r]){

                //大于范围向左扩张
                more--;
                //当前数交换到大于区域中，交换来的数是一个未知大小的数，所以index不移动
                swap(arr,index,more);

                //等价于
                //swap(arr,index,--more);
            }
        }
        //遍历完成后，此时r位置为等于区域的数，需要交换到等于分区中
        swap(arr,more,r);
        //交换完成后，less为小于分区最右索引，more为等于分区最右索引
        //more原本为大于分区最左位置索引，但是将r交换到该位置后，大于分区向右缩减了一个位置，此时more位置为等于分区最右索引
        return new int[]{less+1,more};
    }
    public static void swap(int [] arr,int l,int r){
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

非递归

思路与递归一致，仅是将系统栈替换为自己控制的栈

使用栈记录每次分区得到的左右位置

然后出栈顶元素，继续分区，将新的分区如栈，直到栈为空

使用一个辅助对象用于入栈时保存分区位置 op文章来源地址https://www.toymoban.com/news/detail-700857.html

code：

    //非递归版
    //使用栈记录每次分区得到的左右位置
    //然后出栈顶元素，继续分区，将新的分区如栈，直到栈为空
    //使用一个辅助对象用于入栈时保存分区位置 op
    public static void quickSortUnRecursive(int [] arr){
        if(arr == null || arr.length < 2) return;
        int N = arr.length;
        Stack<Op> stack = new Stack<>();

        //随机得到基准值，放到最右位置
        swap(arr, (int)(Math.random() * N),N-1);
        //分区
        int [] equalArea = partition(arr,0,N-1);
        //将分区后的范围入栈
        stack.push(new Op(0,equalArea[0] -1));
        stack.push(new Op(equalArea[1]+1,N-1));

        //临时变量，保存出栈的范围值
        Op temp = new Op(0,0);

        while (!stack.isEmpty()){
            //出栈
            temp = stack.pop();
            //继续对当前范围进行分区

            //如果分区得到的范围错误，说明该区域已经排好序了
            if(temp.l >= temp.r)continue;

            //随机基准值
            swap(arr,temp.l + (int) (Math.random() * (temp.r - temp.l + 1)), temp.r);
            //分区
            equalArea = partition(arr,temp.l, temp.r);
            //入栈
            stack.push(new Op(temp.l, equalArea[0] -1));
            stack.push(new Op(equalArea[1]+ 1, temp.r));

        }
    }


    public static class Op{
        public int l;
        public int r;
        public Op(int l,int r){
            this.l = l;this.r = r;
        }
    }


    //让arr以r位置数为基准，<arr[r]位置的数放左边，>arr[r]位置的数放右边 ==arr[r]位置的数位于中间
    //返回==arr[r]位置的数最左和最右位置
    public static int[] partition(int [] arr,int l,int r){
        //如果l > r，则数组不合规，返回一个无效值索引
        if(l > r) return new int[] { -1, -1 };
        //如果l == r，则说明只有一个值,那么等于分区也就是当前一个位置的索引
        if(l == r) return new int[] {l,r};

        //l < r

        //基准位置 r
        //less代表 <分区 的最右一个位置索引
        int less = l -1;
        //more代表 >分区 的最左一个位置的索引
        int more = r;
        //index代表待分区数最左位置索引
        int index = l;

        //进行分区，越界条件是待分区索引来到以分区区域[大于分区]
        while (index < more){
            //System.out.println("less,index,more:"+less+","+index + ","+more);
            //如果待分区数 == 基准值，那么说明该数不是大于分区的数，index向右移动
            if(arr[index] == arr[r]){
                index++;

            }
            //如果待分区数 < 基准值，那么说明该位置数是属于小于分区的数，则将该数交换到小于分区去
            if(arr[index] < arr[r]){

                //小于分区范围扩大
                less++;
                //将当前位置交换到小于分区
                //此时当前位置是等于或者小于分区的数
                swap(arr,index,less);
                //索引index需要向右移动
                index++;
                //等价于
                //swap(arr,index++,++less);
            }
            //如果待分区数 > 基准值，那么说明该位置数是属于大于分区的数,则将该数交换到大于分区去
            //此时index不移动，因为将位置的数交换到index位置上了
            if(arr[index] > arr[r]){

                //大于范围向左扩张
                more--;
                //当前数交换到大于区域中，交换来的数是一个未知大小的数，所以index不移动
                swap(arr,index,more);

                //等价于
                //swap(arr,index,--more);
            }
        }
        //遍历完成后，此时r位置为等于区域的数，需要交换到等于分区中
        swap(arr,more,r);
        //交换完成后，less为小于分区最右索引，more为等于分区最右索引
        //more原本为大于分区最左位置索引，但是将r交换到该位置后，大于分区向右缩减了一个位置，此时more位置为等于分区最右索引
        return new int[]{less+1,more};
    }
    public static void swap(int [] arr,int l,int r){
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

到了这里，关于快速排序算法的递归和非递归的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！