[求助][讨论]插入排序的改进 - C++教室 - C++论坛

编程论坛 → 开发语言 → C++论坛 → 『 C++教室』 → [求助][讨论]插入排序的改进

标题：[求助][讨论]插入排序的改进

取消只看楼主

aipb2007

来　自：CQU
等　级：贵宾
威　望：40
帖　子：2879
专家分：7
注　册：2007-3-18

问题点数：0 回复次数：2

[求助][讨论]插入排序的改进

有没有可能利用2分搜索，取代常规插入排序中的线性查找插入。
这样的话，可以把时间代价由 O（n^2）改进至 O（nlgn）。

大家说说看法！

搜索更多相关主题的帖子: 改进　讨论　

2007-07-21 12:25

aipb2007

来　自：CQU
等　级：贵宾
威　望：40
帖　子：2879
专家分：7
注　册：2007-3-18

得分:0

回复：（maoguoqing）不仅2分搜索，那串已经排好的序列...

莫非还可以三分搜索？这样有价值吗？

虽然可以，但是有个问题，插入要移位，所以还是要花费O(n)的时间代价。
这样一来，2分搜索不就没意义了？

不知道我表达清楚没有。！！！

Ｆight ｔｏｗin or ｄie...

2007-07-21 13:59

aipb2007

来　自：CQU
等　级：贵宾
威　望：40
帖　子：2879
专家分：7
注　册：2007-3-18

得分:0

又想了想，不能实现。

看来插入排序只能O(n^2)了。

Ｆight ｔｏｗin or ｄie...

2007-07-23 18:28