基础算法模板之归并排序

归并排序

1.算法分析

归并排序是分治的思想，将一个序列分为多个子序列，先让每个子序列有序，再合并已有序的子序列。

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

2.代码实现

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 k = 0,i = l,j = mid + 1;
	while(i <= mid && j <= r)
	{
		if(q[i] < q[j]) tmp[k ++ ] = q[i ++ ];
		else tmp[k ++ ] = q[j ++ ];
	}
	while(i <= mid) q[k ++ ] = q[i ++ ];
	while(j <= mid) q[k ++ ] = q[j ++ ];
	for(int i = l,j = 0;i <= r;i ++ ,j ++ )
		q[i] = tmp[j];
}

3.算法分析

稳定性：稳定
时间复杂度：
最好情况：o（n）
最坏情况：o（\(n^2\)）
平均情况：o（n\(log_2\)n）
空间复杂度：o(n)

4.扩展-计算逆序对数量

如果将一个数组分为左右两部分，则整个数组中的逆序对数量应该等于左边的逆序对数量 + 右边的逆序对数量 + 对左边每个数可能和右边结合产生的逆序对的数量。因此可以考虑归并过程中计算逆序对数量。
逆序对：如1 3 4 2 5，其中3和2就是一组逆序对
代码如下：

long long merge_sort(int q[],int l,int r)
{
	if(l >= r) return 0;
	int mid = l + r >> 1;
	long long res = merge_sort(q,l,mid) + merge_sort(q,mid + 1,r);
	int k = 0,i = l,j = mid + 1;
	while(i <= mid && j <= r)
	{
		if(q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
		else
		{
			// q[i]到q[mid]这mid-i+1个数一定都和q[j]构成逆序对
			res += mid - i + 1; 
			tmp[k ++ ] = q[j ++ ];
		}
	}
	while(i <= mid) tmp[k ++ ] = q[i ++ ];
	while(j <= mid) tmp[k ++ ] = q[j ++ ];
	for(int i = l,j = 0;i <= r;i ++ ,j ++ )
		q[i] = tmp[j];
	return res;
}