归并排序(C++)

解题思路:

注意事项:

参考代码:

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int arr[N],tmp[N], n;
void merge_sort(int q[], int l,int r)
{
	if (l >= r) // 当左边数比右边大时，return;
		return;
	int mid = (l + r) / 2; // 定义中间数:左加右/2
	merge_sort(q, l, mid), merge_sort(q, mid + 1, r); // 分割

	int k = 0, i = l, j = mid + 1; // 定义i、j两个左右指针，i从1指到mid,j从mid+1指到r;
	while (i <= mid && j <= r)
	{
		if (q[i] <= q[j]) // 如果q[]左边数小于右边数，将左边数添加到tmp新数组中
		{
			tmp[k] = q[i];
			k++;
			i++; // "指针"移动
		}
		else
		{
			tmp[k] = q[j];
			k++;
			j++; // "指针"移动
		}
	}
	while (i <= mid) // 如果q[]左边还剩数字，肯定是最大的，直接复制
	{
		tmp[k] = q[i];
		k++;
		i++;
	}
	while (j <= r) // 同理
	{
		tmp[k] = q[j];
		k++;
		j++;
	}

	for (i = l, j = 0; i <= r; i++, j++)
		q[i] = tmp[j]; // 将tmp里的元素覆盖q数组元素;

}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin>>arr[i];
	merge_sort(arr, 1, n);
	for (int i = 1; i <= n; i++)
		cout << arr[i] << " ";
	return 0;
}