首页 > 代码库 > 求逆序对(inversion)的个数
求逆序对(inversion)的个数
2-4 逆序对
设A[1...n]是一个包含n个不同数的数组,如果在i<j的情况下,有A[i]>A[j],则(i,j)就称为A中的一个逆序对(inversion)。
a)列出数组<2, 3, 8, 6, 1>的5个逆序对
b)如果数组的元素取自集合{1,2,...,n}, 那么, 怎样的数组含有最多的逆序对?它包含多少个逆序对?
c)插入排序的运行时间与输入数组中逆序对的数量之间有怎样的关系?说明你的理由。
d)给出一个算法,它能用Θ(nlgn)的最坏情况运行时间,确定n个元素的任何排列中逆序对的个数。(提示:修改合并排序)
分析与解答:
蛮力法:对于数组A[1...n],如果要确定所有的逆序对,只需要遍历一次数组,对于以A[j]结尾的逆序只需要遍历所有1<= i <=j
若满足A[i] > a[j],则说明(i,j)是一个逆序对,否则不是。这是一种非常朴素的方法,整个算法的时间复杂度为Θ(n*n)
a) 采用类似上面的方法,以6结尾逆序对有(1,4),以1结尾的逆序对有(1,5),(2,5),(3,5),(4,5),总共为5个
b) 当整个数组完全逆序时,含有最多的逆序对,即A={n,...,2,1},这时
以n-1结尾的逆序对有1个,以n-2结尾的逆序对有2个,以此类推,以1结尾的逆序对有n-1个。
总共(n-1)+(n-2)+...1 = n(n-1)/2
c) 插入排序的运行时间与插入排序时的总的比较次数相关,而总共的比较次数与总的逆序对的个数相同。因此两者成正比
在插入排序的过程中,插入A[j]需要比较的次数和已排序的A[1...j-1]中比A[j]大的元素个数相同,这等价于逆序对的个数。
d) 合并排序是采用分治法的思想,若需要排序A[p...q],则可以对半分成A[p...r]和A[r...q],然后将这有序的两部分Merge。
而Merge的过程为Θ(n)的时间复杂度
根据主定率T(n)=2(Tn/2)+Θ(n),时间复杂度为T(n)=Θ(nlgn)。
而求整个序列中的逆序对,也可以利用分治法的思想,即
逆序对(A[p...q])= 逆序对(A[p...r])+逆序对(A[r...q])+逆序对(A[p...r], A[r...q]之间的)
结合合并排序,关键是求如何在Θ(n)的时间有效的求出A[p...r], A[r...q]之间的逆序对
因为在合并排序的Merge过程中,A[p...r]和A[r...q]已经有序,假设此时已经Merge到A[s...r]和A[t...q]。考虑接下来的一步:若从前者取出A[s],说明A[s]比后面的序列A[t...q]中的元素都小,不存在逆序对;若从后者取出A[t],则说明A[t]比前面的序列A[s...r]都小,即以t结尾的逆序对的数量为前者的剩余序列A[s...r]中元素的数量
Merge的过程中即可得到A[p...r], A[r...q]之间的逆序对的数量,时间复杂度亦为Θ(n), 由主定律总的时间复杂为 Θ(nlgn),这种方法要比朴素的方法 Θ(n*n)好很多。
1 //求逆序对个数(使用归并排序) 2 //2014年8月7日 BUAA Rena 3 4 int inversion(int* A,int p,int q) 5 { 6 int sum=0; 7 int mid=(p+q)/2; 8 if (p==q) //这个是终止条件,容易忽略 9 {10 return 0;11 }12 13 sum+=inversion(A,p,mid);14 sum+=inversion(A,mid+1,q);15 16 // 合并思想:用两个临时空间来存储A的两个子序列,然后在求解的过程中排好序再赋值给A17 int m=mid-p+1;18 int n=q-mid;19 int *B=(int*)malloc(sizeof(int)*m);20 int *C=(int*)malloc(sizeof(int)*n);21 int i,j;22 for(i=0;i<m+n;i++)23 {24 if(i<m)25 {26 B[i]=A[i+p];27 }28 else29 {30 C[i-m]=A[i+p];31 }32 }33 34 i=j=0; 35 int k=p;36 while(i<m&&j<n)37 {38 if(B[i]<=C[j])39 A[k++]=B[i++];40 else41 {42 sum+=m-i;43 A[k++]=C[j++];44 }45 }46 if(i==m)47 {48 while(j<n)49 A[k++]=C[j++];50 }51 else52 {53 if(j==n)54 {55 while(i<m)56 A[k++]=B[i++];57 }58 }59 return sum;60 }