二分法？

来源: 古代的事物 于 2021-01-18 21:29:57 [] [旧帖] [给我悄悄话] 本文已被阅读： 次 (584 bytes)
回答: 不光是order, 比较的次数也应该最少才好 由 眼镜 于 2021-01-18 19:50:57

假定十六个数，线性比较按你的做法，比较次数在十五到三十一次之间。

分成八个二元组，每组排序，整数比较八次。

二元组配对比较，得出两个排序的新二元组，这个二元组比较的操作，需要整数比较一到二次，八个二元组，整数比较四到八次。。。

四个二元组，整数比较二到四次，

两个二元组，整数比较一到二次。

下限仍然是十五，上限是二十二次。 

 

所有跟帖： 

• 花哨啊。 数清楚比几次了么？ 反正我数不清你这个两分法 ：） -眼镜- ♂ 给 眼镜 发送悄悄话 (0 bytes) () 01/18/2021 postreply 22:05:39

请您先登陆，再发跟帖！