归并排序（Merge Sort）是一种分治算法，它将数组分成两半，递归地对每一半进行排序，然后再合并两个已排序的子数组得到最终的排序结果。

完整代码

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
#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>

using namespace std;
template<typename Comp>
void merge(vector<Comp>& a, vector<Comp>& tmpArray, int left,int right)
{
	int mid, i, j;
	int k, l, target;
	mid = (left + right) / 2;
	i = left;
	j = mid + 1;
	target = left;
	while (i <= mid && j <= right)
	{
		if (a[i] <= a[j])
		{
			tmpArray[target] = a[i];
			i++;
		}
		else
		{
			tmpArray[target] = a[j];
			j++;
		}
		target++;
	}
	if (i > mid)//左半部分先完成
	{
		for (k = left; k < target; k++)a[k] = tmpArray[k];
	}
	if (j > right)//右半部分先完成
	{
		k = mid;
		l = right;
		while (k >= i)//把左半边剩余的的元素移到右边对齐
		{
			a[l] = a[k];
			k--;
			l--;
		}
	}
	//把tmpArray中元素复制到数组a中
	for (k = left; k < target; k++)a[k] = tmpArray[k];
}
template<typename Comp>
void mergesort(vector<Comp>& a, vector<Comp>& tmpArray, int left, int right)
{
	if (left < right)
	{
		int center = (left + right) / 2;
		mergesort(a,tmpArray,left, center);
		mergesort(a, tmpArray, center + 1, right);
		merge(a, tmpArray, left, right);
	}
}
template<typename Comp>
void mergesort(vector<Comp>& a)
{
	//设置一个固定的过渡数组减少空间开支
	vector<Comp> tmpArray(a.size());
	mergesort(a, tmpArray, 0, a.size() - 1);
}
int main()
{
	vector<int> a = { 8,9,7,6,5,4,3,2,1 };
	int n = a.size();
	mergesort<int>(a);

	for (int i = 0; i < n; i++)
	{
		cout << a[i] << ' ';
	}
	return 0;
};

归并排序函数

mergesort

1
2
3
4
5
6
7
8
9
10
11
template<typename Comp>
void mergesort(vector<Comp>& a, vector<Comp>& tmpArray, int left, int right)
{
	if (left < right)//递归
	{
		int center = (left + right) / 2;
		mergesort(a,tmpArray,left, center);
		mergesort(a, tmpArray, center + 1, right);
		merge(a, tmpArray, left, right);
	}
}
1
2
3
4
5
6
7
template<typename Comp>
void mergesort(vector<Comp>& a)
{
	//设置一个固定的过渡数组减少空间开支
	vector<Comp> tmpArray(a.size());
	mergesort(a, tmpArray, 0, a.size() - 1);
}

merge

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
void merge(vector<Comp>& a, vector<Comp>& tmpArray, int left,int right)
{
	int mid, i, j;
	//target用于记录tmpArray元素下标
    //k,l用于转移左半部分剩余元素
    int k, l, target;
	mid = (left + right) / 2;
	i = left;
	j = mid + 1;
	target = left;
	while (i <= mid && j <= right)//合并a左右两边的元素到过渡数组tmpArray
	{
		if (a[i] <= a[j])
		{
			tmpArray[target] = a[i];
			i++;
		}
		else
		{
			tmpArray[target] = a[j];
			j++;
		}
		target++;
	}
    //分情况讨论
    //这样写避免了教材上的代码那样出现重复复制，降低了时间复杂度
	if (i > mid)//左半部分先完成
	{
        //把tmpArray中元素复制到数组a中
		for (k = left; k < target; k++)a[k] = tmpArray[k];
	}
	if (j > right)//右半部分先完成
	{
		k = mid;
		l = right;
		while (k >= i)//把左半边剩余的的元素移到右边对齐
		{
			a[l] = a[k];
			k--;
			l--;
		}
        //把tmpArray中元素复制到数组a中
		for (k = left; k < target; k++)a[k] = tmpArray[k];
	}
}

合并后剩余元素的两种情况：

1.左半部分先完成

2.右半部分先完成

时间复杂度分析