快速排序算法的递归和非递归

基本思路

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

递归

思路：

步骤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右移

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

code：

    //非递归版//使用栈记录每次分区得到的左右位置//然后出栈顶元素，继续分区，将新的分区如栈，直到栈为空//使用一个辅助对象用于入栈时保存分区位置 oppublic 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;}