第8章数组
第 8 章 数 组
本章知识点8.1一维数组的定义、引用与初始化数组名+一维下标”--表示数据8.2一维数组的应用8.3二维数组“数组名+二维下标”--表示数据8.4数组与函数
本章知识点 8.1 一维数组的定义、引用与初始化 “数组名+一维下标”-表示数据 8.2 一维数组的应用 8.3 二维数组 “数组名+二维下标”-表示数据 8.4 数组与函数
8.2一维数组的应用8.2.3排序问题一P152【例8.7】选择法排序：用选择法将10个整数从小到大排序输出。排序算法很多-最基础的是选择法排序。三个数排序的算法：1intx,y,z,t;I/ 要求3个数从小到大2scanf("%d %d %d",&x,&y,&z)3if (x>y)(t=x; x=y;y =t;)从3个数找最小值5if (x>z)存入x6( t = z; z = x; x = t;)从2个数找最小if (y>z)值存入y8(t=y; y=z; z=t})9printf("%d,%d,%d\n",x,y,z);3/115
【例8.7】选择法排序：用选择法将10个整数从小到大排序输出。 排序算法很多-最基础的是选择法排序。 3/115 8.2.3 排序问题—P152 8.2 一维数组的应用 三个数排序的算法： ① int x,y,z,t; // 要求3个数从小到大 ② scanf("%d %d %d",&x,&y,&z); ③ if (x>y) ④ { t = x; x = y; y = t;} ⑤ if (x>z) ⑥ { t = z; z = x; x = t;} ⑦ if (y>z) ⑧ { t = y; y = z; z = t ;} ⑨ printf("%d,%d,%d\n",x,y,z); 从3个数找最小值 存入x 从2个数找最小 值 存入 y
3个数的排序过程：(1）通过2 次比较，最小数与第1个数交换一第一趟选择排序的结果：3个数中最小数存入第1个数。(2）通过1次比较，将剩余的2个数中的小数与第3个数交换一第二趟选择排序结果：3个数中次小数存入第2个数。(3）放在第3个数的位置上第3个数就是最大值，结论：3个数的排序一一是2次找最小值的过程
3个数的排序过程： (1) 通过 2 次比较，最小数与第 1 个数交换—第一趟选 择排序的结果：3个数中最小数存入第 1 个数。 (2) 通过1次比较，将剩余的2个数中的小数与第 3 个数交 换—第二趟选择排序结果： 3个数中次小数存入第2个数。 (3) 第3个数就是最大值，放在第3个数的位置上。 结论：3个数的排序-是 2 次找最小值的过程
【例8.7】选择排序法■编程：对n个数排序（按由小到大顺序）。选择法思路：每次选择未排好序的数中最小的放在前面，n个数的排序就是n-1次找最小值的过程选择排序过程：n 个数的排序就是 n-1 次找最小值的过程，即：(1）首先通过 n-1 次比较，从 n个数中找出最小数，将它与第1个数交换一第一趟选择排序一一一结果：最小数被存入第1个数。(2）再通过n-2次比较，从剩余的n-1个数中找出次小次小数数，将它与第2个数交换一第二趟选择排序一一一结果：存入第 2 个数。(3）重复上述过程，共经过n-1趟排序后，排序结束。5/115
【例8.7】选择排序法 ◼编程：对n个数排序(按由小到大顺序)。 ◼选择法思路：每次选择未排好序的数中最小的放在前面，n 个数的排序就是n-1次找最小值的过程。 5/115 选择排序过程： n 个数的排序就是 n-1 次找最小值的过程，即： (1) 首先通过 n-1 次比较，从 n 个数中找出最小数， 将 它与第1个数交换—第一趟选择排序-结果：最小数被存入 第 1 个数。 (2) 再通过 n-2 次比较，从剩余的 n-1 个数中找出次小 数，将它与第2个数交换—第二趟选择排序-结果：次小数 存入第 2 个数。 (3) 重复上述过程，共经过 n-1 趟排序后，排序结束
用选择法对10个数按从小到大升序排序--算法（假设n=10）：1、首先找出10个数中的最小数，并存入a[0]中。将a[0]与a[1]、a[2]、a[3]、a[9]进行比实现方法：较，若a[0]大于任何一个--交换最后a[是最小值2、找出10个数中的次小数，并存入a[1]中。实现方法：将a[]]与a[2]、a[3]、a[9]进行比较，若a[i]大于任何一个--交换1———-最后a[1]是次小值。3、找出10个数中的次次小数，并存入a[2]中。将a[2]与a[3]、.a[9]进行比较，若a[2]大实现方法：于任何一个一交换最后a[2]是次次小值
用选择法对10个数按从小到大升序排序-算法（假设n=10）： 1、首先找出10个数中的最小数，并存入a[0]中。 实现方法：将a[0]与a[1] 、a[2]、a[3]、.a[9]进行比 较，若a[0]大于任何一个-交换-最后a[0]是最小值。 2、找出10个数中的次小数，并存入a[1]中。 实现方法：将a[1]与 a[2]、a[3]、.a[9]进行比较，若 a[1]大于任何一个-交换-最后a[1]是次小值。 3、找出10个数中的次次小数，并存入a[2]中。 实现方法：将a[2]与a[3]、.a[9]进行比较，若a[2]大 于任何一个-交换-最后a[2]是次次小值。
n个数的选择法排序是个两重循环外循环控制求最小值的次数---（n-1）次求最小值用n-1次外循环实现。---假设外循环变量为i，则i的循环范围是0~n-2。内循环完成求一个最小值的过程：假设当前元素a[为最小值位置、假设内循环变量为j，让a与其后的所有元素ai逐个比较，j的范围是+1~~n-1。例8.7一n个数从小到大排序（选择法排序）①#includea[j])(t=a[i]：a[i]=a[]:a[]=t：]//交换数据1for(i=;i<n;i++) printf("%d ",a[ij):printf("\n");return 0;思考：加上数据的原来的序号？
n个数的选择法排序是个两重循环 ➢ 外循环控制求最小值的次数-（n-1）次求最小值用n-1次外循环实现。 -假设外循环变量为 i，则 i 的循环范围是0~n-2。 ➢ 内循环完成求一个最小值的过程：假设当前元素a[i]为最小值位置、假设内循环变量为 j， 让a[i]与其后的所有元素a[j]逐个比较，j的范围是i+1~~n-1。 例8.7-n个数从小到大排序（选择法排序） ① #include ② int main() ③ { int a[10],i,j,t,n=10; ④ for (i=0;ia[j]) ⑨ { t=a[i]; a[i]=a[j]; a[j]=t; }//交换数据 ⑩ } ⑪ } ⑫ for(i=0;i<n;i++) printf("%d ",a[i]); ⑬ printf("\n"); ⑭ return 0; ⑮ } 思考：加上数据的原来的序号？
选择法排序(从小到大)第一轮查找最小值的过程-举例i=08653291071-----初始数据A810.310.e2G.10329653298106154J8921076534
• 10 9 8 7 6 5 4 3 2 1-初始数据 • 9 10 8 7 6 5 4 3 2 1 • 8 10 9 7 6 5 4 3 2 1 • 7 10 9 8 6 5 4 3 2 1 • 6 10 9 8 7 5 4 3 2 1 . • 1 10 9 8 7 6 5 4 3 2 j i=0 j j j j 选择法排序(从小到大)第一轮查找最小值的过程-举例
，选择排序有什么缺陷？-多余的交换如何修改？----P1551）定义一个标记变量k---标记本轮比较中最小值a[k]的位置--假设初始元素ai最小，将其下标i作为标记变量k的初始值。2）让后面的所有元素与k所标记位置的最小值a[k]做比较，如果后面的某个元素比a[k]还小，将该元素的下标赋给标记变量k。3）当内循环结束之后，如果标记变量k不再指向初始元素a[i],说明最小值不在初始位置ai---让初始元素a与标记变量k所标记位置的元素a[k]做一次交换，否则不需交换
• 选择排序有什么缺陷？ -多余的交换 • 如何修改？- P155 1）定义一个标记变量 k -标记本轮比较中最小值a[k]的位置 -假设初始元素a[i]最小，将其下标i作为标记变量 k 的初始值。 2）让后面的所有元素与 k 所标记位置的最小值a[k]做比较， 如果后面的某个元素比a[k]还小，将该元素的下标赋给标记 变量k。 3）当内循环结束之后，如果标记变量 k 不再指向初始元素 a[i]，说明最小值不在初始位置a[i]-让初始元素a[i]与标记变 量 k 所标记位置的元素a[k]做一次交换，否则不需交换
a|k|与a[i+l]---a[n-]比较：k改进的选择排序图示效果从小到大初始：【13i=03876271659749k+i=1一：9713［27657649381二趟：i=213[6597764938]27V三趟i=313764927[973865]四趟97133849[7627651五趟：131=52749659776]38六趟：i=6132765384976[97]
初始：[ 49 38 65 97 76 13 27 ] j i = 0 13 49 i = 1 一趟： 13 [ 38 27 65 97 76 49 27 ] 38 二趟： 13 27 [65 97 76 49 38 ] 三趟： 13 27 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 ] k k k k j j j j j j j j j j k 改 进 的 选 择 排 序 图 示 效 果 — 从 小 到 大 i = 3 i = 2 i = 6 i = 5 i = 4 a[k]与 a[i+1]-a[n-1]比较：