分治思想
分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。
分治和递归很像，分治算法一般都是用递归来实现的。
分治是一种解决问题的处理思想，递归是一种编程技巧。
归并排序 Merge Sort
public class MergeSort {
public static int[] assistArr;
// 归并排序
public static void sort(int[] arr) {
assistArr = new int[arr.length];
assistSort(arr, 0, arr.length - 1);
}
// 递归过程
private static void assistSort(int[] arr, int start, int end) {
if (end - start < 1) {
return;
}
int mid = start + ((end - start) >> 1);
assistSort(arr, start, mid);
assistSort(arr, mid + 1, end);
merge(arr, start, mid, end);
}
// 合并数组
private static void merge(int[] arr, int start, int mid, int end) {
// 把范围内的arr复制到assistArr中
if (end + 1 - start >= 0) {
System.arraycopy(arr, start, assistArr, start, end + 1 - start);
}
int curr = start;
int left = start;
int right = mid + 1;
while (left <= mid && right <= end) {
if (assitArr[left] <= assitArr[right]) {
nums[curr] = assitArr[left];
left++;
} else {
nums[curr] = assitArr[right];
right++;
}
curr++;
}
if (left <= mid) {
for (; left <= mid; left++) {
nums[curr] = assitArr[left];
curr++;
}
}
if (right <= end) {
for (; right <= end; right++) {
nums[curr] = assitArr[right];
curr++;
}
}
}
归并排序分为分解和合并两个过程。
分解是将待排序数组从中间分解为两个数组，直到只剩一个元素无法分解。
合并是将两个数组合成一个有序数组。
归并排序是否是稳定排序，取决于merge合并函数的写法。只要在merge过程中不改变相对位置，归并排序就是稳定的排序算法。
归并排序的时间复杂度在任何情况下都是 O(nlogn)，但它在排序过程中需要使用辅助数组，所以它不是原地排序算法。这是归并排序的致命弱点。
时间复杂度：O(nlogn)
空间复杂度：O(n)
快速排序 Quick Sort
分区
public class QuickSort {
public static void sort(int[] arr) {
recursionSort(arr, 0, arr.length - 1);
}
// 递归函数
private static void recursionSort(int[] arr, int start, int end) {
if (start >= end) {
return;
}
int pivot = partition(arr, start, end);
recursionSort(arr, start, pivot - 1);
recursionSort(arr, pivot + 1, end);
}
// 原地分区函数
private static int partition(int[] arr, int start, int end) {
int pivot = arr[end];
int i = start;
for (int j = start; j < end; j++) {
if (arr[j] < pivot) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
arr[end] = arr[i];
arr[i] = pivot;
return i;
}
}
快速排序利用了分治和递归思想，选择一个分区点，将小于它的数放在它前面，将大于它的数放在它后面。按照这个过程层层递归。
原地分区算法
快排的核心在于原地分区算法：
通过两个游标 i 和 j ，将 A[p...r-1] 分为三个部分：
(1) A[p...i-1] 的元素小于pivot分区点
(2) A[i...j-1] 的元素大于分区点
(3) A[j...r] 是未处理区域。
最差 / 平均 / 最好 时间复杂度：O(n2) / O(nlogn) / O(nlogn)
空间复杂度：O(1)
归并排序 和 快速排序
归并排序 和 快速排序
归并排序和快速排序都用到了分治和递归思想，它们的区别在于：
(1) 归并排序是由下到上的，先处理子问题，再进行合并；归并排序时间复杂度恒为 O(nlogn)，但是需要额外空间。
(2) 快速排序是由上到下的，先进行分区，再处理子问题；快速排序使用了原地分区算法，避免使用额外空间。
