文章目录
- 1. 归并排序
- 1.1 归并
- 1.2 递归
- 1.3 迭代
- 2. 数组单调和
- 3. 逆序对
1. 归并排序
归并排序是建立在归并操作的基础上的，效率为O(nlogn)。
归并排序的实现分为递归实现与非递归(迭代)实现。
1.1 归并
归并(Merge)操作是指将两个已经排序好的序列，合并成一个有序序列。
这个合并是相对比较简单的，因为两个序列是事先已经排序好的了，每个序列中的元素放到新序列中的顺序不会改变，只是两个序列的元素可能会交替出现。
比如我们要归并序列A[2, 3, 5, 6]和序列B[1, 4, 8, 9]，按照我们平时的逻辑，我们会从最左边开始，找一个最小的，然后依次进行下去。比如这个例子，我们最小会找出1，为什么，因为我们知道，最小的数一定在最左边，于是看2和1，发现1比较小，所以把它挑出来放到第一个。然后我们会把2挑出来，因为现在1挑出来之后，最左边的数的2和4，显然2比较小，于是我们挑出2。接下来同理，3和4比较，挑出3；4和5比较，挑出4；5和8比较，挑出5；6和8比较，挑出6；最后左边的四个数都被我们挑出来了，而右边还剩下8和9，这时候已经没必要挑了，剩下的数直接往后面扔就行了，因为8比6（A中的最后一个数）大，自然也比A的其他所有数都大，而B本来自身也是排好序的，所以后面的数一定比前面的大。所以我们就得出了序列[1, 2, 3, 4, 5, 6, 8, 9]。
按照上面的思路，把它反映到代码上面，其实也是不难的。
- 首先，因为挑出来的数需要找个地方放，所以需要新开一个空间用来放这些数（合并序列）；
- 然后比较的过程就是用两个下标分别指向两个序列的起始位置，然后比较两个下标所在元素的大小，挑出较小的元素放到合并序列，相应的下标往右边移动，重复该操作直到其中一个序列结束为止；
- 最后把另一个数组的剩余数直接拿出来放到合并序列即可。
代码如下：
/*
* 合并两个已排序的序列arr[start...mid]和arr[mid + 1...end]
*/
public static void merge(int[] arr, int start, int mid, int end) {
// 1. 申请辅助空间
int temp[] = new int[end - start + 1];
// 2. 从左到右进行比较
int i = start; // 指向第一个序列的开始
int j = mid + 1; // 指向第二个序列的开始
int index = 0; // 辅助空间的下标
while(i <= mid && j <= end) { // 循环直至其中一个序列结束
// 挑出较小的数
if (arr[i] <= arr[j]) {
temp[index++] = arr[i++];
} else {
temp[index++] = arr[j++];
}
}
// 3. 将剩下的数放到合并序列的末尾
while(i <= mid) {
temp[index++] = arr[i++];
}
while(j <= end) {
temp[index++] = arr[j++];
}
// 将辅助空间的值复制到原数组
for(int k = 0; k < temp.length; k++) {
arr[start++] = temp[k];
}
} 复制
1.2 递归
归并排序的一种实现方式是使用递归实现。这是分治策略的典型应用。
先把一个大问题分为小问题，小问题又与原先的大问题有相同的结构，可以继续分解为小问题，直到分解为可以迅速解决的足够小的问题，然后小问题的解决就可以反过来解决较大的问题，最终最大的那个问题（原问题）得以解决。
在这一具体的例子中，大问题就是如何把一个序列排序。要如何把这个问题分解为小问题呢？从上面提到的归并操作入手。把这个序列分为两半，如果这两个序列是排序好的就好了，这样就可以使用归并操作对他们进行合并了。但可惜这两个序列并不是排好序的，诶？这不就是子问题吗？两个较小的序列也要排序，与原问题类似，只不过数变少了。然后子问题再用同样的思路解决，就是分成两半，使用归并。一直分下去，没完没了了？并不会，最终会分到一个子序列只有一个数，可以看成已经是排好序的了，不能也不需要再分。这样一来，最小的子问题可以得到解决，那么大问题自然就可以解决了。
代码实现如下：
/*
* 使用递归的方法对序列arr[start...end]进行归并排序
*/
public static void mergeSortRecursion(int[] arr, int start, int end) {
if (start == end) { // 待排序的序列只有一个数，则不需要排序，开始回溯
return;
}
// 分解为两个较小的子问题，将序列分为两个序列，对两个子序列进行排序
int mid = (start + end) / 2;
mergeSortRecursion(arr, start, mid);
mergeSortRecursion(arr, mid + 1, end);
// 两个子问题解决后，再对已排序的两个子序列进行归并操作
merge(arr, start, mid, end);
} 复制
1.3 迭代
迭代的方法跟递归的思路其实是差不多的，都是使用两两归并的方式进行排序，只不过迭代不像递归一样从大问题出发，而是自底向上解决问题，也就是先把最短的序列归并，然后归并的序列长度再依次翻倍，最终完成排序。代码如下：
/*
* 使用迭代的方法对序列arr[start...end]进行归并排序
*/
public static void mergeSortIteration(int[] arr, int len) {
int start, mid, end;
for(int i = 1; i < len; i *= 2) {
start = 0;
// 两两归并，直到后一个子数组不存在
while(start + i < len) {
mid = start + i - 1;
end = mid + i < len ? mid + i : len - 1;
merge(arr, start, mid, end);
start = end + 1; // 归并下一对数组
}
}
} 复制
2. 数组单调和
数组单调和，也叫数组小和，定义如下：
数组小和的定义如下：例如，数组s=[1,3,5,2,4,6]
在s[0]的左边小于或等于s[0]的数的和为0
在s[1]的左边小于或等于s[1]的数的和为1
在s[2]的左边小于或等于s[2]的数的和为1+3=4
在s[3]的左边小于或等于s[3]的数的和为1
在s[4]的左边小于或等于s[4]的数的和为1+3+2=6
在s[5]的左边小于或等于s[5]的数的和为1+3+5+2+4=15
所以s的小和为0+1+4+1+6+15=27
给定一个数组s，实现函数返回s的小和。
参考文章：数组小和（单调和）
数组单调和的定义具体见这里。
要解决这个问题，容易想到的就是二重循环暴力破解，但是这明显是没有办法的办法。其实这可以利用上面的归并排序的方法进行求解。
首先应该明确两个规律：
（1）对于一个序列里面的子序列，若该子序列的单调和已经求出，那么其内部的顺序不会影响整个序列的单调和。这是显而易见的，因为子序列内部顺序的改变，并不会影响其中的元素与整个序列其他元素的前后大小关系，所以不会影响单调和。
（2）在归并的过程中，如果遇到左边序列的一个数A比右边序列的某个数B小，那么A也一定小于B的右边的所有数。这是由待归并的子序列已经排好序的性质决定的。
根据以上两条规律，可以对归并排序的代码做如下调整，使其可以用来求数组单调和：
public static int getSmallSum(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
return mergeSortRecursion(arr, 0, arr.length - 1);
}
/*
* 合并两个已排序的序列arr[start...mid]和arr[mid + 1...end]
*/
public static int merge(int[] arr, int start, int mid, int end) {
int smallSum = 0; // 用以累计数组小和
int temp[] = new int[end - start + 1]; // 申请辅助空间
int index = 0; // 辅助空间的下标
int i = start; // 指向第一个序列的开始
int j = mid + 1; // 指向第二个序列的开始
while(i <= mid && j <= end) { // 循环直至其中一个序列结束
if (arr[i] <= arr[j]) { // 挑出较小的数
smallSum += arr[i] * (end - j + 1); // 根据第二条规律
temp[index++] = arr[i++];
} else {
temp[index++] = arr[j++];
}
}
// 将剩下的数放到合并序列的末尾
while(i <= mid) {
temp[index++] = arr[i++];
}
while(j <= end) {
temp[index++] = arr[j++];
}
// 将辅助空间的值复制到原数组
for(int k = 0; k < temp.length; k++) {
arr[start++] = temp[k];
}
return smallSum;
}
/*
* 使用递归的方法对序列arr[start...end]进行归并排序
*/
public static int mergeSortRecursion(int[] arr, int start, int end) {
if (start == end) { // 待排序的序列只有一个数，则不需要排序，开始回溯
return 0;
}
// 分解为两个较小的子问题，将序列分为两个序列，对两个子序列进行排序
int mid = (start + end) / 2;
int left = mergeSortRecursion(arr, start, mid);
int right = mergeSortRecursion(arr, mid + 1, end);
// 两个子问题解决后，再对已排序的两个子序列进行归并操作
int whole = merge(arr, start, mid, end);
return left + right + whole;
} 复制
3. 逆序对
在一个序列中，若前面的一个数大于后面一个数字，则这两个数字组成一个逆序对。
问题：给定一个数组，求出其逆序对个数。
这个问题也可以使用上面类似的方法求解，只不过是在左边的数大于右边时逆序对的数量累加。归并操作代码如下：
/*
* 合并两个已排序的序列arr[start...mid]和arr[mid + 1...end]
*/
public static int merge(int[] arr, int start, int mid, int end) {
int inverseNum = 0; // 用以累计数组小和
int temp[] = new int[end - start + 1]; // 申请辅助空间
int index = 0; // 辅助空间的下标
int i = start; // 指向第一个序列的开始
int j = mid + 1; // 指向第二个序列的开始
while(i <= mid && j <= end) { // 循环直至其中一个序列结束
if (arr[i] <= arr[j]) { // 挑出较小的数
temp[index++] = arr[i++];
} else {
inverseNum += mid - i + 1;
temp[index++] = arr[j++];
}
}
// 将剩下的数放到合并序列的末尾
while(i <= mid) {
temp[index++] = arr[i++];
}
while(j <= end) {
temp[index++] = arr[j++];
}
// 将辅助空间的值复制到原数组
for(int k = 0; k < temp.length; k++) {
arr[start++] = temp[k];
}
return inverseNum;
} 复制
逆序对可以用来判断一个八数码问题是否有解，思想是：一个八数码，对其进行进行移位操作，不会改变其逆序对总数的奇偶性。所以通过求初始八数码和目标八数码的逆序对，判断其奇偶性是否相同，就可判断是否可以到达目标状态，即是否有解。