归并排序模板 && 求逆序数

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 04 月 21 日
#include<stdio.h>  
#include<stdlib.h>  
//归并排序模板  
typedef int ElementType;  
int ans;  
void Merge(ElementType A[], ElementType TmpArray[], int Lpos, int Rpos, int RightEnd)  
{  
    int i , LeftEnd, NumElements, TmpPos;  
    LeftEnd = Rpos - 1;  
    TmpPos = Lpos;  
    NumElements = RightEnd - Lpos + 1;  
    while(Lpos <= LeftEnd && Rpos <= RightEnd)  
    {  
        if(A[Lpos] <= A[Rpos])  
            TmpArray[TmpPos++] = A[Lpos++];  
        else  
        {  
            ans += (LeftEnd - Lpos + 1);   
            TmpArray[TmpPos++] = A[Rpos++];  
        }  
    }  
    while(Lpos <= LeftEnd)   
    {  
        TmpArray[TmpPos++] = A[Lpos++];  
    }  
    while(Rpos <= RightEnd)  
    {  
        TmpArray[TmpPos++] = A[Rpos++];  
    }  
    for(i = 0; i < NumElements; ++i, --RightEnd)  
        A[RightEnd] = TmpArray[RightEnd];  
}  
void MSort(ElementType A[], ElementType TmpArray[], int Left, int Right)  
{  
    int Center = 0;  
    if(Left < Right)  
    {  
        Center = (Left + Right) >> 1;  
        MSort(A, TmpArray, Left, Center);  
        MSort(A, TmpArray, Center + 1, Right);  
        Merge(A, TmpArray, Left, Center + 1, Right);  
    }  
}  
void MergeSort(ElementType A[], int N)  
{  
    ElementType* TmpArray = NULL;  
    TmpArray = (ElementType*) malloc(N * sizeof(ElementType));  
    if(NULL != TmpArray)  
    {  
        MSort(A, TmpArray, 0, N - 1);  
        free(TmpArray);  
    }  
    else  
        printf("allocate temp memory fail\n");  
}  
int Arr[1001];  
int main(int argc, char* argv[]){  
    //freopen("1.txt","r",stdin);  
    int n;  
    while(scanf("%d",&n)!=EOF){  
        for (int i=0;i<n;i++)  
            scanf("%d",&Arr[i]);  
        ans = 0;  
        MergeSort(Arr,n);  
        printf("%d\n",ans);  
    }  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日