网站做成软件,建筑设计参考网站,企业数据查询网站,建设工程质量协会网站归并排序
算法思想
将数组元素不断地拆分#xff0c;直到每一组中只包含一个元素#xff0c;单个元素天然有序。之后用归并的方式收集跨组的元素#xff0c;最终形成整个区间上有序的序列。
稳定性分析
归并排序是稳定的#xff0c;拆分数组时会自然地将元素分成有先后…归并排序
算法思想
将数组元素不断地拆分直到每一组中只包含一个元素单个元素天然有序。之后用归并的方式收集跨组的元素最终形成整个区间上有序的序列。
稳定性分析
归并排序是稳定的拆分数组时会自然地将元素分成有先后顺序的子数组在归并的过程中如果遇到相等的值优先收集早出现的子数组中的那个即可。
具体实现
递归
// 注意预先定义辅助数组防止递归层数深的情况下花大量时间空间去开数组
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(N ^ 2) O(N2) 量级的方法优化到 O ( N l o g N ) O(NlogN) O(NlogN) 这个级别。 当然本质上来说还是空间换时间这样的操作很明显需要 O ( N ) O(N) O(N) 量级的额外空间。
从使用上来说归并排序一般不会成为手写排序的选择。但是归并分治则是很多问题的优秀解决方案需要注意它的使用前提和具体实现。
后记
使用 Leetcode 912. 排序数组 进行测试归并排序能够比较高高效地完成任务略逊于计数排序和基数排序不过其实题目要求使用尽可能少的额外空间归并排序肯定不属于首选的方案。
