给定一个数组arr, 和一个整数num。把小于num的放数组左边,等于num的放中间,大于num的放右边。要求额外空间复杂度O(1),时间复杂度O(N)
- 快速排序1.0:每次确定一个数的位置
- 快速排序2.0:每次确定一个多个数(num相同,范围)的位置
- 快速排序3.0:随机快速排序+荷兰国旗问题
随机快排(快排3.0):
在arr[L, R]范围上,进行快速排序的过程
1.在这个范围上,随机选择一个num
2.用num对该范围做partition(小于num的放左边,等于num的放中间,大于num的放右边,假设等于num的数所在范围是[a, b])
3.对arr[L, a-1]进行快速排序(递归)
4.对arr[b+1, R]进行快速排序(递归)
因为每一次partition都会搞定一批数的位置不再变动,所以最终排序能完成
public static void quickSort2(int[] arr){ if(arr == null || arr.length < 2){ return; } //让0 到 arr.length - 1有序 process2(arr, 0, arr.length - 1); } public static void process2(int[] arr, int L, int R){ if(L >= R){ return; } //随机快排:随机选一个数与最右边的数交换 //在arr的[L, R]上随机选择一个数进行交换 swap(arr ,L + (int)(Math.random() * (R - L + 1)), R); int[] equalArea = netherlandsFlag2(arr, L, R); //新的左递归 process2(arr, L, equalArea[0] - 1); //新的右递归 process2(arr, equalArea[1] + 1, R); } //荷兰国旗问题 public static int[] netherlandsFlag2(int[] arr, int L, int R){ if(L > R){ return new int[]{-1, -1}; } if(L == R){ return new int[]{1, 1}; } int less = L - 1; int more = R; int index = L; while(index < more){ if(arr[index] == arr[R]){ index++;//等于,直接移动【index++】 } else if(arr[index] < arr[R]){ //小于,与小于区域的前一个数换 swap(arr, index++, ++less); } else { //大于,与大于区域的前一个数换 swap(arr, index, --more); } } swap(arr, more, R); //less+1:等于区的开始 return new int[]{less + 1, more}; }2.2 非递归实现【栈结构】
①定义内部类Op:用来存储要排序的范围信息
Op:
//排序范围 public static class Op{ public int l; public int r; public Op(int left, int right){ l = left; r = right; } }
②荷兰国旗问题:用来排序(小于放左,等于放中,大于放右)
//荷兰国旗问题 public static int[] netherlandsFlag2(int[] arr, int L, int R){ if(L > R){ return new int[]{-1, -1}; } if(L == R){ return new int[]{1, 1}; } int less = L - 1; int more = R; int index = L; while(index < more){ if(arr[index] == arr[R]){ index++;//等于,直接移动【index++】 } else if(arr[index] < arr[R]){ //小于,与小于区域的前一个数换 swap(arr, index++, ++less); } else { //大于,与大于区域的前一个数换 swap(arr, index, --more); } } swap(arr, more, R); //less+1:等于区的开始 return new int[]{less + 1, more}; }
③交换:
public static void swap(int[] arr, int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
全部代码:
//排序范围 public static class Op{ public int l; public int r; public Op(int left, int right){ l = left; r = right; } } //非递归版本【用栈实现】 public static void quickSort3(int[] arr){ if(arr == null || arr.length < 2){ return; } int N = arr.length; swap(arr, (int) (Math.random() * N), N-1); int[] equalArea = netherlandsFlag(arr, 0, N - 1); int el = equalArea[0]; int er = equalArea[1]; Stackstack = new Stack<>(); stack.push(new Op(0, el - 1));//类比:左边递归 stack.push(new Op(er + 1, N - 1));//右边递归 while(!stack.isEmpty()){ Op op = stack.pop(); if(op.l < op.r){ swap(arr, op.l + (int)(Math.random() * (op.r - op.l + 1)), op.r); equalArea = netherlandsFlag(arr, op.l, op.r); el = equalArea[0]; er = equalArea[1]; //入栈:模拟向下递归 stack.push(new Op(op.l, el - 1)); stack.push(new Op(er + 1, op.r)); } } } //荷兰国旗问题 public static int[] netherlandsFlag2(int[] arr, int L, int R){ if(L > R){ return new int[]{-1, -1}; } if(L == R){ return new int[]{1, 1}; } int less = L - 1; int more = R; int index = L; while(index < more){ if(arr[index] == arr[R]){ index++;//等于,直接移动【index++】 } else if(arr[index] < arr[R]){ //小于,与小于区域的前一个数换 swap(arr, index++, ++less); } else { //大于,与大于区域的前一个数换 swap(arr, index, --more); } } swap(arr, more, R); //less+1:等于区的开始 return new int[]{less + 1, more}; } public static void swap(int[] arr, int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }