从键盘任意输入一个3为整数，编程计算并输出它的逆序数（忽略整数前的正负号）。例如，输入-123，则忽略负号，由其百位1、十位2、个位3，然后计算3*100+2*10+1 = 321，并输出321。

输入格式要求："%d" 提示信息："Input x:"

输出格式要求："y = %d\n"

程序运行示例如下：

Input x：-123

y = 321

计算逆序数

在很早之前，我曾经发过一篇文章，讲的是冒泡排序的交换次数就是逆序数。可是，这样计算逆序数的话，时间成本就很高，比较冒泡是时间复杂度为O(N²)的算法呢！那怎么办呢？其实，我们可以使用归并排序的思想来计算逆序数。

（以下内容需要先了解归并排序，具体讲解可以看我的这一篇文章：）

【笔记】数据结构之归并排序

我们会发现，在进行升序的归并排序时，每一次后方元素移到前面来的移动距离就是本次操作的逆序数。那么我们思考之后可以得出，每一步操作的逆序数就是n1-i

具体得看下面这个图：

由于每一层递归结束之后，左右两边都变成了已经升序排序的数组，那么自然地，当右边的元素小于左边元素的时候，把它移到前面的逆序数就是n1-i

代码实现

#include<iostream>
using namespace std;

unsigned int L[100002],R[100002];
unsigned int num[200002];
unsigned long long nixushu=0;

void _Merge(int left, int mid, int right)
{
    int n1 = mid-left;
    int n2 = right-mid;

    for(int i=0;i<n1;i++)
        L[i] = num[left+i];

    for(int i=0;i<n2;i++)
        R[i] = num[mid+i];


    L[n1]=R[n2]=1000000003;
    int js1=0,js2=0;

    for(int i=left;i<right;i++)
    {
        if(L[js1]<=R[js2])
        {
            num[i] = L[js1];
            js1++;
        }
        else
        {
            num[i] = R[js2];
            js2++;
            nixushu += n1-js1;

        }
    }

}

void mergeSort(int left, int right)
{
    if(left+1>=right)
        return;

    int mid = (left+right)/2;
    mergeSort(left,mid);
    mergeSort(mid,right);
    _Merge(left, mid, right);

}


int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>num[i];
    mergeSort(0,n);
    cout<<nixushu<<endl;
}

因此，我们需要关注的关键问题就是合并函数的实现。经过上面的分析，我们可以知道，我们只需要在归并排序的合并函数里面，负责处理L[js1]>R[js2]的那部分代码里面做一些修改，就可以实现计算逆序数的目的。

欢迎关注我的公众号哦！

本文简单介绍了几种计算逆序数的实现方法

简介

所谓逆序数,是指一个排列中所有逆序对的总数,而所谓逆序对,则是指排列中前后位置和大小顺序相反的数对,举个简单的例子:

{   1 , 4 , 2 , 3   } \{\ 1, 4, 2, 3 \ \} { 1,4,2,3 }

上面的排列中,有下面两个逆序对:

$$<4,2><4,3>$$

所以该排列的逆序数为 2

实现

• 朴素的实现很简明,我们遍历排列中所有的数对,检查是否形成逆序关系即可,示例代码如下(Lua):

function inverse_number(seq)
    local inv_num = 0
    
    for i = 1, #seq - 1 do
        for j = i + 1, #seq do
            if seq[i] > seq[j] then
                inv_num = inv_num + 1
            end
        end
    end
    
    return inv_num
end

• 上面的方法虽然简明,但是时间复杂度相对较高($O(n^2)$),这里我们假设排列中元素种类很少(譬如只有 $1,2,3,4$),那么更有效率的一种实现方法就是依次遍历排列元素,对于每一个遍历到的元素而言,该元素之前所有比他(该元素)大的元素,与该元素便形成了一个逆序对(即逆序数增一),依此我们便可以累加计算出排列的逆序数(Lua):

-- assume seq contains "1, 2, 3, 4" only
function inverse_number(seq)
    local inv_num = 0
    
    local count_buffer = { 0, 0, 0, 0 }
    
    for i = 1, #seq do
        if seq[i] == 1 then
            inv_num = inv_num + count_buffer[2] + count_buffer[3] + count_buffer[4]
            count_buffer[1] = count_buffer[1] + 1
        elseif seq[i] == 2 then
            inv_num = inv_num + count_buffer[3] + count_buffer[4]
            count_buffer[2] = count_buffer[2] + 1
        elseif seq[i] == 3 then
            inv_num = inv_num + count_buffer[4]
            count_buffer[3] = count_buffer[3] + 1
        else
            count_buffer[4] = count_buffer[4] + 1
        end
    end
  
    return inv_num
end

• 上面代码的时间复杂度虽然比较高效($O(n)$),但是通用性不高(限制了排列元素种类),我们可以简单扩展一下(Lua):

function inverse_number(seq)
    local inv_num = 0
    
    local count_buffer = {}
    
    for i = 1, #seq do
        for k, v in pairs(count_buffer) do
            if k > seq[i] then
                inv_num = inv_num + v
            end
        end
        
        count_buffer[seq[i]] = (count_buffer[seq[i]] or 0) + 1
    end
  
    return inv_num
end

• 实际上而言,上面实现的时间复杂度也是$O(n^2)$,但在元素种类受限的排列中,使用该实现来求取逆序数的速度仍是非常快的,另外的,我们还可以借用树状数组来进一步加速,有兴趣的朋友可以继续看看更多资料里的内容.

更多资料

• 逆序数的求法
• 求取一维数组中的逆序数