(应用排序算法编程7.2.2)POJ 2299 Ultra-QuickSort(使用归并排序来计算逆序对的个数)

/* 
 * POJ_2299.cpp 
 * 
 *  Created on: 2013年11月1日 
 *      Author: Administrator 
 */  
  
#include <iostream>  
#include <cstdio>  
  
using namespace std;  
  
const int maxn = 500010;  
  
typedef long long lolo;//这里不要使用int,因为a[i]的范围达到了999999999。在最坏的情况下,需要交换的次数已经不是int类型的数所能表示的了  
lolo a[maxn],t[maxn];  
lolo ans;  
  
//归并排序..归并排序是分治思想的一个典型的应用  
void my_sort(lolo l , lolo r){  
    if(l == r){  
        return ;  
    }  
  
    lolo mid = (l+r)/2;  
    my_sort(l,mid);  
    my_sort(mid+1,r);  
  
    lolo i = l,j = mid+1,now = 0;  
    while(i <= mid && j <= r){  
        if(a[i] > a[j]){  
            ans += (mid - i + 1);//当a[i]>a[j]时,a[i]后面的数都能与a[j]形成逆序对  
            t[++now] = a[j++];  
        }else{  
            t[++now] = a[i++];  
        }  
    }  
  
    while(i <= mid){  
        t[++now] = a[i++];  
    }  
  
    while(j <= r){  
        t[++now] = a[j++];  
    }  
  
    now = 0;  
    for(i = l ; i <= r ; ++i){//将临时数组t[]中的数组复制到a[]数组中  
        a[i] = t[++now];  
    }  
}  
  
int main(){  
    lolo n;  
  
    while(scanf("%lld",&n)!=EOF,n){  
        ans = 0;  
  
        lolo i;  
        for(i = 1 ; i <= n ;++i){  
            scanf("%lld",&a[i]);  
        }  
  
        my_sort(1,n);  
        printf("%lld\n",ans);  
    }  
  
    return 0;  
}  

补充：软件开发 , C++ ,

上一个：求一个正实数X的开方
下一个：C++ 转换构造函数 赋值语句