import java.util.Arrays;
public class QuickSort {
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
sort(arr, 0, arr.length - 1);
}
public static void sort(int[] arr, int L, int R) {
if (L < R) {
// 随机比较数排序
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
int book[] = quick(arr, L, R);
// 小于区域排序
sort(arr, L, book[0] - 1);
// 大于区域排序
sort(arr, book[1] + 1, R);
}
}
public static int[] quick(int[] arr, int L, int R) {
int less = L - 1;
int more = R;
while (L < more) {
if (arr[L] < arr[R]) {
swap(arr, ++less, L++);
} else if (arr[L] > arr[R]) {
swap(arr, --more, L);
} else
L++;
}
swap(arr, more, R);
return new int[] { less + 1, more };
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int[] arr = { 2, 6, 4, 7, 5, 6, 8, 2 };
quickSort(arr);
System.out.println(Arrays.toString(arr));
}
}