特殊的快速排序——归并排序。
给定N个数，求排成升序序列所需要的最小交换次数。每次只能交换相邻的两个数。
作为一名《线性代数》只考了60+的选手竟然一眼就看出要求逆序数有木有，可是我不会求啊有木有，搞来搞去还是要用归并排序啊有木有。 T^T
归并排序的主要思路：
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
合并函数：
1 void mergeArray(long long int *a,int first,int mid,int last) 2 { 3 int ia = first,ib = mid + 1,ea = mid,eb = last,top = 0; 4 5 long long int *temp = (long long *)malloc((last-first+2)*sizeof(long long )); 6 7 while(ia <= ea && ib <= eb) 8 { 9 if(a[ia] <= a[ib]) 10 { 11 temp[top++] = a[ia++]; 12 } 13 else 14 { 15 temp[top++] = a[ib++]; 16 ans += ea-ia+1; 17 } 18 } 19 20 while(ia <= ea) 21 { 22 temp[top++] = a[ia++]; 23 } 24 25 while(ib <= eb) 26 { 27 temp[top++] = a[ib++]; 28 } 29 30 for(int i = 0;i < top; ++i) 31 { 32 a[i+first] = temp[i]; 33 } 34 free(temp); 35 36 } View Code很显然，合并的前提是两个数列有序，那么怎样确定两个数列有序呢？
当数列仅有一个元素的时候，显然这个数列是有序的。
所以我们可以将数列不断的二分下去，直到其只有一个元素为止，然后再依次合并即可。
综上：归并排序就是先递归分解序列，再依次合并子序列的过程。
AC_Code：
耗时 2000+ 慢了一13......
1 #include <iostream> 2 #include <cstdlib> 3 #include <cstdio> 4 5 using namespace std; 6 7 long long int a[500010],ans; 8 9 void mergeArray(long long int *a,int first,int mid,int last) 10 { 11 int ia = first,ib = mid + 1,ea = mid,eb = last,top = 0; 12 13 long long int *temp = (long long *)malloc((last-first+2)*sizeof(long long )); 14 15 while(ia <= ea && ib <= eb) 16 { 17 if(a[ia] <= a[ib]) 18 { 19 temp[top++] = a[ia++]; 20 } 21 else 22 { 23 temp[top++] = a[ib++]; 24 ans += ea-ia+1; 25 } 26 } 27 28 while(ia <= ea) 29 { 30 temp[top++] = a[ia++]; 31 } 32 33 while(ib <= eb) 34 { 35 temp[top++] = a[ib++]; 36 } 37 38 for(int i = 0;i < top; ++i) 39 { 40 a[i+first] = temp[i]; 41 } 42 free(temp); 43 44 } 45 46 void merge_sort(long long int *a,int first,int last) 47 { 48 if(first < last) 49 { 50 int mid = (first+last)/2; 51 merge_sort(a,first,mid); 52 merge_sort(a,mid+1,last); 53 mergeArray(a,first,mid,last); 54 } 55 } 56 57 int main() 58 { 59 int n,i; 60 61 while(cin>>n && n) 62 { 63 for(i = 0;i < n; ++i) 64 { 65 cin>>a[i]; 66 } 67 ans = 0; 68 merge_sort(a,0,n-1); 69 70 cout<<ans<<endl; 71 72 } 73 return 0; 74 } View Code
转载于:https://www.cnblogs.com/zmx354/p/3252475.html
相关资源：JAVA上百实例源码以及开源项目