算法之10 | 归并排序
归并排序算法完全遵循分治模式。直观上其操作如下：
（1）分解：分解等排序的n个元素的序列成各具n/2个元素的两个子序列；
（2）解决：使用归并排序递归地排序两个子序列；
（3）合并：合并两个已排序的子序列以产生已排序的答案。
当待排序的序列长度为1时，递归"开始回升"，在这种情况下不根做任何工作，因为长度为1的每个序列都已排好序。
归并排序算法的关键操作是"合并"步骤中两个已排序序列的合并。我们可以通过调用一个辅助过程Merge(A, p, q, r)来完成合并，其中A是一个数组，p、q和r是数组下标，满足 p ≤ q < r。该过程假设子数组A[p..q]和A[q+1..r]都已排好序。它合并这两个子数组形成单一的已排好序的子数组并代替当前的子数组A[p..r]。
伪代码
Merge(A, p, q, r)n1 = q - p + 1//计算左数组的长度n2 = r - q//计算右数组的长度let L[1..n1] and R[1..n2] be new arrays//分别创建左右数组for (i = 1; i <= n1; i++)L[i] = A[p+i-1]//初始化左数组，拷贝过程for (j = 1; j <= n2; j++)R[j] = A[q+j]//初始化右数组，拷贝过程i = 1j = 1k = p//merge过程，即两个有序数组合并成一个有序数组，时间复杂度O(m + n)while (i <= n1 && j <= n2)if (L[i] <= R[j])A[k++] = L[i++]else A[k++] = R[j++]while (i <= n1) A[k++] = L[i++]while (j <= n2) A[k++] = R[j++]
Merge-sort(A, p, r)1 if (p < r)2 q = (p + r) / 23 Merge-sort(A, p, q)4 Merge-sort(A, q+1, r)5 Merge(A, p, q, r)
完整代码
import java.util.Arrays;public class Test {// 归并排序的实现public static void main(String[] args) {int[] nums = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4, -3};System.out.println(Arrays.toString(nums));sort(nums, 0, nums.length-1);System.out.println(Arrays.toString(nums));}/*** 归并排序* 简介:将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，* 每个子序列是有序的。然后再把有序子序列合并为整体有序序列* 时间复杂度为O(nlogn)* 稳定排序方式* @param nums 待排序数组* @return 输出有序数组*/public static int[] sort(int[] nums, int low, int high){int mid = (low+high)/2;if(low<high){// 处理左边sort(nums, low, mid);// 处理右边sort(nums, mid+1, high);// 左右归并merge(nums, low, mid, high);}return nums;}private static void merge(int[] nums, int low, int mid, int high) {// 定义一个辅助数组，所以该算法的空间复杂度为O（n）int[] temp = new int[high-low+1];int i = low;int j = mid+1;int k = 0;// 找出较小值元素放入temp数组中while(i<=mid && j<=high){if(nums[i]<=nums[j])temp[k++] = nums[i++];elsetemp[k++] = nums[j++];}// 处理较长部分while(i<=mid){temp[k++] = nums[i++];}while(j<=high){temp[k++] = nums[j++];}// 使用temp中的元素覆盖nums中元素for (int k2 = 0; k2 < temp.length; k2++) {nums[k2+low] = temp[k2];}}}
算法分析
（1）稳定性
归并排序是一种稳定的排序。
（2）存储结构要求
可用顺序存储结构。也易于在链表上实现。
（3）时间复杂度
对长度为n的文件，需进行lgn趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
（4）空间复杂度
需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)。