原题：Ultra-QuickSort
题目内容：
在这个问题中，你需要分析特别的算法。这个算法通过对一个包含n个元素的进行操作，一直交换相邻的两个序列的元素直到整个序列呈升序排列。对于输入序列9 1 0 5 4 ,Ultra-QuickSort最终得到的输出为0 1 4 5 9 .你的任务就是来计算出Ultra-QuickSort 至少需要多少swap操作来最终达到对一个给定的输入序列排好序的目标。
输入格式:
输入包括多组测试数据。每组测试数据以一行包括一个单独的整数n开始（n<500,000,是输入序列的长度）。每组测试数据接下来的n行包括一个单独的整数a[i]，a[i]≤ 999,999,999,代表输入序列第n个元素。输入以一个长度n为0的序列终止。这个序列不应该被处理。
输出格式：
对于每组测试数据，你的程序应该输入单独的一行，包括一个整数op，代表对该输入序列进行排序所需要最小的交换次数。 输入样例：
5 9 1 0 5 4 3 1 2 3 0 输出样例 6 0
#include<iostream> using namespace std; const int N=5e5+10; int num[N]; int tmp[N]; long long sum; //归并模板 void merge(int low, int mid, int high) { int i,j,k; i=k=low;//左指针 j=mid+1;//右边那个数组指针 while(i<=mid && j<=high)//有一个没有到最后 { if(num[i]<num[j])//左边的数字小的话 tmp[k++]=num[i++];//把左边的数存下来，总是存小的数 else { sum+=j-k;//总的逆序数，单纯的归并排序没有这个 tmp[k++]=num[j++];//存右边的小数字 } } while(i<=mid)//左边还没有走到头 tmp[k++]=num[i++];//存剩下的数字 while(j<=high)//右边没到头 tmp[k++]=num[j++];//存右边的数字 for(i=low; i<=high; ++i)//又放回去了 num[i]=tmp[i];//合并完成 } void mergeSort(int a, int b) { int mid; if(a<b) { mid=(a+b)/2; mergeSort(a, mid);//排左边 mergeSort(mid+1, b);//排右边 merge(a, mid, b);//合并 } } int main() { int n; while(cin>>n) { int i; sum=0;//记得归零啊 if(n==0) break; for(i=0;i<n;i++) { cin>>num[i]; } mergeSort(0,n-1); cout<<sum<<endl; } return 0; }