線代：求解排列中的逆序數

• 這一系列的工程數學教程面向的是已經掌握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