归并排序及延伸（找出数组中的逆序对）

最新推荐文章于 2020-04-24 17:55:08 发布

lpzbaiduwenku

最新推荐文章于 2020-04-24 17:55:08 发布

阅读量295

点赞数

本文链接：https://blog.csdn.net/lpzbaiduwenku/article/details/62434151

版权

//
//归并排序，时间复杂度nlog(n),空间复杂度o(n)，稳定排序
先把数字折半划分递归下去，直到每组的个数为1，
///然后相邻的两组各自排序，然后合并。递归回来合并
///较大数组。log(n)层完成排序，每层比较n次。
int dosort(int *pdata,int *pcopy,int ibegin,int iend);
int sortandfind(int *pdata ,int n)
{
	if(NULL == pdata)
		return 0;
	int *pcopy = new int[n];
	memcpy(pcopy,pdata,sizeof(int)*n);
	int inum = dosort(pdata,pcopy,0,n-1);
	printf("num of %d group\n",inum);
	for(int i =0 ;i<n;i++)
		printf("\n    %d     ",pcopy[i]);
	delete []pcopy;
	pcopy = NULL;
}
int dosort(int *pdata,int *pcopy,int ibegin,int iend)
{
	if(NULL == pdata || NULL == pcopy)
		return 0;
	if(ibegin == iend)//递归结束条件
		return 0;
	int imid = (ibegin + iend)/2;//中间下标
	//将进来的数据分成两组递归调用
	int ileft = dosort(pcopy,pdata,ibegin,imid);//请注意这边的第二个参数，pdata出来后是已经排序的序列，用来下面的比较
	int iright = dosort(pcopy,pdata,imid+1,iend);
	int ibegin1 = ibegin;// 第一组开始的下标
	int iend1 = imid;//第一组的末尾下标
	int ibegin2 = imid + 1;
	int iend2 = iend;
	int icopyindex = iend;//从最后一位往前填充
	int isum = 0;//逆序对总算
	while(iend1 >= ibegin1 && iend2 >= ibegin2)
	{
		if(pdata[iend1] > pdata[iend2])// 两组已排序，大于第二组的最后一个，则逆序对为第二组的个数
		{
			pcopy[icopyindex --] = pdata[iend1--];
			isum += iend2 - ibegin2 +1;
		}
		else
		{
			pcopy[icopyindex--] = pdata[iend2--];
		}
	}
	while(iend1 >= ibegin1)
	{
		pcopy[icopyindex--] = pdata[iend1--];
	}
	while(iend2 >= ibegin2)
	{
		pcopy[icopyindex--] = pdata[iend2--];
	}
	return ileft + iright + isum;
	
}

void main()
{
	int a[] = {9,2,7,8};
	sortandfind(a,4);

}

给定一个数组，找出这个数组包含的逆序对

比如{9,2,7,8}，共有9，2；9,7；9,8三对逆序对