问个sorting相关的题# JobHunting - 待字闺中
f*w
1 楼
已知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次比较
但是不知道怎么证明是最优的？或者这样不是最优的？
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次比较
但是不知道怎么证明是最优的？或者这样不是最优的？
