归并排序及其应用两则

简介:归并排序(merging sort)的时间复杂度为O(nlogn),是一种稳定的排序方法。常用的2-路归并排序中的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列,递归算法形式简洁,简单易用。

应用1:求逆序对数

设a[1…n]是一个包含n个不同数的数组,对于i<j如有a[i]>a[j],则称(i,j)为一个逆序对。出题方式很多,比如直接求一个序列中逆序对的个数;比如交换原序列中相邻两元素位置使之成为单调不下降序列,求交换次数等等。当然,求逆序对数的方法也很多,但时间复杂度不大于O(nlogn)就只有归并排序和平衡二叉树了吧,显然归并排序实现起来更加简单,代码如下所示。

#include <stdio.h>

#define MAX 50001
int temp[MAX];
int count, n;

void Merge(int *array, int s, int m, int t)
{
	int i=s, j, k;
	for (j=m+1,k=s; s<=m&&j<=t; ++k)
	{
		if (array[s]<=array[j])
			temp[k] = array[s++];
		else
		{
			temp[k] = array[j++];
			count += m-s+1;  //record the inversion pairs
		}
	}
	while (s<=m)
		temp[k++] = array[s++];
	while (j<=t)
		temp[k++] = array[j++];
	while (i<=t)
		array[i] = temp[i++];
}

void MergeSort(int *array, int s, int t)
{
	if (s!=t)
	{
		int m;
		m = (s+t)/2;
		MergeSort(array,s,m);
		MergeSort(array,m+1,t);
		Merge(array,s,m,t);
	}
}

int main()
{
	int i;
	while (1)
	{
		count = 0;
		printf("Input the number(1~50000):");
		scanf("%d", &n);
		if (n==0)
			break;
		int array[n+1];
		for (i=1; i<=n; i++)
			scanf("%d", &array[i]);
		printf("The initial sequence is: ");
		for (i=1; i<=n; i++)
			printf("%d  ", array[i]);
		printf("\n");
		MergeSort(array, 1, n);
		printf("The sorted sequence is:  ");
		for (i=1; i<=n; i++)
			printf("%d  ", array[i]);
		printf("\nThe count of inversions is: %d\n", count);
	}
	return 0;
}

p.s.上述代码如果编译有错误的只需将第50行的int array[n+1];换成int array[MAX];就可以了,支持不定长数组是C99标准新增的特性,我平时使用的GCC是完全支持C99标准的,所以编译没问题,但是VS就不行了,呵呵。

应用2:其实也是求逆序对,只不过比较隐晦的那种

早晨刚看的一道题,任给一个正整数序列(个数n为已知),要求找出相邻的m(m>0)个数,使得它们的平均值必须大于等于预先给定的一个常数b,求有多少种选法?

用数组a[1…n]存放所给的n个正整数,则题目要求的其实就是(a[i]+…+a[j])/(j-i+1)>=b的个数,令s[i]=a[1]+…+a[i],且设s[0]=0,则题目转化为求(s[j]-s[i])/(j-i)>=b的个数,把(i,s[i])看成直角坐标系上的一个点,则(s[j]-s[i])/(j-i)表示通过(i,s[i])和(j,s[j])这两点的直线的斜率。过点(i,s[i])做斜率为b的直线,记该直线与y轴交点的纵坐标为y[i],则y[i]=s[i]-b*i,由于s[i]是单调递增的,所以只要求出y[i]中的逆序对即可得到(s[j]-s[i])/(j-i)<b的情况,设这个数为count,那么n(n+1)/2-count即为题目所求。

代码就不放了,在上面那个中改改就可以,我上午刚跑过,没有问题。之前看到网上有人说当序列中存在2个数相等时也要认为是逆序,这种说法其实是不对的,因为题目要求的是大于等于b,所以直接按照上述稳定的方法进行归并求逆序对数即可。

41 thoughts on “归并排序及其应用两则

  1. 尊敬的博主邀请你参加“创意礼品送博主钻石商城乐翻天”的征文活动。具体详细活动地址:http://happy.uc55.com/www/bloger/

  2. 膜拜,处于好奇,有女生搞wp,那她是cs专业的可能性极大,果然,还意外发现你用linux?!

    • 嘻嘻,被你猜中了~
      主要是前阵子有任务要做Linux编程,而且我比较喜欢用GCC编译器,所以装的双系统~

      •   给你补充一下哈,以前我真不知道:
          一轴四馆是指:2010年上海世博会的世博轴、中国国家馆、世博会主题馆、世博中心和世博会文化中心等五个标志性的永久建筑

  3. 我当初想自学C++的时候看着这玩意就头疼,不过后来谁说将if语句都没看完就夭折了,但现在看这些东西居然能看完,奇迹啊

Leave a Reply

Your email address will not be published. Required fields are marked *