一、归并排序
递归思路，将一个序列二分，使前半段有序，使后半段有序，然后使用双指针扫一遍使整段有序。
对于n个元素，每个元素都在排序1个元素，2个元素，4个元素，8个元素......的时候出现，因此复杂度是O(nlogn)。
二、求逆序数
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。
输入
第1行：N，N为序列的长度（n <= 50000)
第2 - N + 1行：序列中的元素（0 <= A[i] <= 10^9）输出
输出逆序数输入样例
4
2
4
3
1输出样例
4
思路
____考虑在每次归并两个有序序列的过程中，我们会将后面一个有序序列的部分元素前移，那么从后向前中间 **超越的元素** 与它成为一个逆序对，代码中为当前总位置j减去已经被分配的比它小的元素k，即 **超越的元素** 数。 _ _
__
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 int a[50020],b[50020];
5 int n;
6 long long merge(int low,int mid,int high){
7 int i=low,j=mid+1,k=low;
8 long long count=0;
9 while(i<=mid&&j<=high){
10 if(a[i]<=a[j]){
11 b[k++]=a[i++];
12 }
13 else{
14 b[k++]=a[j++];
15 count+=j-k;
16 }
17 }
18 while(i<=mid){
19 b[k++]=a[i++];
20 }
21 while(j<=high){
22 b[k++]=a[j++];
23 }
24 for(i=low;i<=high;i++){
25 a[i]=b[i];
26 }
27 return count;
28 }
29 long long mergeSort(int x,int y){
30
31 if(x<y){
32 int mid=(x+y)/2;
33 long long count=0;
34 count+=mergeSort(x,mid);
35 count+=mergeSort(mid+1,y);
36 count+=merge(x,mid,y);
37 return count;
38 }
39 return 0;
40 }
41 int main(){
42 cin>>n;
43 for(int i=0;i<n;i++){
44 scanf("%d",&a[i]);
45 }
46 cout<<mergeSort(0,n-1);
47 return 0;
48 }
View Code
三、最小的交换
只能相邻元素交换，求让序列升序的最小交换次数。
我们不可避免的让大数向后交换，那么我们考虑最大的一个数，让其向后交换，肯定会交换到最后一位，交换的次数为后面比它小的数的个数，即包含它且它更大的逆序对数，再把次小的元素向后移动......最后的移动次数即为逆序对数。
代码同上