逆序数的实现——基于二路归并排序

可利用二路归并排序的基本思想:

法一:左边有序数组和右边有序数组比对,如果左边的下标为i的值>右边下标为j的值,则表示i及其后面(直到middle)的所有值都大于右边下标为j的值

法二:或者说左边下标为i的值大于右边下标为j及其左边(直到middle+1)的所有值()但这个就需要在后面多些代码,下面会详细说。

 

法一:

/*
-------------------------------------------------
   Author:       wry
   date:         2022/3/1 17:10
   Description:  test
-------------------------------------------------
*/

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000+10;
int arr[MAXN];
int temp[MAXN];
int number;

void Combine(int left,int middle,int right) {
    int i = left;
    int j = middle+1;
    int k = left;
    while (i<=middle && j<=right) {
        if (arr[i]<=arr[j]) {
            temp[k] = arr[i];
            i++;
            k++;
        }
        else if (arr[i]>arr[j]){   //表示i及其之后的位置都大于j,相当于逆序对的(a,b)的b已经判断ok
            temp[k] = arr[j];
            j++;
            k++;
            number += middle-i+1;
        }
    }
    while (i<=middle) {     //说明剩下的都是更大的,但是b已经全部判断完,所以不用再额外添加
        temp[k] = arr[i];
        i++;
        k++;
    }
    while (j<=right) {
        temp[k] = arr[j];
        j++;
        k++;
    }
    for (int t=left;t<=right;t++) {
        arr[t] = temp[t];
    }
}

void MergeSort(int left,int right) {
    if (left < right) {
        int middle = left+(right-left)/2;
        MergeSort(left,middle);
        MergeSort(middle+1,right);
        Combine(left,middle,right);
    }
    else {
        return ;
    }
}

int main() {
    int n;
    while (cin>>n) {
        number = 0;
        for (int i=0;i<n;i++) {
            cin >> arr[i];
        }
        MergeSort(0,n-1);
        for (int i=0;i<n;i++) {
            cout << arr[i] << " ";
        }
        cout << endl << number << endl;
    }
    return 0;
}

 

法二需要改的地方为:

while (i<=middle && j<=right) {
  if (arr[i]<=arr[j]) {
    temp[k] = arr[i];
    i++;
    k++;
  }
  else if (arr[i]>arr[j]){   
    temp[k] = arr[j];
    j++;
    k++;
    number += j-middle+1;    //这里
  }
}
while (i<=middle) {     
  temp[k] = arr[i];
  i++;
  k++;
  number++;        //这里
}
while (j<=right) {
  temp[k] = arr[j];
  j++;
  k++;
} 

 

上一篇:运算符


下一篇:强连通分量(Tarjan算法) 图解