小知识点补充

1. 对于求中点mid = (L+R)/2，若数组开的长度比较大，L+R可能会溢出。所以可以写成：mid = L+(R-L)/2。或者更简化的，mid = L+((R-L) >> 1)。此处右移一位等于除以二，就是求中点的意思，并且右移比直接除以2要快。

2. master公式：T(N) = a * T(N/b) + o(N^d)，其中，N为数据规模，a为调用子问题次数，N/b为子问题的规模（所有子问题规模必须相同），o为除了子问题的调用之外，剩下过程的时间复杂度。d=log(b,a)

归并排序

public static void process(int[] arr, int L, int R) {if (L == R) {return;}int mid = L + ((R - L) >> 1);process(arr, L, mid);process(arr, mid + 1, R);merge(arr, L, mid, R);
}public static void merge(int[] arr, int L, int M, int R) {int[] help = new int[R - L + 1]; // 辅助数组int i = 0;int p1 = L;int p2 = M + 1;while (p1 <= M && p2 <= R) {help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];}while (p1 <= M) { //总会有一个时刻，p1或者p2越界，如果p1没越界，就把p1剩下的内容拷贝到helphelp[i++] = arr[p1++];}while (p2 <= R) { //这两个while只有一个会发生help[i++] = arr[p2++];}for (i = 0; i < help.length; i++) {arr[L + i] = help[i];}
}

快速排序

// arr[1..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); // < 区quickSort(arr, p[1] + 1, R); // > 区}
}// 这是一个处理arr[1..r]的函数
// 默认以arr[r]做划分， arr[r] -> p    <p    ==p    >p
// 返回等于区域（左边界，右边界），所以返回一个长度为2的数组res，res[0] res[1]
public 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 };
}

堆排序

public static void heapSort(int[] arr) {if (arr == null || arr.length < 2) {return;}for (int i = 0; i < arr.length; i++) {heapInsert(arr, i);}int heapSize = arr.length;swap(arr, 0, --heapSize);while (heapSize > 0) {heapify(arr, 0, heapSize);swap(arr, 0, --heapSize);}
}// 某个数现在处在index位置，往上继续移动
public static void heapInsert(int[] arr, int index) {while (arr[index] > arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index = (index - 1)/2;}
}// 某个数在index位置，能否往下移动
public static void heapify(int[] arr, int index, int heapSize) {int left = index * 2 + 1; // 左孩子的下标while (left < heapSize) { // 下方还有孩子的时候// 两个孩子中，谁的值大，把下标给largestint largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 :left;// 父和较大的孩子之间，谁的值大，把下标给largestlargest = arr[largest] > arr[index] ? largest :index;if (largest == index) {break;}swap(arr, largest, index);index = largest;left = index * 2 + 1;}  
}