合併排序Inversion應用

• 題目概述:有一n大小的沒排序字串，ex{3, 1, 9, 8, 9, 2}，一共有(3, 1)、(3, 2)、(9, 8)、(9, 2)、(8, 2)、(9,2)六個反序對，請 注意到序列中有兩個 9 都在 2 之前，因此有兩個(9, 2)反序對， 也就是說，不 同位置的反序對都要計算，不管兩隊的內容是否一樣。請撰寫一程式， 計算一個數列 A 的反序對數量 W(A)。

python

import sys
try:
    while True:
        n=int(input())
        case=[int(x) for x in input().split()]
        sum=0
        sys.setrecursionlimit(10000000)#遞迴最大上限
        def mergeList(leftList, rightList):
            global sum  #使用global才能在函式中使用全域變數
            if len(leftList) == 0: #如果左邊沒東西，理所當然直接傳右邊的值
                return rightList 
            elif len(rightList) == 0: 
                return leftList 
            elif leftList[0] > rightList[0]:
                """
                 sum要取的是所有前面元素大於後面元素的數量，而rightList是已經排序過的數列，
                所以當leftList[0]大於rightList[0]的時候，等同於rightList[0]後面的元素都小於leftList[0]
                """
                sum=sum+len(rightList)
                return [leftList[0]] + mergeList(leftList[1:], rightList)
            else: 
                return [rightList[0]] + mergeList(leftList, rightList[1:])


        def chopList(sourceList):
            if 1 >= len(sourceList):#如果sourceList大小為一，就該開始回傳
                return sourceList

            Key = len(sourceList)//2
            leftList = []#製作存放兩邊的空陣列
            rightList = []
            leftList = sourceList[0:Key]
            rightList = sourceList[Key:]

            leftData = chopList(leftList)
            rightData = chopList(rightList)
            return mergeList(leftData, rightData)


        chopList(case)

        print(sum)


except EOFError:
    pass

如果覺得上面程式不好懂的話，可以用python tutor跑一次會比較明瞭

在運行超過50000筆資料的時候，上面的我寫的python程式，運行時間實在是蠻久的，超過3秒，所以我寫了一個C版本的，速度快很多，就算到100000比，運行也不到1秒

C

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
#define ll long long int

vector<ll> task;
ll sum=0;

void merge(vector<ll>&arr,ll l,ll m,ll r)
{
    ll L_size, R_size, i, j, k;
    L_size = m - l + 1;          
    R_size = r - m;
    ll L[L_size], R[R_size]; 
    for (i = 0; i < L_size; i++) 
    {
        L[i] = arr[l + i];
    }

    for (j = 0; j < R_size; j++)
    {
        R[j] = arr[m + 1 + j];
    }

    i = 0;
    j = 0;
    k = l;
    while (i < L_size && j < R_size)
    {
        if (L[i] > R[j])
        {
            arr[k] = L[i];
            sum = sum + (R_size - j);
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < L_size) //把剩下的元素塞進arr裡
    {
        arr[k] = L[i];
        k++;
        i++;
    }

    while (j < R_size)
    {
        arr[k] = R[j];
        k++;
        j++;
    }
}

void cut(vector<ll> &datalist, ll l, ll r)
{
    if(l<r)
    {
        ll center = (l + r-1) / 2;
        cut(datalist, l, center);
        cut(datalist, center+1, r);
        merge(datalist, l, center, r);
    }
}

int main()
{
    ll n,r;
    while(scanf("%lld",&n)!=EOF)
    {
        for (ll i = 0; i < n;i++)
        {
            scanf("%lld", &r);
            task.push_back(r);
        }
        ll l = 0, r = n - 1;

        sum = 0;
        cut(task, l, r);
        printf("%lld\n", sum);

        task.clear();
    }
}