Partition过程
给定一个数组arr,和一个整数num。请把小于等于num的数放在数组的左边,大于num的数放在数组的右边。
要求额外空间复杂度O(1),时间复杂度O(N)
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
// arr[L..R]上,以arr[R]位置的数做划分值
// <= X > X
// <= X X
public static int partition(int[] arr, int L, int R) {
if (L > R) {
return -1;
}
if (L == R) {
return L;
}
int lessEqual = L - 1;
int index = L;
while (index < R) {
if (arr[index] <= arr[R]) {
swap(arr, index, ++lessEqual);
}
index++;
}
swap(arr, ++lessEqual, R);
return lessEqual;
}
荷兰国旗问题
给定一个数组arr,和一个整数num。请把小于num的数放在数组的左边,等于num的数放在中间,大于num的数放在数组的右边。
要求额外空间复杂度O(1),时间复杂度O(N)
// arr[L...R] 玩荷兰国旗问题的划分,以arr[R]做划分值
// <arr[R] ==arr[R] > arr[R]
public static int[] netherlandsFlag(int[] arr, int L, int R) {
if (L > R) { // L...R L>R
return new int[] { -1, -1 };
}
if (L == R) {
return new int[] { L, R };
}
int less = L - 1; // < 区 右边界
int more = R; // > 区 左边界
int index = L;
while (index < more) { // 当前位置,不能和 >区的左边界撞上
if (arr[index] == arr[R]) {
index++;
} else if (arr[index] < arr[R]) {
// swap(arr, less + 1, index);
// less++;
// index++;
swap(arr, index++, ++less);
} else { // >
swap(arr, index, --more);
}
}
swap(arr, more, R); // <[R] =[R] >[R]
return new int[] { less + 1, more };
}
快速排序1.0
使用partition来实现
public static void quickSort1(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process1(arr, 0, arr.length - 1);
}
public static void process1(int[] arr, int L, int R) {
if (L >= R) {
return;
}
// L..R partition arr[R] [ <=arr[R] arr[R] >arr[R] ]
int M = partition(arr, L, R);
process1(arr, L, M - 1);
process1(arr, M + 1, R);
}
快速排序2.0
使用荷兰国旗实现
public static void quickSort1(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process(arr, 0, arr.length - 1);
}
public static void process(int[] arr, int L, int R) {
if (L >= R) {
return;
}
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
int[] equalArea = netherlandsFlag(arr, L, R);
process(arr, L, equalArea[0] - 1);
process(arr, equalArea[1] + 1, R);
}
快速排序3.0
使用非递归方式:使用栈存中间状态
// 快排非递归版本需要的辅助类
// 要处理的是什么范围上的排序
public static class Op {
public int l;
public int r;
public Op(int left, int right) {
l = left;
r = right;
}
}
// 快排3.0 非递归版本
public static void quickSort2(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];
Stack<Op> stack = new Stack<>();
stack.push(new Op(0, el - 1));
stack.push(new Op(er + 1, N - 1));
while (!stack.isEmpty()) {
Op op = stack.pop(); // op.l ... op.r
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));
}
}
}
|