二分搜索算法,插入排序算法
《算法》实验
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
实验序号:01 实验项目名称:二分搜索算法,插入排序算法
学 号 姓 名 专业、班
2014年9月 实验地点 指导教师 时间 一、实验目的及要求
二、实验设备(环境)及要求
PC机,Windows XP,DEV
三、实验内容要求
四、分析讨论
(根据实验写出一些心得或分析等)
六、教师评语 成绩
1(按时完成实验;
2(实验内容和过程记录完整;
3(回答问题完整、正确;
4(有实验的心得或讨论;
5(实验报告的撰写认真、格式符合要求,没有抄袭行为。
签名:
日期:2012.6
本实验的操作步骤如下。
二分搜索算法的逻辑步骤:
(1)令mid=(low+high)/2
(2)比较SearchKey与L[mid].Key只的大小,
若L[mid].Key=SearchKey,则查找成功,结束查找。
若L[mid].Key
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
明关键字为SearchKey的记录只可能存在于记录L[mid]的后半
部分,修改查找的范围,令low=mid+1,high的值保持不变;
若L[mid].Key>SearchKey,表明关键字为SearchKey的记录只可能存在于记录L[mid]的前半
部分,修改查找的范围,令high=mid-1,low的值保持不变;
(3)比较当前变量low与high的值,若low<=high,重复执行第(1)(2)步,若low>high,表明
整个表已经查找完毕,表中不存在关键字为SearchKey的记录,查找失败。
操作结果截图:
直接插入排序逻辑步骤:
设存在一个一维数组 array[1..n], 第 i 趟排序是将数组中下标为 i 的第 i + 1 个元素插入到一个已经按值有序排列的子序列的合适位置。
(1). 插入排序开始时, 第一个元素看成有序序列,从下标为 i = 2 的第二个元素开始,每一趟排序都将下标为 i 的元素插入到之前的有序序列中,然后 i = i + 1 进行下一个元素的插入排序,由此可见插入排序需要 n - 1 趟排序
(2). 每次寻找插入元素 array[i] 的位置时是从有序序列的最后一个元素 array[i-1] 开始查找,直到找到某一位置的元素 array[j] (j >= 0 && j <= i-1)满足 array[j] <= array[i], 那么下标为
j + 1 的位置就应该是插入元素 array[i]的合适位置。从有序序列的最后一个元素开始查找,边查找边移动元素,而不是先找到插入位置再移动元素,这样提高了效率。
(3). 将array数组中下标 [j + 1, i - 1]的所有元素依次后移一位,空出 array[j+1]的位置。 (4). 将array[i] 元素赋值给 array[j+1], 至此完成插入排序的一趟排序。 操作结果截图: