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 的大作中提到】
: 【 以下文字转载自 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 | |
|
