用归并排序求逆序对数（包括归并排序算法实现及代码）

用归并排序求逆序对数（包括归并排序算法实现及代码）

引用

CSDN

1.

https://blog.csdn.net/qq_45585519/article/details/104709508

在算法设计课上老师给出了如上一个问题，让用刚学习的归并排序算法来实现求逆序对数。
那么我们很容易想到这个题有一种O（n*n）的暴力解法，但这不是我们所需要的，所以，要想归并排序来实现求逆序对数，那么首先我们要了解并掌握归并排序算法。
所谓归并排序算法，就是采用分治法将问题规模不断缩小，然后在合并的一个过程。
假设有一个数组，那么我们是一直将其划分，直到只剩余一个元素，那么这个时候我们往回合并，合并过程很简单，无非是每两个数组指针动不动，具体图解如下：

那么我们用代码实现如下：

  
#include<bits/stdc++.h>
#define maxn 10005
using namespace std;
int a[maxn];
//归并过程
void merge(int arr[], int l, int mid, int r){
    int help[r-l+1];//辅助数组
    int i = 0;
    int lIndex = l;
    int rIndex = mid+1;
    while(lIndex <= mid && rIndex <= r){
        help[i++] = arr[lIndex] < arr[rIndex] ? arr[lIndex++]:arr[rIndex++];	
    }
    //左边和右边肯定有一边到头了，不可能同时，因为每次只移动一边
    while(lIndex <= mid){
        help[i++] = arr[lIndex++];
    } 
    while(rIndex <= r){
        help[i++] = arr[rIndex++];
    }
    //将排好序的辅助数组赋值给原始数组，不需要返回值
    for(i = 0; i < r-l+1; i++){
        arr[l+i] = help[i];
    }
}
 
//递归
void mergeSort(int arr[], int l, int r){
    if(l == r){
        return;
    }
    int mid = (l + r) / 2;
    //左半部分归并排序
    mergeSort(arr, l, mid);
    //右半部分归并排序
    mergeSort(arr, mid+1, r);
    //左右部分归并
    merge(arr, l, mid, r);
}
 
//归并排序整个数组
void mergeSort(int arr[], int n){//特判，如果数组为空或只有一个元素，那么就不需要排序
    if(arr == NULL || n < 2){
        return;
    }
    mergeSort(arr,0,n-1);
}
int main(){
    int n; 
    while(cin >> n){
        for(int i = 0; i < n; i++) 
        cin >> a[i];
 
        mergeSort(a, n);
 
        for(int i = 0; i < n; i++){
            cout << a[i] << " ";
        } 
        cout << endl;
    }
    return 0;
} 
  

那么在实现并掌握归并排序算法的基础上，我们只要对其做一点修改就能满足题目的要求了。
注：为了增强可读性，让老师运行一下，加了几行说明；

  
/*
采用归并排序求逆序对数
测试数据:
5
1 2 3 4 5    0
5
5 4 3 2 1  10 
*/
#include<bits/stdc++.h>
#define maxn 10005
using namespace std;
int n;//输入数据的个数 
int tot;//用于计数求逆序对的个数 
int a[maxn];//用于存放数据个数 
int b[maxn];//存放 
 
void mersort(int l, int r){
    if(l>=r) return ;
    int midd = (l+r)/2;
    int i = l;
    int j = midd+1;
    int k = 0;
    while(i<=midd&&j<=r){
        if(a[i] > a[j]){
            b[k++] = a[j++];
            tot += midd-i+1; 
        }else{
            b[k++] = a[i++];
        }
    }
    while(i<=midd) b[k++] = a[i++];
    while(j<=r) b[k++] = a[j++];
    for(int i=0;i<k;i++) a[i+l] = b[i];
}
void mer(int l,int r){
    if(l>=r) return ;//超过则返回
    
    int mid = (l+r)/2; //不断划分 
    mer(l,mid);
    mer(mid+1,r);
    
    mersort(l,r);//合并 
}
int main(){
    cout<<"请输入数据的个数:"<<endl;
    cin>>n;
    cout<<"请输入数据,各数据间用空格隔开"<<endl;
    for(int i=0;i<n;i++)
     cin>>a[i]; 
    tot = 0;//初始化为0 
    mer(0,n-1);
    cout<<"逆序对个数为:"<<endl; 
    cout<<tot<<endl; 
}