【4_2】数组2排序查找

1、2021-11-222021-11-232021-11-242021-11-252021-11-262021-11-272021-11-282021-11-29数据的有序插入算法数据的有序插入算法插入数据插入数据 在有序数组中插入数据后，数组仍然有序。在有序数组中插入数据后，数组仍然有序。 要求数组有足够的空间。要求数组有足够的空间。前提：被操作数组已经是有序数组，操作前前提：被操作数组已经是有序数组，操作前后不改变数组的有序性后不改变数组的有序性2021-11-210 升序升序插入某个数据算法插入某个数据算法ai-1.a1a0alength ai+1aikey ai-1. a1 a0 ai

2、ai+1 alength alength ai+1 aikey 插入过程：插入过程：(1) 确定数据插入位置确定数据插入位置i(2) 从最后一个元素开始逐个后移，直到将第从最后一个元素开始逐个后移，直到将第i个位个位置腾出。置腾出。(3) 将数据插入到相应位置中将数据插入到相应位置中ai-1key2021-11-2112021-11-212 升序升序插入某个数据算法插入某个数据算法优化算法优化算法-判断的同时，进行移位判断的同时，进行移位2021-11-213排序基本概念排序基本概念1、排序的功能：、排序的功能：将一组数据（或记录）的将一组数据（或记录）的任意序列任意序列，重新排成一个按关键字

3、，重新排成一个按关键字有序有序的序列。的序列。2、排序过程的组成步骤：、排序过程的组成步骤： 首先首先比较比较两个关键字的大小；两个关键字的大小； 然后将记录从一个位置然后将记录从一个位置移动移动到另一个位置。到另一个位置。2021-11-214 4.6.2 插入排序插入排序 基本思想：基本思想：从数组的第从数组的第2号元素开始，号元素开始，顺序从数组中取出元素，并将该元素顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当插入到其左端已排好序的数组的适当位置上。位置上。1、插入排序、插入排序:基本思想：基本思想：从数组的第从数组的第1号元素开始，顺序从数组中取出元素，号元素开始，

4、顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上并将该元素插入到其左端已排好序的数组的适当位置上待排元素序列：待排元素序列：53 27 36 15 69 42第一次排序：第一次排序： 27 53 36 15 69 42第二次排序：第二次排序： 27 36 53 15 69 42第三次排序：第三次排序： 15 27 36 53 69 42第四次排序：第四次排序： 15 27 36 53 69 42第五次排序：第五次排序： 15 27 36 42 53 69 线性插入排序示例线性插入排序示例对于有对于有n个数个数据元素的待排据元素的待排序列，插入操序列，插入操作要进行作要进行

5、n-1次次2021-11-216 1 3 5 7 9a0 a1 a2 a3 a4 a5插入位置插入位置pos key=4key插入前插入前： 1 3 4 5 7 9 key插入后插入后：插入元素插入元素xa0 a1 a2 a3 a4 a52021-11-2182021-11-2192021-11-220k=1k=2k=0k=12021-11-221k=3k=4k=3k=42021-11-222例初始： 49 38 65 97 76 13 27 kji=01349一趟： 13 38 65 97 76 49 27 i=12738二趟： 13 27 65 97 76 49 38 三趟： 13 27

6、38 97 76 49 65 四趟： 13 27 38 49 76 97 65 五趟： 13 27 38 49 65 97 76 六趟： 13 27 38 49 65 76 97 kkkkjjjjjjjjjj从小到大排序从小到大排序1 3 4 20 27 12 5ij指向最小从第从第i+1到第到第n-1个元素中个元素中选出最小元素所在位置选出最小元素所在位置k xk与与xi交换位置交换位置2021-11-2242021-11-225思想：思想：小的浮起，大的沉底。小的浮起，大的沉底。从左端开始比较。从左端开始比较。第第0趟：第趟：第0个与第个与第1个比较，大则交换；第个比较，大则交换；第1个与

7、个与第第2个比较，个比较， 大则交换，大则交换，到第到第n-1个个位置上位置上 关键字最大的记录交换到最后一个位置上；关键字最大的记录交换到最后一个位置上；第第1趟：对前趟：对前n-1个记录进行同样的操作，关键字个记录进行同样的操作，关键字次大的记录交换次大的记录交换 到第到第n-2个个位置上；位置上； 依次类推，则完成排序。依次类推，则完成排序。2021-11-226初始值初始值 46 55 13 42 94 5 17 70第第0趟结束趟结束 46 13 42 55 5 17 70 94 第第1趟趟 13 42 46 5 17 55 70 94 第第2趟趟 13 42 5 17 46 55

8、70 94 第第3趟趟 13 5 17 42 46 55 70 94 第第4趟趟 5 13 17 42 46 55 70 94 46 13 55 42 94 5 17 7046 13 42 55 94 5 17 7046 13 42 55 5 94 17 7046 13 42 55 5 17 94 70第第0趟开始趟开始2021-11-2282021-11-2292021-11-2302021-11-231思想：先确定待查找记录所在的范围，然后逐步缩小范思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。围，直到找到或确认找不到该记录为止。前提：必须在前提：必须

9、在有序表有序表中进行。中进行。分三大步骤：分三大步骤：（1）确定范围）确定范围low,high（2）确定中间位置确定中间位置:mid=(high+low)/2(3)比较比较amid与与 key的关系的关系分三种情况：分三种情况：1 1）若中间项的值等于）若中间项的值等于k,k,则说明已查到，返回则说明已查到，返回midmid2 2）若）若k k小于中间项的值，则在线性表的前半部分查找；小于中间项的值，则在线性表的前半部分查找；high=mid-1high=mid-13 3）若）若k k大于中间项的值，则在线性表的后半部分查找大于中间项的值，则在线性表的后半部分查找;low=mid+1;low=

10、mid+12021-11-232mid=(low+high)/2不进位取整不进位取整low：下界：下界high ：上界：上界k=r(mid) : 查找成功，返回查找成功，返回midk r(mid) : low=mid+1 继续继续lowhigh: 查找不成功查找不成功2021-11-233 8 17 25 44 68 77 98 100 115 125 查找查找 k=171 2 3 4 5 6 7 8 9 10mid=(1+10)/2=5mid=(1+4)/2=2lowhighmidmid=(low+high)/2不进位取整不进位取整 8 17 25 44 68 77 98 100 115 125lowhigh=mid-1mid查找成功！查找成功！ 8 17 25 44 68 77 98 100 115 125 查找查找k=1201 2 3 4 5 6 7 8 9 10lowhighmidmid=(1+10)/2=5 8 17 25 44 68 77 98 100 115 125 highlowmidmid=(6+10)/2=8 8 17 25 44 68 77 98 100 115 125 highlowmidmid=(9+10)/2=9 8 17 25 44 68 77 98 100 115 125 highlowmidmid=(10+10)/2=10