线代：求解排列中的逆序数

• 这一系列的工程数学教程面向的是已经掌握C语言编程基础读者

我们知道所谓逆序数就是求出一个数组中的每一项的之前的若干项中有多少项比它大，就叫做逆序数，把所有项的逆序数的加起来就是这个排列的逆序数。逆序数在排列中运用广泛。

举例：比如 3,5,1,4,7,2,6这个数列中

3 在首位所以逆序数是0

5 之前的3比5小，所以逆序数也是0

1 之前有3和5都比它大，所以逆序数是2

以此类推

4 的逆序数是1

7 的逆序数是0

2 的逆序数是4

6 的逆序数是1

所以这个排列的逆序数是0+0+2+1+0+4+1=8

C语言实现：

//这是实现逆序数的程序
#include<stdio.h>

int main()
{
    int i,j,a[10],ni,nisum=0;
    printf("请输入由一个十个整数元素组成排序:\n");    
    for(i=0;i<10;i++)
    {
        printf("第%d个元素:",i+1);
        scanf("%d",&a[i]);
        printf("\n");
    }
    printf("逆序数为 0");
    for(i=1;i<10;i++)
    {
        ni=0;
        for(j=0;j<i;j++)
        {
            if(a[i]<a[j])
            {
                ni++;
            }
        }
        printf("+%d",ni);
        nisum=nisum+ni;
    }
    printf("=%d\n",nisum);
    return 0;
}

C语言程序的精简形式(和上面一样，只是删除了一些啰嗦的内容)

#include<stdio.h>
main()
{
    int i,j,a[10],ni,nisum=0;
    printf("请输入由一个十个整数元素组成排序:\n");    
    for(i=0;i<10;i++)
    {
        printf("第%d个元素:",i+1);
        scanf("%d",&a[i]);
        printf("\n");
    }
    printf("逆序数为 0");
    for(i=1;i<10;i++)
    {
        ni=0;
        for(j=0;j<i;j++)
            if(a[i]<a[j])
                ni++;
        printf("+%d",ni);
        nisum+=ni;
    }
    printf("=%d\n",nisum);
}

更精简但是不推荐的形式：

#include<stdio.h>
main()
{
    int i,j,a[10],ni,nisum=0;
    printf("请输入由一个十个整数元素组成排序:\n");    
    for(i=0;i<10;i++)
    {
        printf("第%d个元素:",i+1);
        scanf("%d",&a[i]);
        printf("\n");
    }
    printf("逆序数为 0");
    for(i=1;i<10;i++)
    {
        ni=0;
        for(j=0;j<i;a[i]<a[j]?ni++:0,j++);
        printf("+%d",ni);
        nisum+=ni;
    }
    printf("=%d\n",nisum);
}

参考文献:

1. 同济大学数学系 工程数学—线性代数 北京:高等教育出版社 2007