题目大意是求解快排最坏情况下的交换次数,我们知道,快速排序在最坏情况下会退化为冒泡排序,因此快排最坏情况下的交换次数也就是冒泡排序对应的交换次数。很容易想到这一题用冒泡排序,并记录交换次数就行了。
这样做看似可行,其实是行不通的,数据量是500000,由于冒泡排序的时间复杂度是O(N^2),所以问题的规模就是500000^2=2.5 * E11,一般我们认为计算机每秒的计算量是E9,因此用冒泡排序是行不通的。
联想有关排序的算法,我们希望这一题的时间复杂度能够降为O(NlogN),快排、堆排序、合并排序满足这样的要求,可是前两种排序方式的交换方式毫无规律可循,只剩下归并排序。
我们来看归并排序,它的核心是归并(由Merge()函数实现),就是将两个有序序列合并为一个有序序列。由冒泡排序我们知道,交换的总次数就是初始序列中每个元素交换次数的总和,每个元素的交换次数等于该元素后面比自己小的元素的个数(因为最终比自己小的元素都在自己前面)。
下图是一次Merge()过程:

可以看出,元素“1”没有移动,元素“4”向后移动了1位,元素“10”向后移动了3位,所以本次合并共移动了4次。统计合并排序过程中所有的移动次数即可。
本题代码如下


有关合并排序请参阅:
http://www.cppblog.com/hoolee/archive/2012/07/18/184029.html
posted on 2012-07-18 17:46 小鼠标 阅读(253) 评论(0)  编辑 收藏 引用 所属分类: 排序

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年7月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

随笔分类(111)

随笔档案(127)

friends

最新评论

  • 1. re: 线段树
  • 是这个样子的,所以在OJ有时候“卡住”了也不要太灰心,没准真的不是自己的原因呢。
    加油,祝你好运啦!
  • --小鼠标
  • 2. re: 线段树
  • 对于编程竞赛来说,Java所需时间一般为C/C++的两倍。合理的竞赛给Java的时间限制是给C/C++的两倍。
  • --伤心的笔
  • 3. re: poj1273--网络流
  • 过来看看你。
  • --achiberx
  • 4. re: (转)ubuntu11.10无法启动无线网络的解决方法
  • 膜拜大神。。查了一个下午资料终于在这里解决了问题。。神牛说的区域赛难道是ACM区域赛。。?
  • --Hang
  • 5. re: 快速排序、线性时间选择
  • 博主,谢谢你的文章。你的方法可以很好的处理分区基准在数组中重复的情况,书上的方法遇到这种输入会堆栈溢出。书上给出了解释但给的方法貌似不简洁。
  • --lsxqw2004

阅读排行榜