归并
要了解归并排序算法首先要了解归并这一过程，归并过程处理两个可比较数组（两个数组已经各自有序），在归并过程中，不断对两个数组的当前首元素进行比较，将较小的元素放置到新数组的下一位置。
归并实现：(原地归并的抽象方法)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| package cn.ywrby.test;
public class MergeTest {
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
public static void MergeTest(Comparable[] a,int lo,int mid,int hi){
int i=lo,j=mid+1;
Comparable[] aux=new Comparable[hi+1];
for (int k=lo;k<=hi;k++){
aux[k]=a[k];
}
for(int k=lo;k<=hi;k++){
if(i>mid) a[k]=aux[j++];
else if(j>hi) a[k]=aux[i++];
else if(less(aux[j],aux[i])) a[k]=aux[j++];
else a[k]=aux[i++];
}
}
}
|
自顶向下的归并排序
基于原地归并的抽象实现完成的一种递归排序，首先不断对原数组进行分割，直至不能分割（每个数组中仅含一个元素），然后以每两个数组进行归并（因为只有一个元素，所以数组有序），经过一轮归并，数组中元素为2个或1个，继续递归进行归并排序，直至数组全部归并只剩一个
整个过程利用了分治思想，将一个大问题拆解为若干个简单的小问题加以解决
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| package cn.ywrby.sorts;
import cn.ywrby.tools.StopWatch;
import java.util.Random;
public class MergeSort {
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static Comparable[] aux;
public static void merge(Comparable[] a, int lo, int mid, int hi) {
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
public static void sort(Comparable[] a) {
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
public 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);
}
private static void exch(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private static void show(Comparable[] a) {
System.out.print("After sort : ");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
public static boolean isSorted(Comparable[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (!less(a[i], a[i + 1])) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int N = 1000;
Comparable<Double>[] test = new Comparable[N];
System.out.print("before sort : ");
for (int i = 0; i < N; i++) {
double data = Math.random();
System.out.print(data + " ");
test[i] = data;
}
System.out.println();
StopWatch watch = new StopWatch();
sort(test);
double time = watch.elapsedTime();
assert isSorted(test);
show(test);
System.out.println("time=" + time);
}
}
|
算法分析
对于长度为N的任意数组，自顶向下的归并排序需要NlgN/2~NlgN次++比较++
令C(N)表示一个长度为N的数组需要进行比较的次数。易知：C(0)=C(1)=0,且自顶向下排序采用了递归的方法，所以可以写成：
$$C(N)<=C_{前}(N/2)+C_{后}(N/2)+N$$
第一项表示数组前半部分比较次数，第二项则表示后半部分比较次数，最后一项表示将两项归并到一起所需要的最大比较次数
$$C(N)>=C_{前}(N/2)+C_{后}(N/2)+N/2$$
同理最后一项表示归并时最小比较次数
以$N=2^n$时为例下的++最坏情况++进行分析，可以得到如下结论：
$$C(2^n)=C_{前}(2^{n-1})+C_{后}(2^{n-1})+2^n=2*C(2^{n-1})+2^n$$
将上式两边同时除以2^n得到：
$$C(2^n)/2^n=C(2^{n-1})/2^{n-1}+1$$
利用该式可以替换右边第一项得到：
$$C(2^n)/2^n=C(2^{n-2})/2^{n-2}+1+1$$
重复n次得到
$$C(2^n)/2^n=C(0)/2^{0}+n=n$$
因此
$$C(2^n)=n2^n$$
进而由N=2^n得到
$$C(N)=NlgN$$
虽然这是对特殊情况的一种讨论，但我们不难理解这对任意N是普遍适用的
对于长度为N的任意数组，自顶向下的归并排序最多需要++访问数组++6NlgN次
每次归并最多访问数组6N次（第一个for循环的复制过程2N次，比较过程中最多2N次，将排序好的元素放回2N次），所以由上一个命题易知，最多需要访问数组6NlgN次
优点
运行时间与NlgN成正比，所以可以处理数百万甚至更大规模数组，这是初级排序算法无法做到的
缺点
辅助数组所使用的额外空间与N成正比
算法优化
- 对小规模数组使用插入排序而不是始终递归
- 添加方法以测试数组是否已经有序(a[mid]<=a[mid+1])
- 不将元素复制到辅助数组
自底向上的归并排序
自底向上的归并排序会遍历整个数组，根据子数组大小进行两两排序。子数组的大小sz的初始值为1，每次加倍。最后一个字数组的大小只有在数组大小是sz的偶数倍的时候才会等于sz(否则会比sz小)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| package cn.ywrby.sorts;
import cn.ywrby.tools.StopWatch;
import java.util.Random;
public class MergeBuSort {
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static Comparable[] aux;
public static void merge(Comparable[] a, int lo, int mid, int hi) {
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
public static void sort(Comparable[] a) {
int N=a.length;
aux=new Comparable[a.length];
for(int sz=1;sz<N;sz*=2){
for(int lo=0;lo<N-sz;lo+=sz*2){
merge(a,lo,lo+sz-1,Math.min(lo+sz*2-1,N-1));
}
}
}
private static void exch(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private static void show(Comparable[] a) {
System.out.print("After sort : ");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
public static boolean isSorted(Comparable[] a) {
for (int i = 0; i < a.length-1; i++) {
if (!less(a[i],a[i+1])){return false;}
}
return true;
}
public static void main(String[] args){
int N=100;
Comparable<Double>[] test=new Comparable[N];
System.out.print("before sort : ");
for(int i=0;i<N;i++){
double data=Math.random();
System.out.print(data+" ");
test[i]=data;
}
System.out.println();
StopWatch watch=new StopWatch();
sort(test);
double time=watch.elapsedTime();
assert isSorted(test);
show(test);
System.out.println("time="+time);
}
}
|
归并排序的局限性
- 归并排序的空间复杂度不是最优的
- 除了比较，算法的其他操作（访问数组）也可能很重要
- 不进行比较也能将某些数据排序
