#算法4 归并排序

往期回顾

上次我们讲了快速排序，它的核心是两个哨兵i和j，以及一个基准数。基准数有三种分别是两端的其中一个数，中间值和随机值。哨兵i和j分别从两端向中间遍历数，直到i找到第一个比基准值大的数，j找到第一个比基准值小的数，将它们调换后再继续，直到相遇，而相遇的位置就是基准值的位置，将基准值与相遇的值进行调换。此时整个数组也被分为了两部分，再把两部分继续执行以上步骤，直到全部有序。但是他有一个退化的风险，也就是会从O(nlogn)的算法变成O(n^2)，所以我们需要一个更稳定的算法，他就是归并排序。

算法思路

a long long time ago……我们学习了把两个有序数组合并的知识归并排序也是运用了这一点，他先把一个数组拆成两半，此时就有了两种情况。
1.两边都有序，皆大欢喜，合并！
2.不是有序的，继续执行以上步骤。
拆了好久好久……
直到拆成只剩一个数的时候，这时不管运气多背都是有序的。 ~~你要敢说一个数不是有序的试试？~~
然后再合并合并再合并……
就变成有序的啦！

具体实现

我们先来完成拆分的步骤。
为了减轻工作量，当它拆到一个数的时候合并，if语句：if(l>=r) return ; (老规矩： $l$ 表示起始的下标， $r$ 表示结束的下标。)然后加上一个 $mid$ ，也就是中间值。int mid =(l+r)/2;再加上分拆的语句(我是把这个函数取名 mergeSort)，代码↓；

  mergeSort(l,mid);
  mergeSort(mid+1,r);

再加上合并的过程(合并函数待会再说)：merge(l,mid,r);
所以分拆函数完整代码就是：

void mergeSort(int l,int r){
  if(l>=r) return ; 
  int mid =(l+r)/2;
  //1. 左右两边有序
  mergeSort(l,mid);
  mergeSort(mid+1,r);
  //O（n） 合并
  merge(l,mid,r);
}

接下来，我们来看看合并的函数。
首先，我们要定义三个变量 $i=l，j=mid，k=l$ ，他们的范围分别是 $l到mid、mid+1到r$ 和一个辅助用的数组。

int i=l,j=mid+1,k=l;

别忘了定义全局的数组t

int t[10000000];

接着，我们在while循环里加上if语句用于判断它们的大小，谁大谁就赋值到临时用的数组中，并将i或j加1，上代码！

while(i<=mid&&j<=r){
	if(a[i]>a[j]){
		t[k++]=a[j++];
	}else{
		t[k++]=a[i++];
	}
}

接下来还是while循环i_mid，jr

while(i<=mid) t[k++]=a[i++];
while(j<=r) t[k++]=a[j++];

最后再把东西“还回去”

for(int x=l;x<=r;x++){
	a[x]=t[x];
}

至此所有的都好啦！本函数完整代码：

int a[10000000],t[10000000];
void merge(int l,int mid,int r){
	//l~mid
	//mid+1 ~r 
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(a[i]>a[j]){
			t[k++]=a[j++];
		}else{
			t[k++]=a[i++];
		}
	}
	while(i<=mid) t[k++]=a[i++];
	while(j<=r) t[k++]=a[j++];
	// t[l~r]  
	for(int x=l;x<=r;x++){
		a[x]=t[x];
	}
	
}

完整代码

请勿抄袭

void merge(int l,int mid,int r){
	//l~mid
	//mid+1 ~r 
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(a[i]>a[j]){
			t[k++]=a[j++];
		}else{
			t[k++]=a[i++];
		}
	}
	while(i<=mid) t[k++]=a[i++];
	while(j<=r) t[k++]=a[j++];
	// t[l~r]  
	for(int x=l;x<=r;x++){
		a[x]=t[x];
	}
	
}

void mergeSort(int l,int r){
  if(l>=r) return ; 
  int mid =(l+r)/2;
  //1. 左右两边有序
  mergeSort(l,mid);
  mergeSort(mid+1,r);
  //O（n） 合并
  merge(l,mid,r);
}