归并排序

1.问题描述

实现二路归并排序。

2.难度等级

medium。

3.热门指数

★★★★☆
出题公司：腾讯、B站。

4.解题思路

归并排序是分治法（Divide and Conquer）的一个典型的应用，属于比较类非线性时间排序。

归并排序先使每个子列有序，再将子列合并成有序列。若将两个子序列合并成一个有序列，称为二路归并。

先分：

归并排序先使每个子列有序，如果使子列有序呢？

将数列一分为二，直到数列中只有一个数时结束递进。因为当数列中只有一个数时，天然有序。

后治：

再将各个子列合并成有序列。

比如无序列 {7, 3, 2, 6, 0, 1, 5, 4}，先分后治完成归并排序的过程如下：

如何实现上面的过程呢？

可以看出，上面的过程是一个典型的先递后归的过程，因此我们可以通过递归的方式实现。

（1）递归划分：

计算数组中点 m ，递归划分左子数组mergesort(l, m)和右子数组mergesort(m + 1, r)；

当 l==r 时，代表子数组长度为 1 ，此时终止划分，开始合并；

（2）合并子数组：

采用双指针分别指向两个有序数组首位，比较两个数大小。以升序排列，取较小值填入辅助数组并移动指针，直到某个指针遍历完子数组。最后将未遍历完的子数组剩余元素一次性拷贝到辅助数组。

复杂度分析：

时间复杂度：最好、最坏和平均时间复杂度都是 O(nlogn)，排序性能不受待排序数据混乱程度的影响，比较稳定，这也是相对于快排的优势所在。

空间复杂度为：O(n)。合并子序列时需要用到辅助空间，长度为数列长度 n。划分的递归深度为 logn，使用 O(logn) 大小的栈帧空间。

稳定性：稳定。

5.实现示例

5.1 C++

// merge 合并子序列为有序列。
vector<int> merge(const vector<int> &vec1, const vector<int> &vec2) {
  vector<int> tmp;
  int i = 0, j = 0;
  for (; i < vec1.size() && j < vec2.size();) {
    if (vec1[i] <= vec2[j]) {
      tmp.push_back(vec1[i]);
      i++;
      continue;
    }
    tmp.push_back(vec2[j]);
    j++;
  }
  if (i < vec1.size()) {
    for (; i<vec1.size(); i++) {
      tmp.push_back(vec1[i]);
    }
  }
  if (j < vec2.size()) {
    for (; j<vec2.size(); j++) {
      tmp.push_back(vec2[j]);
    }
  }
  return tmp;
}

// mergesort 二路归并排序。
vector<int> mergesort(const vector<int> &vec, int l, int r) {
  if (l == r) {
    return vector<int>{vec[l]};
  }
  int mid = (l + r) / 2;
  auto vec1 = mergesort(vec, l, mid);
  auto vec2 = mergesort(vec, mid + 1, r);
  return merge(vec1, vec2);
}
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

验证代码：

#include 
#include 
using namespace std;

int main() {
  auto vec = mergesort(vector<int>{2}, 0, 0);
  for (const auto &v : vec)
    cout << v << ' ';
  cout << endl;
  vec = mergesort(vector<int>{3, 2, 1}, 0, 2);
  for (const auto &v : vec)
    cout << v << ' ';
  cout << endl;
  vec = mergesort(vector<int>{7, 3, 2, 6, 0, 1, 5, 4}, 0, 7);
  for (const auto &v : vec)
    cout << v << ' ';
  cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

运行输出：

2 
1 2 3 
0 1 2 3 4 5 6 7
1
2
3

5.2 Golang

// merge 合并子序列为有序列。
func merge(sl1, sl2 []int) []int {
	sl := make([]int, 0, len(sl1)+len(sl2))
	i, j := 0, 0
	for i < len(sl1) && j < len(sl2) {
		if sl1[i] <= sl2[j] {
			sl = append(sl, sl1[i])
			i++
			continue
		}
		sl = append(sl, sl2[j])
		j++
	}
	if i < len(sl1) {
		sl = append(sl, sl1[i:]...)
	}
	if j < len(sl2) {
		sl = append(sl, sl2[j:]...)
	}
	return sl
}

// mergesort 递归实现二路归并排序。
func mergesort(sl []int, l, r int) []int {
	if l == r {
		return sl[l : r+1]
	}
	mid := (l + r) / 2
	sl1 := mergesort(sl, l, mid)
	sl2 := mergesort(sl, mid+1, r)
	return merge(sl1, sl2)
}
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

验证代码：

package main

import (
	"fmt"
)

func main() {
	fmt.Println(mergesort([]int{2}, 0, 0))
	fmt.Println(mergesort([]int{3, 2, 1}, 0, 2))
	fmt.Println(mergesort([]int{7, 3, 2, 6, 0, 1, 5, 4}, 0, 7))
}
1
2
3
4
5
6
7
8
9
10
11

运行输出：

[2]
[1 2 3]
[0 1 2 3 4 5 6 7]
1
2
3

---

参考文献

「排序算法」归并排序 - LeetCode