归并排序

简介

荒废一周之后,趁着加班打酱油的机会,记录一下最近一周玩的排序算法-归并排序。归并排序的思想还是用到了分治的思路,相较于快排的整体有序之后再分治,归并的思路在于分治之后,将分治后得到的多个有序集合合并。归并算法的平均时间复杂度为O(nlgn).

归并排序

归并的一种实现方式是将序列分成两个包含n/2各元素的子序列,然后分别对这两个序列进行递归排序,最后将这个两个有序的序列合并,得到一个完整的有序序列。
这里我们还是先来一份伪代码:

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
mergeSort(a,l,r)
if l < r
q = (l + r )/2
mergeSort(a,l,q)
mergeSort(a,q+1,r)
merge(a,l,q,r)

merge(a,l,q,r)
length1 = q-l+1;
length2 = r-q;
new L[length1+1]
new R[length2+1]
for i: 1 to length1
L[i]=a[l+i-1]
L[length1 -1] = Max
for j: 1 to length2
L[j]=a[q+i]
R[length2 -1] = Max
i =1
j=1
for k : l to r
if L[i]<R[j]
a[k] = L[i]
i++
else
a[k] = R[j]
j++

从伪代码我们可以看到:归并算法的核心在于merge,和快排不一样的是,归并需要开辟两个临时空间存储已排序序列。分配完空间后并初始化两个临时有序序列后,将两个序列进行归并到源序列上。
我们分析一下这个归并过程:
当L[i] < R[j] 时 a[k] =L[i],此时满足

1
1)i <=x<q    a[k] <= L[x] 即保证a[k]为剩下未比较L[],R[]中最小的。

在伪代码里,两个临时序列尾部添加一个无穷大值,是为了当两个序列各只有一个值时,归并发生两次会发生指针越界的问题。

实现代码

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

public int[] megerSort(int[] num, int left, int right) {
if (left < right) {
int baseIndex = (left + right) / 2;
megerSort(num, left, baseIndex);
megerSort(num, baseIndex + 1, right);
merge(num, left, baseIndex, right);
}
return num;
}

private void merge(int[] num, int left, int baseIndex, int right) {
//初始化两个临时有序序列
int[] leftNum = new int[baseIndex - left + 1 + 1];

for (int i = 0; i < baseIndex - left + 1; i++) {
leftNum[i] = num[left + i];
}
//序列尾部添加无穷大
leftNum[baseIndex - left + 1] = Integer.MAX_VALUE;
int[] rightNum = new int[right - baseIndex + 1];
for (int j = 0; j < right - baseIndex; j++) {
rightNum[j] = num[baseIndex + j + 1];
}
rightNum[right - baseIndex] = Integer.MAX_VALUE;
int i = 0;
int j = 0;
for (int k = left; k <= right; k++) {
if (leftNum[i] < rightNum[j]) {
num[k] = leftNum[i];
i++;
} else {
num[k] = rightNum[j];
j++;
}
}
}

public static void main(String[] arg) {
MergeSort mergeSort = new MergeSort();
int[] num = new int[]{6, 7, 5, 2, 1, 3};
num = mergeSort.megerSort(num, 0, num.length - 1);
}

时间复杂度分析

同快速排序算法,在最理想的情况下,megerSort序列分为规模不大于n/2的两个子序列,而merge的复杂度为r-l+1 =O(n),所以我们得出归并的时间复杂度计算公式:
T(n) = 2T(n/2) + O(n)
求解得T(n) = O(nlgn)

坚持原创技术分享,您的支持将鼓励我继续创作!