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}, 将其按从小到大的顺序排列。 算法分析: 冒泡 :CA\windows\syste32 md.exe 端开! score[1]=74 (即不 的序调 到后面 score[2]=79 水箱里core[3]85 泡都到 score[4]=88 为实现 score[5]=92 为了以 score[6]=93 不存放请按任意键继续
4.1.3 一维数组的应用 例4.3 给定由6个成绩组成的序列{92，88，74，93，85，79}， 将其按从小到大的顺序排列。 算法分析： • 冒泡排序法是一种交换排序方法，它的思路是：从序列的 一端开始，依次将相邻两个元素比较，当发现它们逆序 （即不合顺序）时就进行一次交换，本例需将较大的数调 到后面去，所以相邻元素中前者较大即为逆序。这样就像 水箱里的气泡一样，一个个地上浮到水面上，直到每个气 泡都到达它的平衡位置。 • 为实现这一算法，首先用一维数组score存储待排序的序列， 为了以后查找的方便，成绩从下标1处开始存放，下标0处 不存放数据
4.13一维数组的应用 例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 如果将soe视为水底 88》74,互换 88(92,不变74 的的 scor e[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个元素 开始，依次与相邻元素进 行比较，逆序则交换
4.13一维数组的应用 例4.3给定由6个成绩组成的序列{92,88,74,93,85,79}, 将其按从小到大的顺序排列。 算法分析: 为了表述方便,定义以下3个变量 (1)待排序的数的个数n(此处为6) (2)扫描遍数i(i=1,2,3,“n-1) (3)每遍扫描时待比较元素的下标j(j=1,2,3n-1) 算法步骤如下 (1)将待排序的数据放入数组中 (2)让i从1到n-1循环做步骤(3)(每遍扫描的循环) (3)让j从1到n-做步骤()(依次比较两个相邻数组元素, 以确定是否交换) (4)如果 score[j> score[j+1](逆序),则交换之 (5)输出排序结果
4.1.3 一维数组的应用 例4.3 给定由6个成绩组成的序列{92，88，74，93，85，79}， 将其按从小到大的顺序排列。 算法分析： 为了表述方便，定义以下3个变量 （1）待排序的数的个数n（此处为6） （2）扫描遍数i（i=1,2,3,…n-1） （3）每遍扫描时待比较元素的下标j（j=1,2,3,…n-i） 算法步骤如下 （1）将待排序的数据放入数组中 （2）让i从1到n-1循环做步骤(3)(每遍扫描的循环) （3）让j从1到n-i做步骤(4)(依次比较两个相邻数组元素， 以确定是否交换) （4）如果score[j]>score[j+1]（逆序），则交换之 （5）输出排序结果
413一维数组的应用 例4.3给定由6个成绩组成的序列{92,88,74,93,85,79}, 将其按从小到大的顺序排列。 算法分析: 算法的Ns图 for(i=1. i<n: itt) for(j=1; ji=n-i; j++, scoreljI>score Li+1] 是 交换scr[订与 scores+1]
4.1.3 一维数组的应用 例4.3 给定由6个成绩组成的序列{92，88，74，93，85，79}， 将其按从小到大的顺序排列。 算法分析： 算法的NS图