快速排序
概念：
任取待排序元素序列中的某个元素（例如取第一个元素）作为基准，按照该元素的排序码大小，将整个元素序列划分为左右两个子序列：左侧子序列中的排序码都小于基准元素的排序码，右侧子序列中所有元素的排序码都大于或等于基准元素的排序码。基准元素则排在两个子序列中间（这也是该元素最终应安放的位置）。然后分别对这两个子序列重复实行上述方法（递归过程），直到所有元素都排在相应位置上为止。
简单来说：基于交换思想对冒泡排序的优化，也称为分区的交换排序。核心是划分，可以用递归来实现。
核心代码：
public class QuickSort { public static void quickSort(int[] arr) { if (arr == null || arr.length < 2) { return; } quickSort(arr, 0, arr.length - 1); } // arr[l...r] 排好序 public static void quickSort(int[] arr, int L, int R) { if (L < R) { //随机取一个值 swap(arr, L + (int) (Math.random() * (R - L + 1)), R); int[] p = partition(arr, L, R); quickSort(arr, L, p[0] - 1);// p【0】 --》等于区域的左边界 减一则为小于区域的 quickSort(arr, p[1] + 1, R);// p【1】 --》 等于区域右边界 } } /** * * 这是一个处理arr【l...r】的函数 * 默认以arr【r】 做划分，arr【r】--》p p《 ==p 》p * 返回等于区域(左边界，右边界) 所以返回一个长度为2的数组res，res【0】，res【1】 * */ private static int[] partition(int[] arr, int L, int R) { int less = L - 1; //< 区右边界 int more = R; // >区左边界 while (L < more) {// L表示当前数的位置，arr[R] -> 划分值 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}; } private static void swap(int[] arr, int i, int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } }
图例
荷兰国旗问题
网络异常，图片无法展示
|
给定一个数组arr和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边，要求额外空间复杂度O（1），时间复杂度O（N）
有了上面的快速排序的了解，将数组分成三块。在左边设置了一个大于等于区，这个问题可以在左边设置一个小于区，在右边设置一个大于区，不断向中间逼近，最终中间就是相等的数字，然后跟上面快排的思想基本一致，代码如下：
private static int[] partition(int[] arr, int L, int R) { int less = L - 1; //< 区右边界 int more = R; // >区左边界 while (L < more) {// L表示当前数的位置，arr[R] -> 划分值 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}; } //比较排序 private static void swap(int[] arr, int i, int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; }
总结：类似C语言的双指针的移动，当小于num时，则左指针带着区域移动。
、、、
