首页 > 代码库 > TreeArray2299_MergeSort

TreeArray2299_MergeSort

给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列。

 

解题思路:

一看就是冒泡,交换一次记录一次就可以了

但是n的范围达到50W,冒泡O(n^2)的复杂度铁定超时(即使有7000ms,其实这是一个陷阱)

直接用快排又不符合题目的要求(相邻元素交换),快排是建立在二分的基础上的,操作次数肯定比在所要求的规则下的交换次数要更少

 

那么该怎么处理?

 

其实这题题目已经给出提示了:Ultra-QuickSort

特殊的快排,能和快排Quicksort相媲美的就是归并排序Mergesort了,O(nlogn)

 

但是用归并排序并不是为了求交换次数,而是为了求序列的 逆序数(学过《线代》的同学应该很熟悉了)

一个乱序序列的 逆序数 在只允许相邻两个元素交换的条件下,得到有序序列的交换次数

 

例如例子的

9 1 0 5 4

由于要把它排列为上升序列,上升序列的有序就是  后面的元素比前面的元素大

而对于序列9 1 0 5 4

9后面却有4个比9小的元素,因此9的逆序数为4

1后面只有1个比1小的元素0,因此1的逆序数为1

0后面不存在比他小的元素,因此0的逆序数为0

5后面存在1个比他小的元素4, 因此5的逆序数为1

4是序列的最后元素,逆序数为0

 

因此序列9 1 0 5 4的逆序数 t=4+1+0+1+0 = 6  ,恰恰就是冒泡的交换次数

 

PS:注意保存逆序数的变量t,必须要用__int64定义

 

归并排序:

   长度为7的原始数据: 

   [72] [18] [53] [36] [48] [31] [36]

 

   一趟归并: [18 72] [36 53] [31 48] [36]

 

   二趟归并: [18 36 53 72] [31 36 48]

 

   三趟归并: [18 31 36 36 48 53 72]

 

 

 

时间复杂度为O(nlogn) 这是该算法中最好、最坏和平均的时间性能。

空间复杂度为 O(n)

比较操作的次数介于(nlogn) / 2nlogn - n + 1

在上图中,树的高度为logn,最好的情况,每次左边序列最小的数都比右边序列大,那么对于两个长度为x的子序列,只需要比较x次。在上图中,共logn层,最好的情况下,每层元素为n,分成左序列和右序列,因此比较次数为n/2

最坏情况则是两个x长度子序列每个都需要比较一次,共x次比较,每层需要比较n次。

因此复杂度在(nlogn) / 2nlogn 之间。

 

 

//Memory Time

//3768K 2422MS 

 

#include<iostream>

using namespace std;

 

const int inf=1000000000;  //10E

 

__int64 t; //s[]数列逆序数

 

void compute_t(int* s,int top,int mid,int end)

{

int len_L=mid-top+1;

int len_R=end-mid;

 

int* left=new int[len_L+2];

int* right=new int[len_R+2];

 

int i,j;

for(i=1;i<=len_L;i++)

left[i]=s[top+i-1];

left[len_L+1]=inf;   //设置无穷上界,避免比较大小时越界

 

for(j=1;j<=len_R;j++)

right[j]=s[mid+j];

right[len_R+1]=inf;   //设置无穷上界,避免比较大小时越界

 

i=j=1;

for(int k=top;k<=end;)

if(left[i]<=right[j])

s[k++]=left[i++];

else

{

s[k++]=right[j++];

t+=len_L-i+1;    //计算逆序数

 

//因为逆序对的个数f(A) = f(L) + f(R) + s(L,R);其中f(L) 和 f(R) 分别表示内部 和R内部的逆序对个数,s(L.R)表示合并造成的逆序对。因为LR是已经排好序的,故其实只需求s(L,R).对于right[j]right[j]<left[i],将它放进s之前,lefti以及i以后的节点都比right[j]大,因此逆序数要加上len_L-i+1

}

 

delete left;

delete right;

 

return;

}

 

void mergesort(int* s,int top,int end)

{

if(top<end)

{

int mid=(top+end)/2;

mergesort(s,top,mid);

mergesort(s,mid+1,end);

compute_t(s,top,mid,end);

}

return;

}

 

int main(void)

{

int n;  //序列长度

while(cin>>n)

{

if(!n)

break;

 

/*Input*/

 

int* s=new int[n+1];

for(int i=1;i<=n;i++)

cin>>s[i];

 

/*Merge-Sort*/

 

t=0;  //initial

mergesort(s,1,n);

 

/*Output*/

 

printf("%I64d\n",t);

//对于__int64的数据,输出必须也要这种格式

/*Relax*/

 

delete s;

 

}

return 0;

}

 

TreeArray2299_MergeSort