阅读本文大概需要5分钟
其他
五分钟教你学会归并排序
今天来讨论下归并排序。只要五分钟便能掌握归并排序的原理。
归并算法的中心是归并两个已经有序的数组。归并两个有序数组 A 和 B，就生成了第三个数组 C，数组 C 包含数组 A 和 B 的所有数据项，并且使它们有序的排列在数组 C 中。首先我们来看看归并的过程，然后看它是如何在排序中使用的。
假设有两个有序数组，不要求有相同的大小。设数组 A 有 4 个数据项，数组 B 有 6 个数据项，它们要被归并到数组 C 中，开始时数组 C 有 10 个存储空间，归并过程如下图所示：
归并排序的思想是把一个数组分成两半，排序每一半。然后用 merge 方法将数组的两半归并成一个有序的数组。被分的每一半使用递归，再次划分排序，直到得到的子数组只含有一个数据项为止。正如上面所说的，归并排序需要额外的一个和 AB 两个数组总和相等的空间，如果初始数组几乎沾满了整个存储器，那么归并排序就不能工作了。
归并排序的思想很简单，下面我们来看看具体实现：
public void mergeSort(int[] source) {
int[] workSpace = new int[source.length];
recMergeSort(source,workSpace, 0, source.length-1);
}
private void recMergeSort(int[] source, int[] workSpace, int lowerBound, int upperBound) {
if(lowerBound == upperBound) {
return;
}
else {
int mid = (lowerBound + upperBound) / 2;
recMergeSort(source, workSpace, lowerBound, mid); //左边排
recMergeSort(source, workSpace, mid+1, upperBound); //右边排
merge(source, workSpace, lowerBound, mid+1, upperBound);//归并
}
}
private void merge(int[] a, int[] workSpace, int lowPtr, int highPtr, int upperBound) {
int j = 0;
int lowerBound = lowPtr;
int mid = highPtr - 1;
int n = upperBound - lowerBound + 1;
while(lowPtr <= mid && highPtr <= upperBound) {
if(a[lowPtr] < a[highPtr]) {
workSpace[j++] = a[lowPtr++];
}
else {
workSpace[j++] = a[highPtr++];
}
}
while(lowPtr <= mid) {
workSpace[j++] = a[lowPtr++];
}
while(highPtr <= upperBound) {
workSpace[j++] = a[highPtr++];
}
for(j = 0; j < n; j++) {
a[lowerBound + j] = workSpace[j];
}
}算法分析：归并排序的运行时间最差、最好和平均都是 O(NlogN)，但是它需要额外的存储空间，这在某些内存紧张的机器上会受到限制。归并算法是由分割和归并两部分组成的，对于分各部分，如果我们使用二分查找，时间是 O(NlogN)，在最后归并的时候时间是 O(N)，所以总时间是 O(NlogN)。空间复杂度为 O(N)。
归并排序是稳定的，由于没有发生数据交换，所有当 a=b 的时候，a 一开始如果在 b 前面，则其每一次合并后仍然在 b 前面，故该排序算法是稳定的。
这世上没有天才，你若对得起时间，时间便对得起你。关注我们，每天进步一点点，利用碎片化时间学习。
我的世界不仅是coding