[数据结构与算法]归并排序算法

理论

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//相邻两个有序子序列的合并
//所以每一次都是两个合并，所以要递归很多轮，可以调试看看，然后结合原理，你就懂了代码
void Merge(vector<int>& v, int left,int right,int mid)
{//将t[left,mid]和t[mid+1,right]归并形成v[left,right]
	vector<int>  t(v.size(), 0);//构成一个新的数组作为临时数组
	int i = left;   //左边的指针
	int j = mid + 1;//右边的指针
	int k = left;     //合并v时需要的k 
	/*while (i <= mid && j <= right)*/
	while(i<=mid && j<=right)
	{
		{
			if (v[i] >= v[j])
			{
				t[k++] = v[j++];
			}
			else
				t[k++] = v[i++];
		}
	}
	//剩下的传给t
	while (i <= mid)
		t[k++] = v[i++];
	while (j <= right)
		t[k++] = v[j++];
	//给新的
	for (int i = left; i <=right; i++)        //为什么不是i=0，i<=k呢？因为每一次合并的i位置不一样
		                                     //因此i是每一趟合并的左右位置，而不是全部一起的
	{
		v[i] = t[i];
	}
	
}
//怎么分
//先分在去合并
void MSort(vector<int>& v, int left, int right)
{
	if(left<right)
	{
	int mid = (left + right) / 2;
	//从mid开始对半分,分成左右两半
	MSort(v, left, mid);//左边
	MSort(v,  mid + 1, right);//右边
	//分了在比较合并，也就是调用Merge
	Merge(v,left, right, mid);
	}
}


int main()
{
	vector<int> t{ 0,-1,100,87,200,4 };
	int left = 0;
	int right = t.size()-1;
	MSort(t,left,right);
	for (auto x : t)
		cout << x << ' ';
	system("pause");
	return 0;
}