poj2299 递归与分治策略

package hard;

import java.io.BufferedInputStream;
import java.util.Scanner;

/**
 * poj2299
 * 利用归并排序求逆序对
 * 如果是利用冒泡的话，超时！！！
 * @author NC
 */
public class Poj2299 {

    static long num = 0;//要long才能过啊。。。。

    public static void main(String[] args) {
        Scanner scan = new Scanner(new BufferedInputStream(System.in));
        while (scan.hasNext()) {
            int n = scan.nextInt();
            if (n == 0) {
                break;
            }
            num = 0;
            int data[] = new int[n];
            for (int i = 0; i < n; i++) {
                data[i] = scan.nextInt();
            }
            mergeSort(data, 0, n - 1);
            System.out.println(num);
        }
    }

    static void mergeSort(int[] array, int left, int right) {

        if (left < right) {
            int center = (left + right) / 2;
            mergeSort(array, left, center);
            mergeSort(array, center + 1, right);
            Merge(array, left, center, right);
        }
    }

    static void Merge(int[] array, int left, int center, int right) {
        //[1,2,3,4] left=1,ceter=2,right=4
        int[] temp = new int[right - left + 1];//存放被合并后的元素
        int i = left;
        int j = center + 1;
        int k = 0;
        while (i <= center && j <= right) {
            if (array[i] > array[j]) {
                temp[k++] = array[j++];
                /* array[i]后面的数字对于array[j]都是逆序的 */
                num += center - i + 1;

            } else {
                temp[k++] = array[i++];
            }
        }
        while (i <= center) {
            temp[k++] = array[i++];
        }
        while (j <= right) {
            temp[k++] = array[j++];
        }
        //把temp[]的元素复制回array[]
        for (i = left, k = 0; i <= right; i++, k++) {
            array[i] = temp[k];
        }
    }
}

#include <stdio.h>
#include <stdlib.h>
long long num ;//一样得用long long才能过
long data[500000];
long temp[500000];
 void Merge(long array[], long left, long center, long right) {
        //[1,2,3,4] left=1,ceter=2,right=4
        int i = left;
        int j = center + 1;
        int k = 0;
       
        while (i <= center && j <= right) {
            if (array[i] > array[j]) {
                temp[k++] = array[j++];
                /* array[i]后面的数字对于array[j]都是逆序的 */
                num += center - i + 1;

            } else {
                temp[k++] = array[i++];
            }
        }
        while (i <= center) {
            temp[k++] = array[i++];
        }
        while (j <= right) {
            temp[k++] = array[j++];
        }
        //把temp[]的元素复制回array[]
        for (i = left, k = 0; i <= right; i++, k++) {
            array[i] = temp[k];
        }
    }

     void mergeSort(long array[], long left, long right) {

        if (left < right) {
            long center = (left + right) / 2;
            mergeSort(array, left, center);
            mergeSort(array, center + 1, right);
            Merge(array, left, center, right);
        }
    }

    

int main() {
    long n = 0, i;
    while (scanf("%ld", &n)) {
        if (n == 0) {
            break;
        }
        for (i = 0; i < n; i++) {
            scanf("%ld", &data[i]);
        }
        mergeSort(data,0, n-1);
        printf("%lld\n", num);
        num = 0;
    }
    return 1;
}