排序算法是学习算法时十分重要的部分,尤其是在大量数据处理方面扮演十分重要的角色。这次我们学习两种基于归并操作的排序算法。


0. 归并排序

要将一个数组排序,可以先(递归地)将它分成两半分别排序,然后将结果归并起来,这就是归并排序。

实现归并排序的一种直截了当的方法就是将两个不同的有序数组归并到第三个数组中。创建一个适当大小的数组然后将两个数组中的元素一个个从小到大放入这个数组中。

1. 原地归并辅助方法

当用归并对一个大数组排序时,我们需要进行多次归并,因此每次归并时都创建一个新数组来存储排序结果。这样我们就需要大量的额外空间,所以我们需要一种能够原地归并的方法,而不需要使用额外的空间。

与之前初级排序的算法模板不同,归并排序需要一个新的辅助方法 merge() 对数组进行原地归并。

// 原地归并方法
public static void merge(Comparable[] a, int left, int mid, int right)
int p = left, q = mid + 1;

// 将 a[left..right] 复制到 temp[left..right]
for (int i = left; i <= right; i++){
temp[i] = a[i];
}

// 归并
for (int i = left; i <= right; i++){
// 当左半边用尽时,取右半边的元素
if (p > mid){
a[i] = temp[q++];
// 当右半边用尽时,取左半边的元素
}else if(q > right){
a[i] = temp[p++];
// 当左半边小于右半边时,取左半边的元素
}else if(less(temp[p], temp[q])){
a[i] = temp[p++];
// 当右半边小于左半边时,取右半边的元素
}else{
a[i] = temp[q++];
}
}
}

2. 自顶向下的归并排序

2.1 概述

在归并排序中,对数组进行排序,先将它分为两个子数组,然后通过递归调用将它们单独排序,最后将有序的子数组归并为最终的排序结果。

这种将大问题分割为小问题分别解决,然后用小问题的答案来解决大问题,这就是算法设计中的分而治之思想。

(PS:图片标题写错了,应该是“自顶向下”)

2.2 自顶向下归并排序实现

public class Merge
{
private static Comparable[] temp; // 归并所需的辅助数组

public static void sort(Comparable[] a)
{
temp = new Comparable[a.length];
sort(a, 0, a.length - 1);
}

private static void sort(Comparable[] 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); // 将两部分归并在一起
}
}

2.3 自顶向下归并排序分析

自顶向下归并排序可以用一颗树来表示,每个结点都表示一个 sort() 方法通过 merge() 方法归并而成的子数组。

通同树状图我们可以得到,自顶向下的归并排序需要 1/2NlgNNlgN 次比较。自顶向下的归并排序最多需要访问数组 6NlgN 次。

总结:

以上分析,告诉我们归并排序所需的时间和 NlgN 成正比。这比初级排序算法要快得太多了,可以用归并排序处理数百万甚至更大规模的数组。

3. 自底向上归并排序

3.1 概述

自底向上归并排序就是先归并哪些微型数组,然后在成对归并得到的子数组,如此这般,直到我们将整个数组归并在一起。

我们把数组中的每一个元素看作大小为 1 的数组,进行两两合并,然后四四合并,然后八八合并,直到将整个数组合并。

3.2 自底向上归并排序实现

public class MergeBU
{
private static Comparable[] temp; // 归并所需的辅助数组

public static void sort(Comparable[] a)
{
int N = a.length;
temp = new Comparable[N];
for (int size = 1; size < N; size *= 2){
for (int i = 0; lo < N-size; lo += size*2){
merge(a, i, i+size-1, Math.min((i+size-1)+szie), N-1));
}
}
}
}

3.3 自底向上归并排序分析

自底向上的归并排序需要 1/2NlgNNlgN 次比较,最多访问数组 6NlgN 次。

总结:

当数组长度为 2 的幂时,自顶向下和自底向上的归并排序所用的比较次数和数组访问次数正好相同,只是顺序不同。其他时候,两种方法的比较和数组访问的次序会有所不同。


参考文献:算法(第四版) —— 人民邮电出版社

评论