4.13一维数组的应用 例4.2有10位学生的成绩存放在数组 score中,从键盘输入1个 数,使用折半查找法查找这个成绩是否在数组中,如果在, 输出其下标,如果不在,输出0。数组的下标表示第位学 生的成绩,数组的下标处不存储成绩 算法的NS图 输入待查找成绩x 初始化待查找区间上下界1o=1,high=n while(low<=high) 计算待查找元素下标nid=(low+high)/2 score lmld==x 是 否 score lmld」 查找成功是 否 退出循环查找前半区间查找后半区间 high=mid-1 low-mid+1 low<=high 是 否 匚查找成功,输出nd输出查找不成功
4.1.3 一维数组的应用 例4.2 有10位学生的成绩存放在数组score中，从键盘输入1个 数，使用折半查找法查找这个成绩是否在数组中，如果在， 输出其下标，如果不在，输出0。数组的下标i表示第i位学 生的成绩，数组的下标0处不存储成绩。 算法的NS图
4.13一维数组的应用 例4.2折半查找核心程序段 while(10W<=high)//只有待查找区间不为空,就循环 mid=(10W+high)/2;//计算中间元素下标 if( score[mid]=x)//中间元素与待查找元素相等,查找成功 break 退出循环 else if( (score [mid]>x)//中间元素较大,查找前半区间 high=mid-1;//修改待查找区间上界 else //中间元素较小,查找后半区间 low= mid +1: //修改待查找区间下界 if (low<= high //待查找区间不为空,查找成功 cout<"查找成功,待查找成绩是第“ <mid<位学生的成绩"<endl; e⊥se //待查找区间为空,査找不成功 cout<"未査找到该成绩!"<<endl;
4.1.3 一维数组的应用 例4.2折半查找 核心程序段 while(low <= high) // 只有待查找区间不为空，就循环 { mid = (low + high) / 2; // 计算中间元素下标 if(score[mid] == x) // 中间元素与待查找元素相等，查找成功 break; // 退出循环 else if(score[mid] > x) // 中间元素较大，查找前半区间 high = mid - 1; // 修改待查找区间上界 else // 中间元素较小，查找后半区间 low = mid + 1; // 修改待查找区间下界 } if(low <= high) { // 待查找区间不为空，查找成功 cout<<"查找成功，待查找成绩是第“ <<mid<<" 位学生的成绩"<<endl; } else { // 待查找区间为空，查找不成功 cout<<"未查找到该成绩！"<<endl; }
4.13一维数组的应用 例4.2折半查找 折半查找的查找效率要远高于顺序查找 折半查找需要存储数据的数组已经有序 x=55 x=12 513174246557094 513174246557094 Ow mid high low mid high 513174246557094 513174246557094 low mid hig low mid high 513174246557094 high low 查找成功 查找失败
4.1.3 一维数组的应用 例4.2折半查找 折半查找的查找效率要远高于顺序查找 折半查找需要存储数据的数组已经有序 5 13 17 42 46 55 70 94 low mid high x=55 5 13 17 42 46 55 70 94 low mid high 5 13 17 42 46 55 70 94 low mid high x=12 5 13 17 42 46 55 70 94 low mid high 5 13 17 42 46 55 70 94 high low 查找成功 查找失败
4.13一维数组的应用 例43给定由6个成绩组成的序列{92,88,74,93,85,79}, 将其按从小到大的顺序排列。 算法分析: 冒泡排序法是一种交换排序方法,它的略是:从序列的 端开始,依次将相邻两个元素比较,当发现它们逆序 即不合顺序)时就进行一次交换,本例需将较大的数调 到后面去,所以相邻元素中前者较大即为逆序这样就像 水箱里的气泡一样,一个个地上浮到水面上,直到每个气 泡都到达它的平衡位置。 为实现这一算法,首先用一维数组 score存储待排序的序列, 为了以后查找的方便,成绩从下标1处开始存放,下标0处 不存放数据
4.1.3 一维数组的应用 例4.3 给定由6个成绩组成的序列{92，88，74，93，85，79}， 将其按从小到大的顺序排列。 算法分析： • 冒泡排序法是一种交换排序方法，它的思路是：从序列的 一端开始，依次将相邻两个元素比较，当发现它们逆序 （即不合顺序）时就进行一次交换，本例需将较大的数调 到后面去，所以相邻元素中前者较大即为逆序。这样就像 水箱里的气泡一样，一个个地上浮到水面上，直到每个气 泡都到达它的平衡位置。 • 为实现这一算法，首先用一维数组score存储待排序的序列， 为了以后查找的方便，成绩从下标1处开始存放，下标0处 不存放数据
41.3一维数组的应用 例4.3冒泡排序算法分析 数组下标 score[i] score2]| score3 通过一遍扫描可将最小的 COXE [4] score[5] score[61 初始值 王sa数交换到 ]score[6] 92》88,互换 88 74 93 85 79 92》74,互换 93 92《93,不变 再进行一遍扫描,次小的 93》85,豆换|88 93 93》79,互换 88 74 92 85 nn数被交到 score[5]。 93 到达位 74 如果将Se1视为水底 88》74,互换 88(92,不变74 的 score[6]视为水面,则最 即日数大的数最先浮到水面然 3后次大的数也浮到水 74<88,不变74 面 ●●。●。● 88>85,互换74 8879,互换74 95 88到达位74 85 79 n个数排序,至多只需进行 74<85,不变74 85 2n1遍排序 8579,豆换74 85 93 85到达位 74 22每遍扫描中,从第1个元素 74<79,不变 RBs3开始,依次与相邻元素进 79到达位74 79 85 88 92 93 行比较,逆序则交换
4.1.3 一维数组的应用 例4.3 冒泡排序 算法分析 通过一遍扫描可将最小的 数交换到score[6]， 再进行一遍扫描，次小的 数被交换到score[5]。 如果将score[1]视为水底， score[6]视为水面，则最 大的数最先浮到水面，然 后 次 大 的 数 也 浮 到 水 面…… n个数排序，至多只需进行 n-1遍排序 每遍扫描中，从第1个元素 开始，依次与相邻元素进 行比较，逆序则交换