常见排序算法总结 (三) - 归并排序与归并分治

归并排序

算法思想

将数组元素不断地拆分，直到每一组中只包含一个元素，单个元素天然有序。之后用归并的方式收集跨组的元素，最终形成整个区间上有序的序列。

稳定性分析

归并排序是稳定的，拆分数组时会自然地将元素分成有先后顺序的子数组，在归并的过程中如果遇到相等的值，优先收集早出现的子数组中的那个即可。

具体实现

递归

// 注意预先定义辅助数组，防止递归层数深的情况下花大量时间空间去开数组
public static int MAX_N = 50010;
public static int[] temp = new int[MAX_N];// 归并，用于将已经有序的两个数组合并成更大的有序数组
private void merge(int[] arr, int left, int mid,  int right) {int index1 = left, index2 = mid + 1, index = left;// 两个数组都有剩余元素，每次收集值较小的元素while(index1 <= mid && index2 <= right) {temp[index++] = arr[index1] <= arr[index2] ? arr[index1++] : arr[index2++];}// 其中一个数组为空，将另一个数组剩余的所有元素都添加到结果数组的末尾while(index1 <= mid) {temp[index++] = arr[index1++];}while(index2 <= right) {temp[index++] = arr[index2++];}// 结果回写到原数组System.arraycopy(temp, left, arr, left, right - left + 1);
}// 归并排序
private void mergeSort(int[] arr, int left, int right) {// 左右端点相同，数组中只有单个元素认为天然有序if (left == right) {return;}int mid = left + ((right - left) >>> 1); // 计算区间中点作为划分数组的依据// 递归地对左半边数组进行排序mergeSort(arr, left, mid);// 递归地对右半边数组进行排序mergeSort(arr, mid + 1, right);// 归并收集结果merge(arr, left, mid, right);
}

非递归

// 注意预先定义辅助数组，防止递归层数深的情况下花大量时间空间去开数组
public static int MAX_N = 50010;
public static int[] temp = new int[MAX_N];// 归并方法，用于将已经有序的两个数组合并成更大的有序数组
private void merge(int[] arr, int left, int mid,  int right) {int index1 = left, index2 = mid + 1, index = left;// 两个数组都有剩余元素，每次收集值较小的元素while(index1 <= mid && index2 <= right) {temp[index++] = arr[index1] <= arr[index2] ? arr[index1++] : arr[index2++];}// 其中一个数组为空，将另一个数组剩余的所有元素都添加到结果数组的末尾while(index1 <= mid) {temp[index++] = arr[index1++];}while(index2 <= right) {temp[index++] = arr[index2++];}// 结果回写到原数组System.arraycopy(temp, left, arr, left, right - left + 1);
}// 归并排序
private void mergeSort(int[] arr) {int n = arr.length;// 根据步长来迭代，每一轮扩大一倍for (int left, mid, right, step = 1; step < n; step <<= 1) {left = 0; // 左端点从 0 开始while (left < n) {mid = left + step - 1; // 计算区间中点的位置// 另一半区间无法构成，直接进行下一轮if (mid >= n - 1) {break;}// 数组内剩余元素不一定够填满右半边数组，右端点要根据情况来取值right = Math.min(left + (step << 1) - 1, n - 1);merge(arr, left, mid, right);// 移动指针，准备归并右半边数组left = right + 1;}}
}

归并分治

分治是一种算法思想，归并分治顾名思义就是涉及到了归并的分治策略。这部分内容其实和排序关系不大，但是作为归并应用的扩展放在一起整理比较合适的。

算法思想

如果一个问题满足两个条件，那么大概率可以使用归并分治解决：

全局的结果相当于划分成两部分之后，左半边、右半边与跨左右三部分的结果的并集，也就是这个问题可以总中间拆分成子问题。
如果拆分之后小范围上有序，能够使得计算跨左右的答案时更方便。

实践案例：Leetcode 493. 翻转对

递归

class Solution {// 注意预先定义辅助数组，防止递归层数深的情况下花大量时间空间去开数组public static int MAX_N = 50010;public static int[] temp = new int[MAX_N];public int reversePairs(int[] nums) {return reversePairs(nums, 0, nums.length - 1);}// 重载一个同名方法，将它改造成方便递归的形式private int reversePairs(int[] nums, int left, int right) {// 只有一个元素的情况下没有答案if(left == right) {return 0;}int mid = left + ((right - left) >>> 1);// 结果等于左半边、右半边与跨左右的结果的并集return reversePairs(nums, left, mid) + reversePairs(nums, mid + 1, right) + merge(nums, left, mid, right);}private int merge(int[] nums, int left, int mid,  int right) {int res = 0;// 当前跨小范围的情况下，更小范围内已经有序for(int i = left, j = mid + 1; i <= mid; i++) {// 确定了当前轮 j 的位置之后，这个指针不会回退，这也是提升性能的根本原因while(j <= right && (long) nums[i] > (long) 2 * nums[j]) {j++;}res += j - mid - 1;}// 常规归并流程int index1 = left, index2 = mid + 1, index = left;while(index1 <= mid && index2 <= right) {temp[index++] = nums[index1] <= nums[index2] ? nums[index1++] : nums[index2++];}while(index1 <= mid) {temp[index++] = nums[index1++];}while(index2 <= right) {temp[index++] = nums[index2++];}System.arraycopy(temp, left, nums, left, right - left + 1);return res;}
}

非递归

class Solution {// 注意预先定义辅助数组，防止递归层数深的情况下花大量时间空间去开数组public static int MAX_N = 50010;public static int[] temp = new int[MAX_N];public int reversePairs(int[] nums) {int res = 0;int n = nums.length;for (int left, mid, right, step = 1; step < n; step <<= 1) {left = 0;while (left < n) {mid = left + step - 1;if (mid >= n - 1) {break;}right = Math.min(left + (step << 1) - 1, n - 1);res += merge(nums, left, mid, right); // 累计每次归并的结果left = right + 1;}}return res;}private int merge(int[] nums, int left, int mid,  int right) {int res = 0;// 当前跨小范围的情况下，更小范围内已经有序for(int i = left, j = mid + 1; i <= mid; i++) {// 确定了当前轮 j 的位置之后，这个指针不会回退，这也是提升性能的根本原因while(j <= right && (long) nums[i] > (long) 2 * nums[j]) {j++;}res += j - mid - 1;}// 常规归并流程int index1 = left, index2 = mid + 1, index = left;while(index1 <= mid && index2 <= right) {temp[index++] = nums[index1] <= nums[index2] ? nums[index1++] : nums[index2++];}while(index1 <= mid) {temp[index++] = nums[index1++];}while(index2 <= right) {temp[index++] = nums[index2++];}System.arraycopy(temp, left, nums, left, right - left + 1);return res;}
}

梳理总结

分治是一种通过不断划分来减小问题规模，而归并是用来收集得到全局结果的方法。上面的例子所使用的都是一分为二的做法，其实每一轮可以划分成更多子问题，演变成多路归并。
正是上面这种不停划分的过程，使得无论是归并排序还是归并分治，都能有效地将暴力搜索需要 $O(N ^ 2)$ 量级的方法，优化到 $O (Nl o g N)$ 这个级别。
当然，本质上来说还是空间换时间，这样的操作很明显需要 $O (N)$ 量级的额外空间。