首页 > 其他 > 详细

归并排序(合并排序)(逆序对)

时间:2014-05-20 10:56:28      阅读:697      评论:0      收藏:0      [点我收藏+]

Description

 

在这个问题中,你需要分析一个对n个不同数排序的算法。该算法主要通过交换相邻数直到序列有序(升序)。比如:对输入序列

                      9 1 0 5 4

经过一系列交换后变成有序序列

                      0 1 4 5 9
你的任务是计算将序列变成有序最少需要经过多少次交换。

 

Input

 

输入包含多组测试数据。每组第一个是整数n<500,000,表示输入序列的长度,接下来是n行,每行有一个整数a[i](0≤a[i]≤999,999,999)。当n=0时表示结束。

 

Output

 

对每一组输入,输出该序列变成有序所需要交换的最少的次数。

 

Sample Input

5
9
1
0
5
4
3
1
2
3
0

Sample Output

6
0

Hint

 

选做


合并排序


Waterloo local 2005.02.05

 
 
 
代码:
 

  

归并排序(合并排序)(逆序对),布布扣,bubuko.com

归并排序(合并排序)(逆序对)

原文:http://www.cnblogs.com/ZhaoPengkinghold/p/3737694.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!