f*******w 发帖数: 1243 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: fenghaolw (生如夏花), 信区: JobHunting
标 题: 问个sorting相关的题
发信站: BBS 未名空间站 (Thu Sep 20 19:58:35 2012, 美东)
已知7个数,关系如下
x1 > x2 > x4
x2 > x5
x1 > x3 > x6
x3 > x7
问怎么排序是最优的,最优的方法worst case需要多少次比较
我是用merge sort的想法,先merge
x2, x4 和 x2, x5
需要1次比较 (x4 和 x5)
然后merge
x3, x6 和 x3, x7
需要1次比较 (x6 和 x7)
然后merge
x2, x4, x5 和 x3, x6, x7
需要5次比较(merge sort:3+3-1次比较)
所以总共是7次比较
但是不知道怎么证明是最优的?或者这样不是最优的? | r****o 发帖数: 1950 | 2 I think you are right.
Anyone have better ideas?
【在 f*******w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 【 以下文字转载自 JobHunting 讨论区 】 : 发信人: fenghaolw (生如夏花), 信区: JobHunting : 标 题: 问个sorting相关的题 : 发信站: BBS 未名空间站 (Thu Sep 20 19:58:35 2012, 美东) : 已知7个数,关系如下 : x1 > x2 > x4 : x2 > x5 : x1 > x3 > x6 : x3 > x7 : 问怎么排序是最优的,最优的方法worst case需要多少次比较
| x*******6 发帖数: 262 | |
|