nyoj322 sort 归并排序，树状数组

超、凢脫俗 2022-01-07 16:05 215阅读 0赞

## Sort ##

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 4

描述

You want to processe a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. Then how many times it need.  
For example, 1 2 3 5 4, we only need one operation : swap 5 and 4.

输入

The input consists of T number of test cases.(<0T<1000) Each case consists of two lines: the first line contains a positive integer n (n <= 1000); the next line contains a permutation of the n integers from 1 to n.

输出

For each case, output the minimum times need to sort it in ascending order on a single line.

样例输入

2
    3
    1 2 3
    4
    4 3 2 1

样例输出

0
    6

如果按冒泡排序这些O(n^2)肯定会超时，所以需要找一种更快的方法 --------归并排序。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用[分治法][Link 1]的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。这题还可以用树状数组来做

法一：用归并排序做

#include<stdio.h>
    int a[1000001],b[1000001]; /*合并排序结果先保存到b中*/
    int merge(int a[],int low,int mid,int high)
    {
        int i=low,j=mid+1,k=low;
        int count=0;/*计数器*/ 
        while((i<=mid)&&(j<=high))/*部分合并*/
        {
            if(a[i]<=a[j])
            {
                b[k++]=a[i++];
            }
            else
            {
                b[k++]=a[j++];
                count+=(mid-i+1);
            }
        }
        while(i<=mid)/*转储剩余部分*/
        {
            b[k++]=a[i++];
        }
        while(j<=high)
        {
            b[k++]=a[j++];
            
        }
        for(i=low;i<=high;++i)/*把b中的值复制给a*/
        {
            a[i]=b[i];
        }
        return count;
    }
    int sort(int a[],int low,int high)
    {
        int x,y,z;
        int mid=(high+low)/2;
        int i=low,j=mid+1;
        if(low>=high)
        {
            return 0;
        }
        x=sort(a,low,mid);
        y=sort(a,mid+1,high);
        z=merge(a,low,mid,high);
        return (x+y+z);
    }
    int main()
    {
        int ncases,n,i;
        scanf("%d",&ncases);
        while(ncases--)
        {
            scanf("%d",&n);
            for(i=0;i<=n-1;i++)
            {
                scanf("%d",&a[i]);
            }
            printf("%d\n",sort(a,0,n-1));
        }
        return 0;
    }

法二：用树状数组

不知道什么是树状数组的 就先看看树状数组吧。。链接：[http://dongxicheng.org/structure/binary\_indexed\_tree/][http_dongxicheng.org_structure_binary_indexed_tree]

#include<stdio.h>
    #include<string.h>
    int num[1004],n;
    int lowbit(int x)
    {
        return x&(-x);
    }
    void add(int x)
    //更新含有x的数组个数
    {
        while(x<=n)
        {
            num[x]++;
            x+=lowbit(x);
        }
    }
    int sum(int x)
    //向下统计小于x的个数
    {
        int total=0;
        while(x>0)
        {
            total+=num[x];
            x-=lowbit(x);
        }
        return total;
    }
    int main()
    {
        int x,cases;
        scanf("%d",&cases);
        while(cases--)
        {
            scanf( "%d",&n);
            memset( num,0,sizeof( num ));
            int ss = 0;
            for( int i = 0; i < n; ++i )
            {
                scanf( "%d",&x);
                add(x);
                ss += (i-sum( x - 1 ));
            }
            printf( "%d\n",ss );
        }
        return 0;
    }

转载于:https://www.cnblogs.com/lovychen/p/3238090.html

[Link 1]: http://baike.baidu.com/view/1583824.htm
[http_dongxicheng.org_structure_binary_indexed_tree]: http://dongxicheng.org/structure/binary_indexed_tree/