内蒙古科技大学：《C语言程序设计》课程授课教案（讲义）第六章 数组 6.3

内蒙古科技大学 教 案 课程名称：C语言程序设计 编写时间：2014年2月16日 授课章节 第六章数组$6.3 目的要求 排序算法介绍 选择排序法冒泡排序法 重点难点 选择排序法冒泡排序法 教学内容 一、选择法： 选择法排序首先取数组中第一个元素，依次与后面的元素进行比较，若不符合相应的序列， 记录较小（或较大）元素的下标，且用较小（或较大）的元素与后面的元素继续比较，直到内层 循环结束。当内层循环结束后，记录的下标即为比较范围内最小（或最大）的元素的下标，同时 将元素交到第一个元素的位。这样每进行 一遍比较只进行一次数据交换，若有个元素则 比较n一1次后，最小数值（或最大数值）就被交换到第 个 元素的 然后再取第二个元素 依次与后面的一2个元素进行比较，方法同上。每一遍的比较次数比前一海少一次。直到最后 遍比较次数为1，一共要进行n一1遍的比较。 例题：选择法对10个任意整数按由小到大顺序排序 程序： #include void sort(int x lin) (intm.h.k.t; for(m-0;mx[h) k=hi if(k!=m) (t-x[ml:xlml-x[k]:x[k]-t) } 第1次 第1页

内 蒙 古 科 技 大 学 教 案 课程名称： C 语言程序设计 编写时间：2014 年 2 月 16 日 授课章节 第六章 数组 $6.3 目的要求 排序算法介绍 选择排序法 冒泡排序法 重点难点 选择排序法 冒泡排序法 教学内容 一、选择法： 选择法排序首先取数组中第一个元素，依次与后面的元素进行比较，若不符合相应的序列， 记录较小（或较大）元素的下标，且用较小（或较大）的元素与后面的元素继续比较，直到内层 循环结束。当内层循环结束后，记录的下标即为比较范围内最小（或最大）的元素的下标，同时 将该元素交换到第一个元素的位置。这样每进行一遍比较只进行一次数据交换，若有 n 个元素则 比较 n－1 次后，最小数值（或最大数值）就被交换到第一个元素的位置。然后再取第二个元素 依次与后面的 n－2 个元素进行比较，方法同上。每一遍的比较次数比前一遍少一次。直到最后 一遍比较次数为 1，一共要进行 n－1 遍的比较。 例题：选择法对 10 个任意整数按由小到大顺序排序 程序： #include void sort(int x[ ],int n) {int m,h,k,t; for(m=0;mx[h]) k=h; if(k!=m) {t=x[m];x[m]=x[k];x[k]=t;} } } 第 1 次 第 1 页

内蒙古科技大学 教案续页) ka10: printf("请输入10个任意无序的整数："片 for(k=0:k<10k+) scanf("%d",&alkD); sort(a,10) /调用排序函数 ri输出10个排好序的整：" fork-0:k<10:k+) printf("%d ",a[kD); printf("In"); 程序运行结果： 国"C:\Users\Administrator\Desktop\C语言制作课件a回x 青输人10个任意无序的整数：23548691710 输出10个排好序的整数：1234567891g ress any key to continue 二、冒泡法 冒泡法排序的思路： 冒泡法排序也叫起泡法排序，是相邻两元素进行比较的一种排序方法。每 遍都从第一个元素开始，两两比较，若不符合相应序列，则两数值交换位置。 当比较完一遍后，最大（或最小）的数己沉底，被放置在最后的位置，而相应 较小（或较大）的数则上浮。由于第一遍已找出最大（或最小）的数，第二遍 不需要与其比较，所以第二遍比第一遍的比较次数 一次。同样需要n一1遍比 较才能完成排序。 第1次第2页

内 蒙 古 科 技 大 学 教 案（续页） void main() { int k,a[10]; printf("请输入 10 个任意无序的整数："); for(k=0;k<10;k++) scanf("%d",&a[k]); sort(a,10); //调用排序函数 printf("\n 输出 10 个排好序的整数："); for(k=0;k<10;k++) printf("%d ",a[k]); printf("\n"); } 程序运行结果： 二、冒泡法： 冒泡法排序的思路： 冒泡法排序也叫起泡法排序，是相邻两元素进行比较的一种排序方法。每 遍都从第一个元素开始，两两比较，若不符合相应序列，则两数值交换位置。 当比较完一遍后，最大（或最小）的数已沉底，被放置在最后的位置，而相应 较小（或较大）的数则上浮。由于第一遍已找出最大（或最小）的数，第二遍 不需要与其比较，所以第二遍比第一遍的比较次数少一次。同样需要 n－1 遍比 较才能完成排序。 第 1 次 第 2 页

内蒙古科技大学 教案（续页） 例如：对6个整数按由大到小的顺序排序（相邻两个数比较， 将小的调到后头。) 原来数据 5 82479 举例说明 第一轮比较 5 8 247 结果 8 5479 2 第二轮比较 8 5 479 2 结果 8 5 794 第三轮比较 8 5 79 4 2 结果 8 7 9 5 4 2 第四轮比较 8 7 95 4 2 结果 8 9 7 5 4 2 第五轮比较 8 9 5 4 2 结果 9 8 7542 最终结果 9 87542 第1次第3页

内 蒙 古 科 技 大 学 教 案（续页） 例如：对 6 个整数按由大到小的顺序排序(相邻两个数比较， 将小的调到后头。) 原来数据 5 8 2 4 7 9 第一轮比较 5 8 2 4 7 9 结果 8 5 4 7 9 2 第二轮比较 8 5 4 7 9 2 结果 8 5 7 9 4 2 第三轮比较 8 5 7 9 4 2 结果 8 7 9 5 4 2 第四轮比较 8 7 9 5 4 2 结果 8 9 7 5 4 2 第五轮比较 8 9 7 5 4 2 结果 9 8 7 5 4 2 最终结果 9 8 7 5 4 2 举例说明 第 1 次 第 3 页

内蒙古 科技大学 教案 (续页) 冒泡法程序： #include void main() 举例说明 int h,k,t,a6={5,8,2,4,7,9}; for(h=0;h<5;h++) for(k=0;k<5-h;k++) if(a[k]<a[k+1]) {t=a[k];a[k]=a[k+1];a[k+1]=t) for(k=0;k<=5;k++) printf("a[%d]=%d "k,a[k]); printf(\n”); 程序运行结果： "C:\Users\Administrator\Desktop\Debug\tk1.exe" ✉回x a[0]-9a[1]-8a[2]-7a[3]-5a[4]=4a[5]-2 Press any key to continue 课堂教学小结： 排序是计算机进行数据处理的基本运算之一，排序后的数据便于进行查找，选择合适的排序方法可以提高 编程效率。冒泡法和选择法是我们重点掌握的内容。 第1次第4页

内 蒙 古 科 技 大 学 教 案（续页） 冒泡法程序： #include void main( ) {int h ,k, t,a[6]={5, 8, 2, 4, 7, 9 }; for(h=0; h<5; h++) for(k=0; k<5-h; k++) if(a[k]<a[k+1]) {t=a[k]; a[k]=a[k+1]; a[k +1]=t;} for (k=0; k<=5; k++) printf( "a[%d]=%d ", k, a[k] ); printf(“\n”); } 程序运行结果： 举例说明 课堂教学小结： 排序是计算机进行数据处理的基本运算之一，排序后的数据便于进行查找，选择合适的排序方法可以提高 编程效率。冒泡法和选择法是我们重点掌握的内容。 第 1 次 第 4 页