程序设计基础 第8章数组 1/14
程序设计基础 1/14 第 8 章 数 组
本章知识点 8.0数组的概念 81一维数组用“数组名+一维下标”来表示数据 8.2一维数组的应用 8.3二维数组用“数组名+二维下标”来表示数据 8.4数组与函数 数组元素与数组名做函数参数 小结 恩 2/14
8.0 数组的概念 8.1 一维数组 用“数组名+一维下标”来表示数据 8.2 一维数组的应用 8.3 二维数组 用“数组名+二维下标”来表示数据 8.4 数组与函数 数组元素与数组名做函数参数 小结 本章知识点 2/14
【例8.7】选择排序法 ■编写程序，对个数排序按由小到大顺序)。 ■选择法思路：每次选择未排好序的数中最小的放在前面， 个数的排序就是n-1次找最小值的过程。 ■例如：n=58025368350 if(x>y） temp=x;x=y;y=temp;} if(x>z)找三个数的最小值 temp=z;Z=x;x temp;} if(y>z)/找两个数的最小值 temp=y;y z;z=temp;) 三个数排序是找两 个最小值的过程 恩 3/14
【例8.7】选择排序法 ◼编写程序，对n个数排序(按由小到大顺序)。 ◼选择法思路：每次选择未排好序的数中最小的放在前面，n 个数的排序就是n-1次找最小值的过程。 ◼例如：n = 5 80 25 36 83 50 3/14 if (x>y) { temp = x; x = y; y = temp;} if (x>z) //找三个数的最小值 { temp = z; z = x; x = temp;} if (y>z) //找两个数的最小值 { temp = y; y = z; z = temp;} 三个数排序是找两 个最小值的过程
【例8.7】选择排序法 ■编写程序，对个数排序（按由小到大顺序）。 ■选择法思路：每次选择未排好序的数中最小的放在前面，门 个数的排序就是n-1次找最小值的过程。 ■例如：n=58025368350 排序过程： (1)第一趟选择排序，通过n-1次比较交换，从n个数中找出最 小的数，放在第一个元素位置上；2580368350 (2)第二趟选择排序，通过n-2次比较，从剩余的n-1个数中找 出次小的数，放在第二个元素的位置上；2536808350 (3)重复上述过程，共经过-1趟排序后，排序结束。 恩 4/14
排序过程： (1)第一趟选择排序，通过n-1次比较交换，从n个数中找出最 小的数，放在第一个元素位置上；25 80 36 83 50 (2)第二趟选择排序，通过n-2次比较，从剩余的n-1个数中找 出次小的数，放在第二个元素的位置上；25 36 80 83 50 (3) 重复上述过程，共经过n-1趟排序后，排序结束。 【例8.7】选择排序法 ◼编写程序，对n个数排序(按由小到大顺序)。 ◼选择法思路：每次选择未排好序的数中最小的放在前面，n 个数的排序就是n-1次找最小值的过程。 ◼例如：n = 5 80 25 36 83 50 4/14
【例8.7】 选择排序法 n=5初始8025368350 a[o]a[1]a[2]a[3]a[4] a[o]a[1]a[2]a[3]a[4] a0]af1a2☒a3]a4 a[o]a[1]a[2]a[3]a[4] 289 3683 50 25 3680 8350 25 36 8083 50 25365089 25 80 83 50 25 36 80 83 50 2536 5083 89 第四趟1次比较 5 80 36 83 50 25 36 80 83 50 第三趟2次比较 5 80 36 83 50 第二趟3次比较 for (i=0;ia[]) if(a叮>a) t=a[; t=ai]; a叮=al a0=a] a]=t; a]=t; 3 5/14
【例8.7】选择排序法 n=5 初始 80 25 36 83 50 5/14 a[0] a[1] a[2] a[3] a[4] 25 80 36 83 50 25 80 36 83 50 25 80 36 83 50 25 80 36 83 50 a[0] a[1] a[2] a[3] a[4] 25 36 80 83 50 25 36 80 83 50 25 36 80 83 50 a[0] a[1] a[2] a[3] a[4] 25 36 80 83 50 25 36 50 83 80 a[0] a[1] a[2] a[3] a[4] 25 36 50 80 83 第一趟 4次比较 第二趟 3次比较 第三趟 2次比较 第四趟 1次比较 //第i趟选择排序，求最小值过程 for (j=i+1; ja[j]) { t=a[i]; a[i]=a[j]; a[j]=t; } } for (i=0; ia[j]) { t=a[i]; a[i]=a[j]; a[j]=t; } }
可见：n个数的选择排序是个两重循环 ·外循环控制求最小值的次数，n-1次求最小值用-1次外循 环实现，假设外循环变量为i,则i的循环范围为0~n-2; ·内循环完成求一个最小值的过程，假定当前元素为最小 值，假设内循环变量为j,让a[心与其后的所有元素aj]逐个 比较，j的范围即为i+1~n-1。 for (i=0;ia[j]) t=a[i]; a[i]=al]; al]=t; 3 恩 6/14
可见：n个数的选择排序是个两重循环 • 外循环控制求最小值的次数，n-1次求最小值用n-1次外循 环实现，假设外循环变量为i,则i的循环范围为0~n-2； • 内循环完成求一个最小值的过程，假定当前元素a[i]为最小 值，假设内循环变量为j，让a[i]与其后的所有元素a[j]逐个 比较，j的范围即为i+1~n-1。 6/14 for (i=0; ia[j]) { t=a[i]; a[i]=a[j]; a[j]=t; } }
选择排序实现 川选择排序 for (i=0;i for (j=i+1;ja[j]) inti,jt,a[100],n=100; t=a[i]; 输入数据 a[i]=a]; for (i=0;i<=n-1;i++) a[]=t; { scanf("%d",&a[i]); /输出数据 for(i=0;i<=n-1;i++) { printf("%d ",ali]); } return 0; 恩 7/14
选择排序实现 #include int main() { int i,j,t,a[100],n=100; //输入数据 for (i=0;ia[j]) { t=a[i]; a[i]=a[j]; a[j]=t; } } } //输出数据 for (i=0;i<=n -1;i++) { printf("%d ",a[i]); } return 0; } 7/14
i 选择排序缺陷：多余的交换 改进的选择排序，减少交换次数 ·10987654321 for(i=0;i<n-1;i++) ·9 10↑8765432 1 k=i;k记录最小值所在下标，初值为 for (j=i+1;j<n;j++) ·810°9 6 5432 ·7109 8 6 5 432 1 if (a[k]aljl) { ·610 9 87j 5 3 .4 21 k=j;/更新k为最小值所在下标 } ·1109876543 2 if(!=k)最小值不在初始位置交换 x=ali];ali]=a[k];a[k]=x; 如何修改？对于第趟选择排序 1、定义一个标记变量k,来标记本轮比较中最小值的位置，假设初始元 素a[叮最小，将其下标作为标记变量的初始值k=i。 2、然后让后面的所有元素a]与标记变量所标记位置的最小值a[k做比较， 如果比最小值还小，只需将新的最小值下标j赋予标记变量k即可。 3、当外循环结束之后，标记变量如不再指向初始元素，说明最小值不在 初始位置，这时让初始元素与标记变量所标记位置的元素做一次交换即 可，否则不需交换。 8/14
• 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 j j j j 选择排序缺陷：多余的交换 8/14 如何修改？对于第i趟选择排序 1、定义一个标记变量k，来标记本轮比较中最小值的位置，假设初始元 素a[i]最小，将其下标作为标记变量的初始值 k = i。 2、然后让后面的所有元素a[j]与标记变量所标记位置的最小值a[k]做比较， 如果比最小值还小，只需将新的最小值下标 j 赋予标记变量 k 即可。 3、当外循环结束之后，标记变量如不再指向初始元素，说明最小值不在 初始位置，这时让初始元素与标记变量所标记位置的元素做一次交换即 可，否则不需交换。 //改进的选择排序，减少交换次数 for (i = 0; i a[j]) { k = j; //更新k为最小值所在下标 } } if (i != k) //最小值不在初始位置交换 { x = a[i]; a[i] = a[k]; a[k] = x; } }
n=7 i=0 初始：[13 38 65 97 76 k↓9 27] 个： k i=1一趟：13 [27 65 97 76 49 381 个： 二趟：13 27 I65 97 76 49 381 三趟： 13 27 38 [97 76 49 65] 改进的选择排序图示效果 四趟： 13 27 38 49 [76 97 65] 五趟： 13 27 38 49 65 97 761 六趟：1327 3849 65 76 971 色 9/14
初始：[ 49 38 65 97 76 13 27 ] j n =7 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 改 进 的 选 择 排 序 图 示 效 果 9/14
输入n个数给a0到an-1 改进的选择排序，减少交换次数 #include for i=0 to n-2 #define N 105 int main() k=i int alN],i,j,k,x,n; for j=i+1 to n-1 scanf(%d”,&n; a[k]>a[jl for (i=0;ialjl)k=j; f(!=k) x=a[i];a[i]=a[k];a[k]=x;} for (i=1;i<11;i++) printf("%d "alil); return 0; 10/114
输入n 个数给a[0] 到 a[n-1] for i = 0 to n - 2 for j = i + 1 to n-1 a[k] > a[j] 真 假 k = j 输出a[0] 到 a[n-1] k = i a[i] a[k] 真 i != k 假 //改进的选择排序，减少交换次数 #include #define N 105 int main( ) { int a[N], i, j, k, x, n; scanf(“%d”, &n); for (i = 0; i a[j]) k = j; } if (i != k) { x = a[i]; a[i] = a[k]; a[k] = x; } } for (i = 1; i < 11; i++) printf ("%d ", a[i]); return 0; } 10/14