# POJ 2299 Ultra-QuickSort C语言版

POJ题解 1974浏览

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
0
5
4
3
1
2
3
0

Sample Output

6
0

Slyar:题目本质就是求逆序对了，简单介绍一下。逆序对是指在序列{a0,a1,a2...an}中，若ai<aj(i>j)，则(ai,aj)上一对逆序对。而逆序数顾名思义就是序列中逆序对的个数。例如： 1 2 3是顺序，则逆序数是0；1 3 2中(2,3)满足逆序对的条件，所以逆序数只有1； 3 2 1中(1,2)(1,3)(2,3)满足逆序对，所以逆序是3。由定义不能想象，序列n的逆序数范围在[0,n*(n-1)/2]，其中顺序时逆序数为 0，完全逆序时逆序数是n*(n-1)/2。

PS.归并算法基本思路

### 网友最新评论 (4)

1. 确实不错啊，瞻仰
涛声依旧5年前 (2013-08-05)回复
2. merge sort 写的很清晰，逆序对分析也很到位！ 学习了！Thanks!
hua8年前 (2011-06-21)回复
3. 把你的POJ上的每一篇报告仔细研读了一下，收获很多，真是非常感谢你~~~呵呵
流觞8年前 (2011-04-18)回复
4. 真是太好了,谢谢！
Frank9年前 (2009-10-18)回复