归并排序

看前须知

首先，归并排序和快速排序一样，在算法竞赛中可以直接使用c++中的algorithm来使用就行，但是在面试啊，笔试啊等一些可能要手写代码的地方上面，学习这个排序的思想和模板还是很好的。这个归并排序算法主要运用了二分的思想，对于一个有穷无序数组进行每回分成两半的方式来进行。

崩坏3小剧场

正如我听过的一句话，如符华小姐所说，我们先制作一个馒头，第一天吃一半，第二天吃第一天的一半，第三天吃第二天的一半，这样下去就可以永远吃不完我们的馒头了hhh

题目概要

给定你一个长度为 n的整数数列。请你使用归并排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼10^9,1∼10^9 范围内, 表示整个数列。）

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

算法实现

void merge_sort(int q[], int l, int r)
{
	if (l >= r)return;
	int mid = l + r >> 1;//二进制左移1，相当于除以2

	merge_sort(q, l, mid); merge_sort(q, mid + 1, r);

	int k = 0, i = l, j = mid + 1;
	while (i <= mid && j <= r)
	{
		if (q[i] <= q[j])tmp[k++] = q[i++];
		else tmp[k++] = q[j++];
	}
	while (i <= mid)tmp[k++] = q[i++];
	while (j <= r)tmp[k++] = q[j++];

	for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}

开始的操作和快速排序算法是一样的，如果我们的数列只有一个数了，那我们就不用再继续折腾下去了，直接return就行

我们假如有这样一行无序数列(数组hh) 3 6 4 9 0 2 1 4 5 7，我们把它分成两半，一半是3 6 4 9 0，另一半是2 1 4 5 7，我们又搞了两个指针i,j它们分别指向第一半和第二半即i=0,j=5我们一个一个比较。首先i指向的数是3，j指向的数是2，2 < 3,我们把2放到新的一个数组里面，设新数组的名字是tmp吧(才，才不是配合我的图片呢hhh),放进去后我们继续，1<3，好，我们把1放到tmp里面，继续！这下子4>3了，我们把3放到tmp里面，不断轮回，最终tmp数组里面的数是这样的 2 1 3 4 5 6 4 7这样的情况，欸，怎么会没有9和0呢？你想，我们让数字进入tmp数组的要求是不是要另外一边的数比它大啊，可是到了9后，j那边没有数比它大了，j已经输了，但是我们的数字还没有全部进去，这时候我们就要对剩下的数进行一个遍历，确保它们全部进去才行，这样以后全部的数都进去了，tmp也成了2 1 3 4 5 6 4 7 9 0，这时候我们开始一轮新的循环，也就是符华小姐吃面包啦，分成两边各自进行排列，排啊排，最后我们可以得到我们想要的答案了,0 1 2 3 4 4 5 6 7 9正是我们想要的结果，很好很好。

结果实现和算法设计中需要的变量

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int q[N], n,tmp[N];

int main()
{
	int i;
	scanf_s("%d", &n);
	for (i = 0; i < n; i++)scanf_s("%d", &q[i]);
	merge_sort(q, 0, n - 1);
	for (i = 0; i < n; i++)printf("%d ", q[i]);
	return 0;
}