计算逆序对数

90 阅读 0 评论 60 点赞

我是靠谱客的博主幽默大雁，最近开发中收集的这篇文章主要介绍计算逆序对数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

描述：一个长度为N的整数序列A，满足 $i<j$ ， $A_{i}>A_{j}$ ，的对数（i，j）称为整数序列A的一个逆序对，求出整数序列A的所有的逆序对数

输入：输入包含多组测试数据，每组测试数据包含两行，第一行为整数N（1<=N<=20000），当输入0时结束，第二行为N个整数，表示长度为N的整数序列

输出：每组数据对应一行，输出逆序对的个数

样例输入

样例输出

0
10
0

求解步骤

题目要求求取逆序对数，在这里再用归并排序算法，归并排序是采用分治算法的思想，即将n个元素分为两个包含n/2的更小的子序列，依次递归下去，对每一个更小的子序列进行排序，算法的复杂度可以降到nlogn。

而在归并的过程中，对于两个已经排好序的子序列A、B，分别从左到右分别扫描序列中的内容，记 $a_{i}in{A}$ 、 $b_{j}in{B}$ ，如果 $a_{i}<b_{j}$ ， $a_{i}$ 之后的元素都不与 $b_{j}$ 构成逆序对，如果 $a_{i}>b_{j}$ ，则 $a_{i}$ 之后的元素都与 $b_{j}$ 构成逆序对。

#include<iostream>
#include<stdlib.h>
#include<string>
#include<string.h>


using namespace std;
int c ;//计算逆序对个数

void merge_sort_recursive(int a[], int reg[], int start, int end)
{
    if (start >= end)
        return;
    int length = end - start;
    int mid = length / 2 + start;//寻找中位数
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(a, reg, start1, end1);
    merge_sort_recursive(a, reg, start2, end2);
    int k = start;
    while (start1 <= end1&&start2 <= end2){
        if (a[start1] <= a[start2])
            reg[k++] = a[start1++];
        else
        {
            reg[k++] = a[start2++];
            c += (end1 - start1+1);
        }
    }
    while (start1 <= end1)
        reg[k++] = a[start1++];
    while (start2 <= end2)
        reg[k++] = a[start2++];
    for (k = start; k <=end; k++)
        a[k] = reg[k];
    return;
}



int main()
{
    int i = 0;
    int num;
    int *a = new int[20005];
    int *reg = new int[20005];//保存排序的结果
    while (scanf("%d",&num)&&num!=0)
    {
        c = 0;
        memset(a, 0,  sizeof(a));
        memset(reg, 0,  sizeof(reg));
        for (i = 0; i < num; i++)
        {
            scanf("%d", &a[i]);
        }
        merge_sort_recursive(a, reg, 0, num-1);
        //for (i = 0; i < num; i++)
        //  cout << reg[i]<<' ';
        //cout << endl;
        cout << c << endl;
    }
    return 0;
}