归并排序 Merge Sort

将两个有序数列合并成一个有序数列,称之为归并。归并排序Merge Sort就是利用归并思想堆数列进行排序

1. 前言

根据具体的实现,归并排序包括:从上往下从下往上两种方式

  • 从下往上

    将带排序的数列分成若干个长度为1的子数列,然后将这些数列两两合并;的到若干个长度为2的有序数列,再将这些数列两两合并;得到若干个长度为4有序数列,再将它们两两合并;直到合并成一个数列为止。

  • 从上往下

    与从上往下在排序上是相反的,主要包括3步:

    • 分解:将当前区间一分为二,即求分裂点mid =(low+high)/2
    • 求解:递归地堆两个子区间a[low … mid]和a[min+1 … high]进行归并排序。递归的中介条件是子区间长度为1
    • 合并:将已排序的两个子区间a[low … mid]和a[min+1 … high]归并为一个有序的区间a[low … high]

2. 实现

2.1 从上往下的归并排序

从上往下的归并排序采用了递归的方式实现。它的原理非常简单,如下图:

2.2 从下往上的归并排序

从下往上的归并排序的思想正好与”从下往上的归并排序”相反。如下图:

3. 时间复杂度和稳定性

  • 时间复杂度:O(N*logN)

    假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N),需要遍历多少次呢? 归并排序的形式就是一棵二叉树,它需要遍历的次数就是二叉树的深度,而根据完全二叉树的可以得出它的时间复杂度是O(N*lgN)

  • 稳定性:归并排序是稳定的算法,它满足稳定算法的定义

4. 代码实现

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
package org.example.sort;

/**
* 归并排序
*
* @author xiaoyuge
*/
public class MergeSort {
/**
* 将一个数组中的两个相邻有序区间合并成一个
*
* @param a 包含两个有序区间的数组
* @param start 第一个有序区间的起始位置
* @param mid 第一个有序区间的结束位置,也是第二个有序区间的起始位置
* @param end 第二个有序区间的结束位置
*/
public static void merge(int[] a, int start, int mid, int end) {
int[] temp = new int[end - start + 1];//汇总两个有序区间的临时区域
int i = start; //第1个有序区间的索引
int j = mid + 1; //第2个有序区间的索引
int k = 0; //临时的索引

while (i <= mid && j <= end) {
if (a[i] < a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
while (i <= mid) {
temp[k++] = a[i++];
}
while (j <= end) {
temp[k++] = a[j++];
}
//将排序后的元素,全部都整合到数组a中
for (i = 0; i < k; i++) {
a[start + i] = temp[i];
}
temp = null;
}

/**
* 归并排序 从上往下
*
* @param a 待排序的数组
* @param start 数组的起始位置
* @param end 数组的结束位置
*/
public static void mergeSortUpToDown(int[] a, int start, int end) {
if (a == null || start >= end) {
return;
}
int mid = (end + start) / 2;
mergeSortUpToDown(a, start, mid); //递归排序a[start...mid]
mergeSortUpToDown(a, mid + 1, end); //递归排序a[end...end]

//将两个有序区间合并成一个
merge(a, start, mid, end);
}

/**
* 对数组a做若干次合并:数组a的总长度len,将它分成若干个长度为gap的子数组
* 将每2个相邻的子数组进行合并排序
*
* @param a 待排序的数组
* @param len 数组长度
* @param gap 子数组的长度
*/
public static void mergeGroups(int[] a, int len, int gap) {
int i;
int towLen = 2 * gap; //相邻两个子数组的长度

//合并
for (i = 0; i + 2 * gap - 1 < len; i += (2 * gap)) {
merge(a, i, i + gap - 1, i + 2 * gap - 1);
}
//若i+gap-1 < len -1则剩余一个子数组没有配对,将该子数组合并到已排序的数组中
if (i + gap - 1 < len - 1) {
merge(a, i, i + gap - 1, len - 1);
}
}

/**
* 归并排序 从下往上
*
* @param a 待排序的数组
*/
public static void mergeSortDownToUp(int[] a) {
if (a == null) {
return;
}
for (int n = 1; n < a.length; n *= 2) {
mergeGroups(a, a.length, n);
}
}

public static void main(String[] args) {
int[] a = {80,30,60,40,20,10,50,70};
//从上往下
mergeSortUpToDown(a, 0, a.length - 1);
for (int i : a) {
System.out.printf("%d ", i);
}
}
}