冒泡排序法

计算机系网络教研室第4章构造型数据类型1、一维数组应用举例——冒泡法排序经典算法介绍：排序问题是程序设计中的典型问题之一，它有很广泛的应用，比如给你一组学生成绩，要你输出前20名的成绩。这时你就要用到排序。再比如要问你中国的GDP排世界第几，你要先把各国GDP排个序，才知道中国在第几。所谓排序就是将数组中的各元素的值按从小到大的顺序或按从大到小的顺序重新排列。排序过程一般都要进行元素值的比较和元素值的交换。第4章构造型数据类型分析:假设有N个数据放在数组a中,现要把这N个数从小到大排序.冒泡排序法的基本思想是:第一:在a[0]到a[N-1]的范围内,依次比较两个相邻元素的值,若a[J]a[J+1],则交换a[J]与a[J+1],J的值取0,1,2,……,N-2;经过这样一趟冒泡,就把这N个数中最大的数放到a[N-1]中.看图示例1:用冒泡排序法对8个整数{6,8,5,4,6,9,3,2}进行从小到大排序.第4章构造型数据类型第二:再对a[0]到a[N-2]的范围内再进行一趟冒泡,又将该范围内的最大值换到了a[N-2]中.看图示二Swap变量作用看图示三第四:如果在某趟冒泡过程中没有交换相邻的值,则说明排序已完成,可以提前结束处理.第三:依次进行下去,最多只要进行N-1趟冒泡,就可完成排序.看流程第4章构造型数据类型第一讲之冒泡法排序现假设有8个随机数已经在数组中，开始排序初始状态：数组aa[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]68546932第一趟排序：两两相邻比较：总结回到思路一8584938692第一趟最后结果：9第二趟冒泡排序开始：此时的待排序元素a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]第四章构造型数据类型第一讲之冒泡法排序654683295466328945632689同样对待排序元素两两比较后结果为：这是第三趟冒泡的待排序元素接着第三趟冒泡排序结果为：回到思路二第四章构造型数据类型第一讲之冒泡法排序同样第四趟结果为：23456689453266893245668943256689第六趟结果为：第七趟结果（最终）为：第五趟结果为：回到思路二看流程冒泡法排序流程图程序整体流程：开始结束输入数据输出数据冒泡排序细化输入数据流程：i=0i8scanf(“%d”,&a[i]);i++NY细化输出数据流程：i=0i8printf(“%d”,a[i]);i++NY执行第i趟冒泡排序冒泡法排序流程图i++i8-1i=0YN写程序j=0j8-i-1NYj++比较相邻两元素的值并交换a[j]a[j+1]交换a[j]与a[j+1]的值YN冒泡法排序流程图a[j]a[j+1]swap=1;交换a[j]与a[j+1]的值YNi++;i8-1i=0YNj8-i-1NYj++swap=0j=0加入Swap变量的流程图程序!(swap)breakNY冒泡法程序main(){inti,j,a[8],temp,swap;clrscr();for(i=0;i8;i++)scanf(%d,&a[i]);for(i=0;i8;i++)printf(%d,,a[i]);printf(\n);}{}注：对n个元素冒泡排序第i趟排序的待排序元素是a[0]到a[n-i-1]。这里的i表示数组的下标.swap=1;if(!swap)break;swap=0;流程图if(a[j]a[j+1]){temp=a[j];a[j]=a[j+1];a[j+1]=temp;}for(j=0;j8-i-1;j++)回到第四点上一页比较for(i=0;i8-1;i++)第四章构造型数据类型第一讲之冒泡法排序swap变量的作用如果在某趟冒泡过程中没有交换相邻的值,则说明排序已完成,可以提前结束处理.比如：为原始数列：8、15、27、96、32、65、78、79这个序列用冒泡法排序，一趟之后就得到升序结果，而之后的六趟都可以不要进行。所以，swap变量就是用来标识如果某趟排序之后已经得到最终结果，则多余的次数就无须进行。回到流程图冒泡法与选择法的比较用选择排序法对键盘输入的N个数从小到大进行排序.基本思想:假设有N个数据放在数组a中,现要把这N个数从小到大排序.首先:在a[0]到a[N-1]的范围内,选出最小值与a[0]交换;然后:在a[1]到a[N-1]范围内,选出最小值与a[1]交换;接着是a[2]到a[N-1]的范围，这样依次进行下去,进行N-1次选择后就可完成排序.即第i趟排序的待排序范围是a[i]~a[N-1]的元素，要从中选出值最小的元素并与a[i]交换位置。冒泡法与选择法的比较a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]数组a68546932KKiKKK26每趟选择排序是找到待排序序列中最小的元素，把它交换到待排序的最前的位置。所以，一趟只有一次交换。回到冒泡图示iKK384556698总结本次课主要内容：1.冒泡法基本思想，通过n-1趟排序把n个待排序数大的元素象石头一样往下沉（放在最后），小的元素象气泡一样往上浮。2.冒泡法的流程图3.冒泡法程序4.冒泡法中swap变量的作用5.简述了选择法排序，要求回去预习选择法排序。