算法导论<二>

Merge sort

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

int f_min(int x,int y) {if(x<y)return x; else return y;}
int f_max(int x,int y) {if(x<y)return y; else return x;}

//double f_min(double x,double y) {if(x<y)return x; else return y;}
//double f_max(double x,double y) {if(x<y)return y; else return x;}
using namespace std;

const int MM = 111111;
#define maxint 0x3f3f3f3f
int N;
int num[MM];
int L[MM], R[MM],ans;
void get_data() {
    int i,j,k;
    for(i=1;i<=N;i++) scanf("%d",&num[i]);
}
void Merge(int*A,int p,int r,int q) {
    int i,j,k,len1,len2;
    len1=r-p+1, len2=q-r;
    for(i=0;i<len1;i++) L[i]=A[p+i];
    L[len1]=maxint;
    for(i=0;i<len2;i++) R[i]=A[r+1+i];
    R[len2]=maxint;
    i=j=0;
    for(k=p;k<=q;k++) {
        if(L[i]<=R[j]) A[k]=L[i++];
        else A[k]=R[j++];
    }
}
void Merge_sort(int*A,int p,int q) {
    if(p<q) {
        int mid=(p+q)>>1;
        Merge_sort(A,p,mid);
        Merge_sort(A,mid+1,q);
        Merge(A,p,mid,q);
    }
}
void solve() {
    int i,j,k;
    Merge_sort(num,1,N);
    for(i=1;i<=N;i++) printf("%d ",num[i]);
    printf("\n");
}

int main() {
    while(scanf("%d",&N)!=EOF) get_data(),solve();
    return 0;
}

Merge sort 计算逆序数

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

int f_min(int x,int y) {if(x<y)return x; else return y;}
int f_max(int x,int y) {if(x<y)return y; else return x;}

//double f_min(double x,double y) {if(x<y)return x; else return y;}
//double f_max(double x,double y) {if(x<y)return y; else return x;}
using namespace std;

const int MM = 111111;
#define maxint 0x3f3f3f3f
int N;
int num[MM];
int L[MM], R[MM],ans;
void get_data() {
    int i,j,k;
    for(i=1;i<=N;i++) scanf("%d",&num[i]);
}
int Merge(int*A,int p,int r,int q) {
    int i,j,k,len1,len2,ans;
    len1=r-p+1, len2=q-r;
    for(i=0;i<len1;i++) L[i]=A[p+i];
    L[len1]=maxint; 
    for(i=0;i<len2;i++) R[i]=A[r+1+i];
    R[len2]=maxint;
    i=j=ans=0;
    for(k=p;k<=q;k++) {
        if(L[i]>R[j]) ans+=len1-i;
        if(L[i]<=R[j]) A[k]=L[i++];
        else A[k]=R[j++];
    }
    return ans;
}
int Merge_sort(int*A,int p,int q) {
    int ret=0;
    if(p<q) {
        int mid=(p+q)>>1;
        ret+=Merge_sort(A,p,mid);
        ret+=Merge_sort(A,mid+1,q);
        ret+=Merge(A,p,mid,q);
    }
    return ret;
}
void solve() {
    int i,j,k;
    ans=Merge_sort(num,1,N);
    printf("%d\n",ans);
}

int main() {
    while(scanf("%d",&N),N) get_data(),solve();
    return 0;
}