快速排序
快速排序的核心思想是分治，其算法大体可分为三个部分：
- 确定一个分界点
pivot（这个分界点可以任取，一般来说取左端点或中间端点）； - 调整区间，将小于
pivot的数和大于pivot的数分开； - 递归处小于
pivot和大于pivot的部分。
这里我们用到了双指针，即在待排序数组的两端定义两个指针 i 和 j ，i 不断向右移动直到 q[i] > pivot，j 不断向左移动直到 q[j] < pivot，这时将 q[i] 和 q[j] 交换，之后递归进行处理。
这样处理的好处就是 i 左边的数永远是小于 pivot， j 右边的数永远是大于 pivot 。
下面给出快速排序的C++模板：
void quick_sort(int q[], int l, int r){
if(l >= r) return;
int x = q[l + (r - l) / 2], i = l - 1, j = r + 1;
while(i < j){
do i++; while(q[i] < x);
do j--; while(q[j] > x);
if(i < j){
swap(q[i], q[j]);
}
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}（在使用此模板时轻易不要改动，否则容易出现边界问题。。。。）
归并排序
归并排序的核心思想也是分治，其算法大体也可以分为三个部分：
- 确定分界点（这个分界点是数组的中点，不能改变）；
- 递归排序左半部分和右半部分；
- 归并–将两部分数组合二为一。
发现与快速排序不同的地方了吗？
快速排序是先处理再递归，不需要使用额外的空间，而归并排序是先递归再处理，而且需要使用额外的空间。
此算法的核心就是如何将两排序数组合二为一，这里我们依然采用双指针法。我们开辟一个额外的数组空间 tmp ，定义两个指针分别指向已经分割好的两数组的第一个元素，然后对指针所指向的元素的值进行比较，取较小者加入新数组 tmp ，当其中一个数组全部加入后，将另一个数组按顺序加入 tmp 即可。
下面给出归并排序的Java模板：
public static void mergeSort(int[] arr, int l, int r){
if(l >= r){
return;
}
int mid = l + (r - l) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
public static void merge(int[] arr, int l, int mid, int r){
int[] tmp = new int[r - l + 1];
int i = l, j = mid + 1;
int k = 0;
while(i <= mid && j <= r){
if(arr[i] <= arr[j]){
tmp[k++] = arr[i++];
}else{
tmp[k++] = arr[j++];
}
}
while(i <= mid){
tmp[k++] = arr[i++];
}
while(j <= r){
tmp[k++] = arr[j++];
}
for(int m = l, n = 0; m <= r; ++m, ++n){
arr[m] = tmp[n];
}
}关于归并排序，有一个非常经典的小和问题：
在一个数组中， 每一个数左边比当前数小的数累加起来， 叫做这个数组的小和。 求一个数组
的小和。
例子：
[1,3,4,2,5]
1左边比1小的数， 没有；
3左边比3小的数， 1；
4左边比4小的数， 1、 3；
2左边比2小的数， 1；
5左边比5小的数， 1、 3、 4、 2；
所以小和为1+1+3+1+1+3+4+2=16 思路：
通过归并排序进行求解，每次merge都能计算出一次小和，当要将两个排好序的两个子序列进行合并时，如果左边的当前值比右边的当前值要小，则说明这个值比右边的所有值都要小，所有就产生了arr[i] * (r - l + 1)个小和，通过这种进行计算，直到计算完成。
题解：
public static int merge(int[] arr, int l, int mid, int r){
int[] tmp = new int[r - l + 1];
int i = l, j = mid + 1;
int res = 0, k = 0;
while(i <= mid && j <= r){
if(arr[i] < arr[j]){
res += (r - j + 1) * arr[i];
tmp[k++] = arr[i++];
}else{
tmp[k++] = arr[j++];
}
}
while(i <= mid){
tmp[k++] = arr[i++];
}
while(j <= r){
tmp[k++] = arr[j++];
}
for(int m = l, n = 0; m <= r; ++m, ++n){
arr[m] = tmp[n];
}
return res;
}
public static int mergeSort(int[] arr, int l, int r){
if(l >= r){
return 0;
}
int mid = l + (r - l) / 2;
return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
}
public static void main(String[] args) {
int[] arr = {1, 3, 4, 2, 5};
int res = mergeSort(arr, 0, arr.length - 1);
System.out.println(res);
}快速排序和归并排序的核心思想都是分治，从另一种层面上理解，快速排序实质上就是一个二叉树的前序遍历，读到这里相信很多小伙伴是理解不了的，我们可以这样理解：快排的步骤是先构造一个分界点，然后再递归的处理左右子数组，这不就是二叉树的前序遍历（根左右）吗？同理，我们可以得出归并排序实质上就是一个二叉树的后序遍历。
这两个算法还是比较重要的，建议在理解的基础上背一手模板就很舒服。
