目录

• • 线性排序——计数排序
  • 逆序数对——归并排序

线性排序——计数排序

to be continue…

逆序数对——归并排序

首先了解一下什么叫做逆序数对，抄一段百度

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。也就是说，对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个 不同的自然数，可规定从小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素的实际先后次序与标准次序不同时，就说有1个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。

ok，现在我们的代码需求是求出一个数列的逆序数对数，不同于暴力求解的双遍历O(n^2)的时间复杂度，这里我们可以利用归并排序的一个特性很精妙地求解出逆序数。

#include <iostream>

using namespace std;

const int Max = 1000 + 10;

int arr[Max];
int temp[Max];

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++];
        } else{
            temp[k++] = arr[j++];
        }
    }
    while (i <= right){
        temp[k++] = arr[i++];
    }
    while (j <= right){
        temp[k++] = arr[j++];
    }
    for(k = left; k <= right; k++){
        arr[k] = temp[k];
    }
}

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);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    MergeSort(0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
    }
    printf("\n");

    return 0;
}