C++中的归并排序

 

代码模板

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); //递归分治 
	
	int cnt(0),i(l),j(mid+1);//cnt为tmp数组中的指针,i和j为需要归并的两个范围指针
	while(i<=mid&j<=r)
		if(q[i]<q[j]) tmp[cnt++]=q[i++];
		else tmp[cnt++]=q[j++];//指针对比,将更小的数值移入临时数组tmp当中
	while(i<=mid) tmp[cnt++]=q[i++];
	while(j<=r) tmp[cnt++]=q[j++];//确保所有数字全部被扫描,强制移动并填入数据
	 
	for(i = l,j = 0;i<=r;i++,j++) q[i]=tmp[j];//由于是从第l个开始排序,所以i=l而不是=0}

代码原理

扫描

归并排序的本质是将一长段数据分为两个部分,然后通过两个指针一起从头开始对比,将更小的数字放入一个临时数组中,在数组一和数组二对比完毕以后,临时数组里面的数据理论上来说就是从小到大(或者按照需求改为从大到小)排好了。

​ 首先通过位运算划分中间点mid,其中以最小的数组为单位划分为A和B两个数组,这两个数组在分治的”最小单位“下理论上应该是从小到大依次分布的,只不过A、B两个数组相互独立。这个时候利用两个指针ij对两个数组进行分别扫描,大致示意图如下

A 1 2 3 4 5 6 7
  ↑
  i
B 2 3 4 5 6 7 8
  ↑
  j
  
实际的数组: 1 2 3 4 5 6 7 2 3 4 5 6 7 8

填入临时数组

​ 定义一个临时数组tmp,在扫描的过程中,以上示例来说,由于A1要比B2更小,所以1被采用

,定义一个计数器cnt,将tmp[cnt++]定义为1(更小的数字)然后依次进行填充,直到两个数组都被扫描并且使用完毕

写入原数组

这个时候通过一个简单的for循环将排序好的tmp填入需要排序的q数组对应的位置即可。

时间复杂度

O(nlogn)