在nlgn时间内实现逆序对数的计算

数组中逆序对的数量是同运行插入排序产生的移动的数量是相同的，但是选择排序的最差的时间复杂度是n的平方次，但是合并排序最差的是nlogn的时间复杂度。所以应该修改合并排序来计算逆序对数量。在L和R合并的过程中，如果没有移动的话，序列是L+R，所以计算移动的数量就是元素没有移动过R与L与R合并后的位置之间的差值就是移动的数量。

以下代码是实现的算法：

1. #include<iostream>
3. constintMAXINT=0xFFFF-1;
5. voidInversionMerge(intA[],intstart,intmid,intend,int&c)
6. {
7. intlen1=mid-start+1+1;//加一个位置用于保存哨兵
8. intlen2=end-mid+1;//加一个位置用于保存哨兵
9. int*L=newint[len1];
10. int*R=newint[len2];
11. for(inti=0;i<len1-1;i++)
12. L[i]=A[start+i];
13. L[len1-1]=MAXINT;
14. for(intj=0;j<len2-1;j++)
15. R[j]=A[mid+j+1];
16. R[len2-1]=MAXINT;
17. i=0;j=0;
18. for(intk=start;k<=end;k++)
19. {
20. if(L[i]<=R[j])
21. {
22. A[k]=L[i];
23. i++;
24. }
25. else
26. {
27. A[k]=R[j];
28. c=c+((mid+1+j)-k);
29. j++;
30. }
31. }
32. }
33. voidInversionMergeSort(intA[],intstart,intend,int&c)
34. {
35. if(start<end)
36. {
37. intmid=(end+start)/2;
38. InversionMergeSort(A,start,mid,c);
39. InversionMergeSort(A,mid+1,end,c);
40. InversionMerge(A,start,mid,end,c);
41. }
42. }
45. intmain(void)
46. {
47. int*a;
48. intc=0;//保存逆序对数量
49. intn;
50. std::cout<<"Pleaseinputthearray'ssize:/n";
51. std::cin>>n;
52. a=newint[n];
53. std::cout<<"Pleaseinputthearray'value:"<<std::endl;
54. for(inti=0;i<n;i++)
55. std::cin>>a[i];
56. InversionMergeSort(a,0,n-1,c);
57. std::cout<<"Thesortednumberseries:";
58. for(i=0;i<n;i++)
59. std::cout<<""<<a[i];
60. std::cout<<std::endl;
61. std::cout<<"theInversionNumberIs"<<c<<std::endl;
62. return0;
63. }

答案经检验是正确的，开心！