merge_sort

expect-999 / 2023-08-02 / 原文

主要思想：分治

关键步骤：

**1.确定分界点，一般以数组的中点为界，即mid=(l+r)/2 **

**2.递归排序左右边，mid左边left左边先排序，然后右边right再排序 **

3.最后归并合二为一，即排好序的left与right的数先存到数组temp中，再由temp传入原数组

视频链接辅助理解
https://www.bilibili.com/video/BV1Pt4y197VZ/?share_source=copy_web&vd_source=6c3070fecaa59f130c4f496c1d1f6a70

代码如下

点击查看代码

include <iostream>

using namespace std;

const int N = 1e6 + 10;

int p[N],temp[N];  //需要一个temp数组暂时存放数

void merge_sort(int q[], int l, int r)
{
	if (l >= r) return;

	int mid = (l + r) >> 1;

	merge_sort(q, l, mid);
	merge_sort(q, mid + 1, r);
    //递归处理左右两边的值，使得mid左右两边变成有序序列

	int i=l, j = mid + 1, cnt = 0;

	while (i <= mid && j <= r)
	{
		if (p[i] <= p[j]) temp[cnt++] = p[i++];
		else temp[cnt++] = p[j++];
        //哪个数的值小就取出来放入temp数组中
	}

	while (i <= mid) temp[cnt++] = p[i++];
	while (j <= r) temp[cnt++] = p[j++];
 //其中肯定有i或者j没有遍历完，把没有遍历完的数放入temp数组中
//（因为letf与right是有序的，所以最后留下来的数肯定比之前遍历好的数大，不然不会没有遍历完）

	for (int i = l,cnt=0; i <=r; i++,cnt++) p[i] = temp[cnt];
    //将temp中的数存入原数组p中
}

int main()
{
	int n,i;

	scanf_s("%d", &n);

	for (i = 0; i < n; i++)
	{
		scanf_s("%d", &p[i]);
	}

	merge_sort(p, 0, n - 1);

	for (i = 0; i < n; i++) {
		printf("%d ", p[i]);//最后遍历输出
	}

	return 0;
}

本人蒟蒻，如有错误或不恰当的地方还望指点，希望对你有所帮助，感谢观看我的博客