一、归并排序
归并排序的思路
归并排序是典型的分治算法，把一个数组的排序，分为两个子序列的排序，然后将两个有序序列合并。以上就是整个算法的核心。整个过程如下图所示（图侵删）：
归并排序图解
具体实现如下：
public static void merge(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int l, int r) {
if (l == r) {
return;
}
// int mid = (l + r) / 2;
// 等同于以上写法，这样的好处是防止溢出
int mid = l + ((r - l) >> 1);
mergeSort(arr, l, mid);
mergeSort(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++];
}
// 将临时数组中的内容拷贝回原数组中
// （原left-right范围的内容被复制回原数组）
for(i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
}
二、归并排序的延伸算法
1、小和问题
题目描述如下：
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。
求一个数组的小和。
例子:
[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
解题思路
把问题转化为在有序数组下，对于下标为i的数，找出比i大的个数后，相乘再相加。因此，我们需要进行归并排序，然后根据有序数组的特性，分布榨出小和
代码实现
public static int smallSum(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
return mergeSort(arr, 0, arr.length - 1);
}
public static int mergeSort(int[] arr, int l, int r) {
if (l == r) {
return 0;
}
// int mid = (l + r) / 2;
// 等同于以上写法，这样的好处是防止溢出
int mid = l + ((r - l) >> 1);
return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
}
/// 合并两个有序数组为新的有序数组
public static int 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;
int res = 0;
// 逐一判断左指针指向的数和右指针指向的数
// 小的加入到数组中
while (p1 <= m && p2 <= r) {
// 这里是归并排序算法的基础上添加的代码
res += arr[p1] < arr[p2] ? arr[p1] * (r - p2 + 1) : 0;
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
// 将剩余的数加入到数组中
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
// 将临时数组中的内容拷贝回原数组中
// （原left-right范围的内容被复制回原数组）
for(i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
return res;
}
可以发现，相比归并排序算法，我们只在merge的过程中，进行了小和的计算。因此求出了每一个子序列的小和，全部子序列的小和相加即为整个序列的小和。
2、逆序对
在一个数组中，左边的数如果比右边的数大，则折两个数构成一个逆序对，请打印所有逆序对。
例如：1, 5, 6, 3, 2的逆序对为(3,2), (5,2), (6,2), (5,3), (6,3)
算法思路
跟上一道题一样，在merge的基础上进行拓展。假设在一次merge的过程中，左序列的p1大于右序列的p2，那么，根据子序列有序的特性，我们可以知道p1~mid的数，均大于p2，因此可以组成mid - p1 + 1个逆序对。因此找出每个子merge过程的逆序对，合并后，即可获得所有的逆序对
实现代码
public static int reversePart(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
return mergeSort(arr, 0, arr.length - 1);
}
public static int mergeSort(int[] arr, int l, int r) {
if (l == r) {
return 0;
}
int mid = (l + r) / 2;
return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
}
public static int merge(int[] arr, int l, int m, int r) {
int p1 = l;
int p2 = m + 1;
int[] help = new int[r - l + 1];
int i = 0;
int count = 0;
while (p1 <= m && p2 <= r) {
if (arr[p1] <= arr[p2]) {
help[i++] = arr[p1++];
}else {
// 左 > 右，说明以p1为界限，p1~m之间的数据都大于右
// 因此可推出逆序数的公式为 m - p1 + 1
for(int k = p1; k <= m; k++) {
System.out.print("(" + arr[k] + "," + arr[p2] + "), ");
}
count += m - p1 + 1;
help[i++] = arr[p2++];
}
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
// 拷贝
for(i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
return count;
}
