归并排序

原理

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

它能够保证将任意长度为N的数组排序所需的时间效率为NlogN,但是他需要O(N)的额外空间来实现。

归并的实现方法很简单,创建一个适当大小的数组然后将两个数组的元素按从小到大的顺序放到这个数组中。

这里借用Jack Cui大蛇的图来形象的展示 一下归并排序的过程:
归并排序.png

归并1.png

归并2.png

实现

下面的merge(a, lo, mid, hi)方法实现了这一功能,它会将子数组a[lo…mid]和a[mid+1…hi]归并成一个有序的数组并将结果放入a[lo…hi]中。

1
2
3
4
5
6
7
8
9
10
11
12
public static void merge(int[] a, int lo, int mid, int hi) {
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k ++)
copy[k] = a[k];

for (int k = lo; k <= hi; k ++) {
if (i > mid) a[k] = copy[j ++];
else if(j > hi) a[k] = copy[i ++];
else if(less(copy[j], copy[i])) a[k] = copy[j ++];
else a[k] = copy[i ++];
}
}

该方法先将所有元素复制到copy中,然后在归并回a。方法在归并时进行了四个判断,从上到下依次是:左半边用尽(取右边的元素)、右半边用尽(取左边的元素)、右半边当前元素小于左半边的当前元素(取右半边的元素)、右半边当前元素大于等于左半边的当前元素(取左半边的元素)。

基于以上代码,我们可以写出完整的归并排序的代码:

1
2
3
4
5
6
7
8
9
10
11
12
public static void MergeSort(int[] a) {
int[] copy = new int[a.length]; // 一次性分配空间
sort(a, 0, a.length-1);
}

public static void sort(int[] a, int lo, int hi) {
if (hi < lo) return ;
int mid = lo + (hi-lo)/2;
sort(a, lo, mid); // 将左半边排序
sort(a, mid+1, hi); // 将右半边排序
merge(a, lo, mid, hi); // 归并
}

以上方法采用的是自顶向下(从一个大数组逐步的拆分成小数组然后排序合并),我们也可以采用自底向上的归并排序,即先归并那些微型数组,然后再成对归并得到的子数组,直至将整个数组归并在一起。

1
2
3
4
5
6
7
8
9
10
11
private static int[] copy;

public static void MergeSort(int[] a) {
int N = a.length;
copy = new int[N];
for (int sz = 1; sz < N; sz = sz+sz) {
for (lo = 0; lo < N-sz; lo += sz+sz) {
merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}
}
}

算法分析

归并排序是一种渐进最优的基于比较排序的算法。归并排序的形式就是一棵二叉树,它需要遍历的次数就是二叉树的深度,而根据完全二叉树的可以得出它的时间复杂度是O(n*log2n)。空间复杂度为O(n)。排序过程中,相等的元素的顺序不会改变,所以它是稳定的算法。

有收获再赞赏哦🤭
------ 本文结束感谢您的阅读-------------
0%