c++ --- 归并排序

2、归并排序

步骤：

1. 选取中间点 mid = (L+R)/2
2. 递归排序 左边left 和 右边 right
3. 归并 ---- 将数组合二为一

模板代码

int temp[10];
void merge_sort(int q[], int l, int r) {
	//如果左右边界相等 直接退出
	if (l >= r) return;

	//获取数组中心
	int mid = (l + r) / 2;

	//递归排序 分成左右两边
	merge_sort(q, l, mid);
	merge_sort(q, mid+1,r);
	
	//归并的过程
	//k 表示当前temp数组有多少个数了
	int k = 0;
	//i 指向左半边的起点
	int i = l;
	//j 指向右半边的起点
	int j = mid + 1;
	
	
	while (i<=mid && j<=r)
	{
		//两个数组的当前指向的数 谁大 放入临时数组
		if (q[i]<=q[j])
		{
			temp[k++] = q[i++];
		}else {
			temp[k++] = q[j++];
		}
	}
	//走到最后 有一个数组会先走完， 那么我们把剩下的另一个数组拿过来接到最后
	while (i<=mid)
	{
		temp[k++] = q[i++];
	}
	while (j<=r)
	{
		temp[k++] = q[j++];
	}

	//将结果拿回原数组
    //这里是分段的将排序好的数组拿回q[]中，并不是将所有的元素排好后统一拿进去
	for (i = l, j = 0; i <= r; i++, j++) {
		q[i] = temp[j];
	}

}
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

相比于快排，这里会多使用一个temp临时的数组