程序设计基础（上) 张立红 13405330459(88028) QQ:2653453357 9#501
程序设计基础（上） 张立红 13405330459（88028） QQ：2653453357 9#501
第8章 数组
第 8 章 数 组
本章知识点 8.1一维数组的定义、引用与初始化 “数组名+一维下标”-表示数据 8.2一维数组的应用 8.3二维数组 “数组名+二维下标”表示数据 8.4数组与函数
本章知识点 8.1 一维数组的定义、引用与初始化 “数组名+一维下标”-表示数据 8.2 一维数组的应用 8.3 二维数组 “数组名+二维下标”-表示数据 8.4 数组与函数
8.2一维数组的应用 8.2.3排序问题一P152 【例87】选择法排序：用选择法将10个整数从小到大排序输出。 排序算法很多-一最基础的是选择法排序。 三个数排序的算法： ① intx,y,z,t;∥要求3个数从小到大 ② scanf("%d %d %d",&x,&y,&z); ③ if(X>y）) ④ {t=X;X=y;y=t切 从3个数找最小值 ⑤ if (x>Z) 存入X ⑥ {t=z;z=x;x=t;) ⑦ if (y>z) 从2个数找最小 ⑧ {t=y;y=z;z=ti) 值存入y ⑨ printf("%d,%d,%dIn",x,y,z); 恩 4/115
【例8.7】选择法排序：用选择法将10个整数从小到大排序输出。 排序算法很多-最基础的是选择法排序。 4/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个数中的小数与第2个数交 换一第二趟选择排序结果：3个数中次小数存入第2个元素。 (3)第3个数就是最大值，放在第3个元素位置上。 结论：3个数的排序一一是2次找最小值的过程
3个数的排序过程： (1) 通过 2 次比较，最小数与第 1 个数交换—第一趟选 择排序的结果：3个数中最小数存入第 1 个元素。 (2) 通过1次比较，将剩余的2个数中的小数与第 2个数交 换—第二趟选择排序结果： 3个数中次小数存入第2个元素。 (3) 第3个数就是最大值，放在第3个元素位置上。 结论：3个数的排序-是2次找最小值的过程
【例8.7】 选择排序法 ■编程：对个数排序（按由小到大顺序）。 ■选择法思路：每次选择未排好序的数中最小的放在前面， 个数的排序就是n-1次找最小值的过程。 选择排序过程： n个数的排序就是n-1次找最小值的过程，即： (1)首先通过n-1次比较，从n个数中找出最小数，将 它与第1个数交换一第一趟选择排序一结果：最小数被存入 第1个元素。 (2)再通过n-2次比较，从剩余的n-1个数中找出次小 数，将它与第2个数交换一第二趟选择排序一结果：次小数 存入第2个元素。 (3)重复上述过程，共经过-1趟排序后，排序结束。 恩 6/115
【例8.7】选择排序法 ◼编程：对n个数排序(按由小到大顺序)。 ◼选择法思路：每次选择未排好序的数中最小的放在前面，n 个数的排序就是n-1次找最小值的过程。 6/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[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]是次次小值
用选择法对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[为最小值位置，假设内循环变量为，让a[与 其后的所有元素a逐个比较，j的范围是i+1~~n-1
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 mainO ③ {inta[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; 4 田老。加上数捏的百业的字早2
例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; ⑭ } 思考：加上数据的原来的序号？
选择法排序（从小到大）第一轮查找最小值的过程-举例 =0 10 9 8 7 654321-初始数据 9 10 8 7 6 5 4 3 2 1 8 10 9 7 6 4 3 2 1 7 10 9 8 6 5 4 3 2 1 6 10 9 8 5 4 3 2 1 110 98765432
• 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 选择法排序(从小到大)第一轮查找最小值的过程-举例