- /*
- 题目:
- 求给定数组的逆序对数.
- */
- /*
- 思路:
- 归并排序.
- */
- #include<iostream>
- #include<cstring>
- #include<vector>
- #include<algorithm>
- #include<map>
- using namespace std;
- int merge(int A[], int left,int mid,int right){
- int myCount = 0;
- int p1 = left;
- int p2 = mid + 1;
- int temp[right-left+1];
- int i = 0;
- while(p1 <= mid && p2 <= right){
- if(A[p1]> A[p2]){
- myCount = myCount + 1 + mid - p1;// 右边数字大于左边数字的个数.
- temp[i] = A[p2];
- p2++;
- }else{
- temp[i] = A[p1];
- p1++;
- }
- i++;
- }
- while(p1 <= mid){
- temp[i++] = A[p1++];
- }
- while(p2 <= right){
- temp[i++] = A[p2++];
- }
- for(int i = left; i <= right; i++){
- A[i] = temp[i-left];
- }
- return myCount;
- }
- int sort(int A[], int left,int right) {
- if(left == right){
- return 0;
- }
- int mid = left + ((right-left) / 2);
- //cout<<left<<""<<mid<<" "<<right<<endl;
- int num1 = sort(A,left,mid);
- int num2 = sort(A,mid+1,right);
- return merge(A,left,mid,right) + num1 + num2;
- }
- int main(){
- int a[] = {1,3,7,2,4,1};
- cout<<sort(a,0,5)<<endl;
- for(int i = 0; i < 6;i++){
- cout<<a[i]<<" ";
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3341946.html