笔者好长时间没有更新博客了,一个原因是开发的项目所用到的技术都是老技术点,所接触到的知识都是行业逻辑流程,所以只是自己做了总结并没有拿上来分享。另外一个原因是目前笔者在重新学习C++语言以及计算机的一些基本知识(算法等)。
下面的代码为C++代码,好了直接进入正题
折半查找又称二分查找。
使用条件:有序集合。
算法思想:先确定待查记录所在的范围(区间),然后逐步缩小范围直到找到或者不找到为止。
关键点在于比较中间位置所记录的关键字和给定值的比较,如果比给定值大(这里假设集合从小到大排列)那么可以缩小区间范围(集合开始-->中间位置的上一位),在比较该区间的中间位置所记录的关键字与给定值,依次循环到找到或者找不到位置。
举例编程:这里有一个整数数据 int a[10]={1,5,10,13,17,23,65,77,81,93};
1)这是递归(感谢园友zdd指出这里判断条件的错误,应该改为if(min>max))
|
2)非递归
|
性能分析:时间复杂度O(logn)
----------------------------------------------------------------------------------------------------
插入排序
使用条件:可对比大小的集合。
算法思想:将一个记录插入到已排好序的有序列中,从而得到一个新的,记录数增1的有序序列。待插记录依次比较已经排好序列,如果序列数大于该待插记录,那么该序列往后挪一位,直到找到序列小于待插记录,那么此时插入到该序列的后一个位置,依次上面操作,直至插完位置。