1、折半搜索算法

（1）算法代码：

（2）复杂性分析

任何一种以比较为基础的搜索算法，在最坏情况下所用的时间都不可能低于 (log ) n  ，因此，也就不可能存在最坏情况下所需时间比折半搜索数量级还低的算法。

2、排序问题

2.1归并排序算法

（1）归并排序算法思想

该算法采用分治方法，将要排序的数组分成两部分，先对每部分进行排序，然后将两部分的元素按不降顺序放在一个新数组中。这一过程可能需要多次分解和合并，因此是一个递归过程。

（2）合并两个有序组

（3）归并排序主程序

该算法的最好、最坏和平均时间复杂性都是双界nlog n。

2.2 快速排序算法

（1）划分程序

（2）算法主程序

（3）复杂性分析

快速排序与归并排序具有相同的平均时间复杂性。但实际表现有所不同，快速排序一般要比归并排序用时少。
注：在快速排序中，如果划分元素是随机选取的，则几乎可以保证不会出现最坏情况，几乎都在平均时间内完成。

几种排序算法的时间复杂性比较

分治算法

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们