计算插入排序中的交换数量

Question

在这里给出的问题,我必须计算总数.使用插入排序对数组进行排序时所需的交换.
这是我的方法

#include <stdio.h>
int main()
{
    int t, N, swaps, temp, i, j;
    scanf("%d", &t);

    while(t--){
        scanf("%d", &N);

        int arr[N];
        swaps = 0;

        for(i=0; i<N; ++i){

            scanf("%d", &temp);

            j=i;
            while(j>0 && arr[j-1] > temp){
                arr[j] = arr[j-1];
                ++swaps;
                --j;
            }

            arr[j] = temp;
        }
        printf("%d\n", swaps);
    }

    return 0;
}

但是,这个soln超出了时间限制.

我怎样才能让它更快？
而且,这个问题的其他更好的解决方案是什么？

Answer 1

这是一个名为倒置计数的标准问题

这可以使用O(n*lg(n))中的mergesort来解决.这是我的倒数计数代码

int a[200001];
long long int count;
void Merge(int p,int q,int r)
{
    int n1,n2,i,j,k,li,ri;
    n1=q-p+1;
    n2=r-q;
    int l[n1+1],rt[n2+1];
    for(i=0;i<n1;i++)
        l[i]=a[p+i];
    for(i=0;i<n2;i++)
        rt[i]=a[q+1+i];
    l[n1]=LONG_MAX;
    rt[n2]=LONG_MAX;
    li=0;ri=0;
    for(i=p;i<=r;i++)
    {
        if(l[li]<=rt[ri])
            a[i]=l[li++];
        else
        {
            a[i]=rt[ri++];
            count+=n1-li;
        }
    }
}
void mergesort(int p,int r)
{
    if(p<r)
    {
        int q=(p+r)/2;

        mergesort(p,q);
        mergesort(q+1,r);
        Merge(p,q,r);
    }
}    
int main()
{
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    count=0;
    mergesort(0,n-1);
    printf("%lld\n",count);
}    

基本上反转计数的问题是找不到.对i和j,其中j> i使a [i]> a [j]

要知道这背后的想法,你应该知道基本的合并排序算法

http://en.wikipedia.org/wiki/Merge_sort

理念:

使用分而治之

除以:序列n的大小为两个大小为n/2的列表征服:递归计数两个列表组合:这是一个技巧部分(在线性时间内做)

结合使用合并和计数.假设两个列表是A,B.它们已经排序.从A,B产生输出列表L,同时还计算反转次数,(a,b)其中a是in-in A,b是-in B和a> b.

这个想法类似于merge-sort中的"merge".将两个已排序的列表合并到一个输出列表中,但我们也会计算反转.

每次a_i被附加到输出时,不会遇到新的反转,因为a_i小于列表B中剩下的所有内容.如果b_j被附加到输出,那么它小于A中的所有剩余项,我们增加了数量反转次数由A中剩余的元素数量计算.