前言
本文主要介绍了两种排序，归并排序和快速排序，归并排序有递归和非递归2种方式实现，快速排序的升级版为荷兰国旗问题。
1.归并排序
归并排序：
1)整体是递归，左边排好序+右边排好序+ merge让整体有序；
2)让其整体有序的过程里用了排外序方法；
3)利用master公式来求解时间复杂度；
4)可以用非递归实现。
递归方式举例如下：
实现如下：
// 递归方法实现 public static void mergeSort1(int[] arr) { if (null == arr || arr.length < 2) { return; } process(arr, 0, arr.length - 1); } public static void process(int[] arr, int L, int R) { // base case 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) { help[i++] = arr[p1++]; } while (p2 <= R) { help[i++] = arr[p2++]; } System.arraycopy(help, 0, arr, L, help.length); }
非递归方式举例如下：
实现如下：
// 非递归方法实现 public static void mergeSort2(int[] arr) { if (null == arr || arr.length < 2) { return; } int N = arr.length; int mergeSize = 1; // 步长 while (mergeSize < N) { int L = 0; // 当前左组的第一个位置 while (L < N) { if (L + mergeSize >= N) { break; } int M = L + mergeSize - 1; int R = Math.min(M + mergeSize, N - 1); merge(arr, L, M, R); L = R + 1; } // 防止溢出 if (mergeSize > N / 2) { break; } mergeSize <<= 1; } }
现在计算时间复杂度：
递归方式：
非递归方式：
综上，归并排序复杂度：T(N)= 2*T(N/2)+ O(N^1)
根据master可知时间复杂度为O(N*logN)
merge过程需要辅助数组，所以额外空间复杂度为O(N)
归并排序的实质是把比较行为变成了有序信息并传递，比O(N^2)的排序快
相比于冒泡排序、选择排序和插入排序O(N2)的时间复杂度，归并排序O(N*LogN)的时间复杂度优化了很多，这是因为减少了比较次数。
用常见面试题再深入理解一下归并排序的精髓。
在一个数组中，一个数组左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和。
举例：[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的时候，如下：
原理是：思路转换，从计算一个数左边更小的数之和转换为一个数右边更大的数之和。
实现如下：
public class SmallSum { public static int smallSum(int[] arr) { if (null == arr || arr.length < 2) { return 0; } return process(arr, 0, arr.length - 1); } public static int process(int[] arr, int l, int r) { if (l == r) { return 0; } int mid = l + (r - l) >> 1; return process(arr, l, mid) + process(arr, mid+1, r) + merge(arr, l, mid, r); } public static int merge(int[] arr, int l, int mid, int r) { int[] help = new int[r - l + 1]; int i = 0; int p1 = l, p2 = mid + 1; int res = 0; while (p1 <= mid && p2 <= r) { res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0; help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]; } while (p1 <= mid) { help[i++] = arr[p1++]; } while (p2 <= r) { help[i++] = arr[p2++]; } System.arraycopy(help, 0, arr, l, help.length); return res; } }
扩展：在一个数组中求所有的降序对。
如下：
也就是求一个数右边有多少个数比它小，或者说，左边有多少个数比它大。
图示如下：
