超级快排：Ultra-QuickSort

89 阅读 0 评论 59 点赞

我是靠谱客的博主美满战斗机，最近开发中收集的这篇文章主要介绍超级快排：Ultra-QuickSort，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目内容：

在这个问题中，你需要分析特别的算法。这个算法通过对一个包含n个元素的进行操作，一直交换相邻的两个序列的元素直到整个序列呈升序排列。对于输入序列9 1 0 5 4 ,Ultra-QuickSort最终得到的输出为0 1 4 5 9 .你的任务就是来计算出Ultra-QuickSort 至少需要多少swap操作来最终达到对一个给定的输入序列排好序的目标。

输入格式:

输入包括多组测试数据。每组测试数据以一行包括一个单独的整数n开始（n<500,000,是输入序列的长度）。每组测试数据接下来的n行包括一个单独的整数a[i]，a[i]≤ 999,999,999,代表输入序列第n个元素。输入以一个长度n为0的序列终止。这个序列不应该被处理。

输出格式：

对于每组测试数据，你的程序应该输入单独的一行，包括一个整数op，代表对该输入序列进行排序所需要最小的交换次数。

输入样例：

输出样例：

6
0

上来看很简单啊，不就是求逆序对！然后写了bubble，果然，超时...

然后事情就变得诡异了起来...

用归并排序找和加，测试了几个自己编的数据发现没问题

在MOOC平台上跑，超时超时超时*n

于是去网上找，发现和自己差不多啊？归并啊?把网上的代码提交...能过，改了好几次我的还是过不了

然后想没啥必要的优化...都不太行

最后发现...是大的循环的问题，不能用while(1){ cin>>N;if(N==0)break;}

打扰了打扰了

这么过分一定要发CSDN

/*类似求逆序
需要更高效的算法？
归并排序还超时？？
*/
#include<iostream>
using namespace std;
int N;
const int maxn = 500001;
int a[maxn];
long long ans=0;
void merge(int *a,int le,int mid,int ri)
{
	int *temp=new int[ri-le+1];
	int r=mid+1;
	int l=le;//起始位置
	int i=0;
	while(l<=mid&&r<=ri)
	{
		if(a[l]>=a[r])
		{
			temp[i++]=a[r++];
			ans+=(mid+1-l);//大的在他后面的也一定比右半部的东西大，比mid+1大不会往前走
		}
		else{
			temp[i++]=a[l++];
		}
	}
	while(l<=mid)
	{
		temp[i++]=a[l++];
	}
	while(r<=ri)
	{
		temp[i++]=a[r++];
	}
	for(int i=le,p=0;i<=ri;p++,i++)
	{
		a[i]=temp[p];
	}
	delete temp;
}
void mergesort(int *a,int le,int ri)
{
	if(ri-le>0)
	{
		int mid=(le+ri)/2;
		mergesort(a,le,mid);
		mergesort(a,mid+1,ri);
		merge(a,le,mid,ri);
	}
}
/*int count_ex(int n)
{
	int cou = 0;
	long int tmp;
	for (int i = 0; i<N - 1; i++)
	{
		bool flag = false;
		for (int j = N - 1; j>i; j--)
		{
			if (a[j]<a[j - 1])
			{
				tmp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = tmp;
				cou++;
				flag = true;
			}
		}
		if (flag == false)
		{
			break;
		}
	}
	return cou;
}*/
int main()
{
	while (scanf("%d",&N)!=EOF&&N)
	{
		ans=0;
		for (int i = 0; i<N; i++)
		{
			scanf("%d",&a[i]);
		}
		mergesort(a,0,N-1);
		printf("%dn",ans);
	}
	return 0;
}