poj 2299 Ultra-QuickSort(歸并排序)

題目：​​http://poj.org/problem?id=2299​​

Ultra-QuickSort

Time Limit: 7000MS	Memory Limit: 65536K
Total Submissions: 49165	Accepted: 17984

Description

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence 

9 1 0 5 4 ,

Ultra-QuickSort produces the output 

0 1 4 5 9 .

Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

Sample Input

5

9

1

5

4

3

1

2

3

Sample Output

60

本來想用這題來練習線段樹的，結果怎麼也想不到那裡去。後來看别人的代碼才明白每個葉子節點存儲的不是依據dex存儲val[i]而是依據dex在相應位置存儲1，然後根據排好序的序列由val[i]追蹤dex，左邊的1都加起來（逆序數），然後去掉dex的1，如此反複進行就能到達目的。送出代碼時我可沒這麼做，用歸并排序累加每一次相鄰的交換數就是最終的結果。（臨時在百度百科上學習了歸并排序||-_-）

冒泡排序的時間的複雜度是O(n^2）.

冒泡排序算法的運作如下：（從後往前）

比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。

針對所有的元素重複以上的步驟，除了最後一個。

持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。

并歸排序的時間複雜度：O(nlogn)

設有數列{6，202，100，301，38，8，1}

初始狀态：6,202,100,301,38,8，1

第一次歸并後：{6,202},{100,301},{8,38},{1}，比較次數：3；

第二次歸并後：{6,100,202,301}，{1,8,38}，比較次數：4；

第三次歸并後：{1,6,8,38,100,202,301},比較次數：4；

總的比較次數為：3+4+4=11,；

逆序數為14；

歸并排序的優勢：分治法，已比較了的小部分不再比較，如：{8,38},{1}變成{1,8,38}隻比較1和8後{1}的長度成為0，不再比較，直接寫下{8,38}。

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=5e5+10;
int a[maxn],b[maxn];
long long sum;
void Merge(int sourceArr[],int tempArr[],int startdex,int middex,int enddex)
{
    int i = startdex,j=middex+1,k = startdex;
    while(i<=middex && j<=enddex)
    {
        if(sourceArr[i]<sourceArr[j])
            tempArr[k++] = sourceArr[i++];
        else
            tempArr[k++] = sourceArr[j++],sum+=(middex+1-i);  //if sum++; not adjacent exchange
    }
    while(i!=middex+1)
        tempArr[k++] = sourceArr[i++];
    while(j!=enddex+1)
        tempArr[k++] = sourceArr[j++];
    for(i=startdex;i<=enddex;i++)
        sourceArr[i] = tempArr[i];
}

void MergeSort(int sourceArr[],int tempArr[],int startdex,int enddex)
{
    int middex;
    if(startdex<enddex)
    {
        middex=(startdex+enddex)/2;
        MergeSort(sourceArr,tempArr,startdex,middex);
        MergeSort(sourceArr,tempArr,middex+1,enddex);
        Merge(sourceArr,tempArr,startdex,middex,enddex);
    }
}
int main()
{
    //freopen("cin.txt","r",stdin);
    int n;
    while(cin>>n&&n){
        sum=0;
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        MergeSort(a,b,0,n-1);
        printf("%lld\n",sum);
    }
    return 0;
}