【算法】归并排序及其应用
- 2020 年 3 月 29 日
- 筆記
一、归并排序
归并排序的思路
归并排序是典型的分治算法，把一个数组的排序，分为两个子序列的排序，然后将两个有序序列合并。以上就是整个算法的核心。整个过程如下图所示（图侵删）：
归并排序图解
具体实现如下：
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; }
