Java排序之归并排序
1. 简介
归并排序的算法是将多个有序数据表合并成一个有序数据表。如果参与合并的只有两个有序表，则成为二路合并。对于一个原始的待排序数列，往往可以通过分割的方法来归结为多路合并排序。
2. 归并排序思路
将长度为n的待排序数组看做是由n个有序长度为1的数组组成将其两两合并，得到长度为2的有序数组然后再对这些子表进行合并，得到长度为4的有序数组重复上述过程，一直到最后的子表长度为n也就完成了排序
3. 代码实例
归并排序有两种实现方式：递归和非递归。在看归并排序的代码之前先来看一下怎么和合并两个有序数组：
// 基础，合并两个有序数组
public static int[] merge2Arr(int[] arr1, int[] arr2) {
int len1 = arr1.length;
int len2 = arr2.length;
int[] res = new int[len1 + len2]; // 使用一个数组用来存储排好序的数组
int i = 0, j = 0, k = 0;
while(i < len1 && j < len2) {
res[k++] = arr1[i] < arr2[j]? arr1[i++] : arr2[j++];
}
while(i < len1) {
res[k++] = arr1[i++];
}
while(j < len2) {
res[k++] = arr2[j++];
}
return res;
}
归并排序的递归实现：
// 归并排序，递归实现
public void sortMergeRecursion(int[] nums) {
sortMergeRecursionHelper(nums, 0, nums.length - 1);
}
public void sortMergeRecursionHelper(int[] nums,int left, int right) {
if(left == right) return; // 当待排序的序列长度为1时，递归开始回溯，进行merge
int middle = left + (right - left) / 2;
sortMergeRecursionHelper(nums, left, middle);
sortMergeRecursionHelper(nums, middle + 1, right);
mergeArr(nums, left, middle, right);
}
public void mergeArr(int[] nums, int left, int middle, int right) {
int[] tem = new int[right - left + 1];
int i = left, j = middle + 1, k = 0;
while(i <= middle && j <= right) {
tem[k++] = nums[i] < nums[j]? nums[i++] : nums[j++];
}
while(i <= middle) {
tem[k++] = nums[i++];
}
while(j <= right) {
tem[k++] = nums[j++];
}
// 将辅助数组数据写入原数组
int index = 0;
while(left <= right) {
nums[left++] = tem[index++];
}
}
归并排序的非递归实现（迭代）：
// 归并排序，非递归实现(迭代)
public void sortMergeIteration(int[] nums) {
int len = 1; // 初始排序数组的长度
while(len < nums.length) {
for(int i = 0; i < nums.length; i += len * 2) {
sortMergeIterationHelper(nums, i, len);
}
len *= 2; // 每次将排序数组的长度*2
}
}
/**
* 辅助函数
* @param nums 原数组
* @param start 从start位置开始
* @param len 本次合并的数组长度
*/
public void sortMergeIterationHelper(int[] nums, int start, int len) {
int[] tem = new int[len * 2];
int i = start;
int j = start + len;
int k = 0;
while(i < start + len && (j < start + len + len && j < nums.length)) {
tem[k++] = nums[i] < nums[j]? nums[i++] : nums[j++];
}
while(i < start + len && i < nums.length) { // 注意：这里i也可能超出长度
tem[k++] = nums[i++];
}
while(j < start + len + len && j < nums.length) {
tem[k++] = nums[j++];
}
int right = start + len + len;
int index = 0;
while(start < nums.length && start < right) {
nums[start++] = tem[index++];
}
}
归并排序的时间复杂度为O(n*log2n),空间复杂度为O(n)
归并排序是一种稳定的排序方法。
参考：
https://blog.csdn.net/y999666/article/details/50942604
转载于:https://www.cnblogs.com/scuwangjun/p/9144543.html
相关资源：插入排序和归并排序的实现java
