大学计算机基础-基于计算思维（Windows 10+Office 2016）（第2版）课件 10.3.1冒泡排序

大学计算机基础——基于计算思维（Windows10+Office2016）第10章算法思维与运用10.3.1冒泡排序10.3排序算法基本排序算法冒泡排序冒泡排序选择排序直接插入排序问题3冒泡排序大学入学军训时要求n人一列从低到高排列，现在已知n人的身高（无序），请按要求完成任务。1.问题分析冒泡排序的过程类似水中冒气泡的过程，将待排序的n个身高数据看作是垂直排列的重量不同的气泡。根据重气泡不能在轻气泡上面的原则，从上往下扫描，比较相邻数据，如果它们是逆序的话就交换它们的位置，重复多次后，最大数据就“沉到”了最后位置，称为第1趟扫描冒泡。问题3冒泡排序1.问题分析第2遍操作对剩余的数据进行扫描冒泡，将第二大的数据沉下去。这样一直做，经过n-1趟以后，所有数据就排好序了。问题3冒泡排序2．算法实现（1）设计输入子程序input。先设计一个子程序来完成数据的输入功能（名称为input），要求生成n个150~190的随机整数存储到数组a[]中。数组名a作为“输出”参数，如图所示为input的各接口参数问题3冒泡排序2．算法实现（1）设计输入子程序input。在子程序中要生成n个150~190的随机整数存储到a[]数组中，可设计一个循环结构（设循环变量为i，从1递增到n）由随机函数构建公式产生1个150~190的随机整数存放到数组a[i]元素中问题3冒泡排序2．算法实现（2）设计输出子程序output。设计一个子程序来完成数据的输出功能（名称为output），要求将上述数组a[]中的所有数据输出，数据间用空格分隔。在创建子程序output时，要已知数组的大小n和数组名a，而且在output中都不会改变其值，所以n和a都作为“输入参数”问题3冒泡排序2．算法实现（2）设计输出子程序output。在子程序output中要输出a数组中所有元素，可设计一个循环结构（设循环变量为i，从1递增到n），在循环体内按格式输出数组元素a[i]。问题3冒泡排序2．算法实现（3）设计main子图main子图的主要功能是：①输入要排队列人数n。②调用input子程序生成数组a，模拟待排人的身高数据。③调用output子程序显示数组a（无序）。问题3冒泡排序2．算法实现（3）设计main子图右图所示为该程序调试运行中的一组数据（10个）问题3冒泡排序（4）设计冒泡子程序bubble表中列出了a数组有5个元素的冒泡排序过程。问题3冒泡排序（4）设计冒泡子程序bubble从表中，我们要找出a数组有n个元素时冒泡排序的一般规律。问题3冒泡排序（4）设计冒泡子程序bubble完成bubble子程序，实现步骤如下：①创建bubble子程序，其各参数如图所示。问题3冒泡排序（4）设计冒泡子程序bubble②在bubble子程序中首先构建扫描冒泡趟数的循环i（1～n-1）。③然后在每趟冒泡i的循环体内再构建一个比较次数的循环j（从上往下扫描1～n-i）。④在内循环j的循环体内，从上到下比较相邻元素，若a[j]>a[j+1]则交换其中的内容。问题3冒泡排序（5）完善main子图①调用bubble子程序，对数组a进行冒泡排序。②调用output子程序