高中信息技术选修1：算法与程序设计 5.3 排序算法的程序实现【市一等奖】

冒泡排序算法程序实现经典算法之一、冒泡排序算法的基本思想用冒泡排序法把4位同学的身高（179,166,183,172）按低到高排序。（1）把待排序的n个元素看成是垂直堆放的一列数据。（2）从最下面的一个元素起，自下而上地比较相邻的两个元素中的数据，将较小（按升序排序）的数据换到上面一个元素中。重复这一过程，直到处理完最后两个元素中的数据，称为一遍加工。（3）对余下的n-1个元素重复上述过程，直至最后进行余下两个数据元素的比较和交换。初始(n=4)179166183172第1次比较、交换第2次比较、交换第3次比较、交换179166183172179166172183179166172183179166172183166179172183第1遍加工第1次比较、交换第2次比较、交换第1次比较、交换166179172183166179172183166172179183166172179183第2遍加工第3遍加工二、程序实现1、升序排序①相邻两两比较，逆序交换②怎么实现一遍加工？③总共进行几遍加工？初始179166183172第1次比较、交换第2次比较、交换第3次比较、交换179166172183179166172183166179172183第1遍加工第1次比较、交换第2次比较、交换第1次比较、交换166179172183166172179183166172179183第2遍加工第3遍加工4→24→34→4ina(j)数组aa(4),a(3),a(2)a(4),a(3)a(4)j冒泡排序加工遍数数据个数最多需要几遍范例2179,1663179,166,1834179,166,183,1725179,166,183,172,175n1234n-1二、程序实现1、升序排序Fori=1Ton-1Forj=nToi+1Step-1

Ifa(j)<a(j-1)Thent=a(j):a(j)=a(j-1):a(j-1)=tEndIfNextjNexti2、降序排序2①相邻两两比较，逆序交换②怎么实现一遍加工？③总共进行几遍加工？初始179166183172第1次比较、交换第2次比较、交换第3次比较、交换179166172183179166172183166179172183第1遍加工第1次比较、交换第2次比较、交换第1次比较、交换166179172183166172179183166172179183第2遍加工第3遍加工4→24→34→4inj数组a结构特征:双重循环里嵌套1个选择语句a(j)>a(j-1)【例1】实现某排序算法的部分VB程序段如下：Fori=1To4Forj=8Toi+1Step-1Ifd(j)<

d(j-1)Thent=d(j):

d(j)=d(j-1):d(j-1)=t

EndIfNextjs=s+Str(d(i))NextiText1.Text=s若数组元素d(1)到d(8)的数据依次为“12,7,18,13,9,17,6,23”，运行该程序段后，文本框Text1中显示的内容是

A.67912B.23181713

C.1271813D.917623Ifd(j)>

d(j-1)Thens=Str(d(i))+s假设有某数组：67,86,58,93,47第一遍加工：47,67,86,58,93第二遍加工：47,58,67,86,933、优化冒泡排序算法优化思路：某一遍加工过程中没有数据交换，说明数据已有序，无需进一步加工。Fori=1Ton-1

flag=FalseForj=ntoi+1Step-1Ifa(j)<a(j-1)Thent=a(j):a(j)=a(j-1):a(j-1)=t

__________EndIfNextjIf__________ThenExitForNextiflag=Trueflag=False逻辑变量：flag【知识拓展】有如下程序段：Fori=1To5Forj=1To6-iIfa(j)<a(j+1)Thent=a(j):a(j)=a(j+1):a(j+1)=tEndIfNextjNexti数组元素a(1)到a(6)的值依次为“71,54,58,29,31,78”，经过该程序段“加工”后，数组元素a(1)到a(6)的值依次为A.29,31,54,58,71,78 B.71,58,54,78,31,29C.54,29,31,58,71,78 D.78,71,58,54,31,29下沉式冒泡Fori=1Ton-1Forj=1Ton-i

Ifa(j)<a(j+1)Thent=a(j):a(j)=a(j+1):a(j+1)=tEndIfNextjNexti小↓Fori=1Ton-1Forj=nToi+1Step-1

Ifa(j)<a(j-1)Thent=a(j):a(j)=a(j-1):a(j-1)=tEndIfNextjNexti小结：升序降序优化（引入逻辑变量）下沉式冒泡Fori=1Ton-1Forj=nToi+1Step-1

Ifa(j)>a(j-1)

Thent=a(j):a(j)=a(j-1):a(j-1)=tEndIfNextjNexti小↑大↑小↓/大↓【思考】有如下程序段：Fori=1To2Forj=5Toi+1Step-1Ifa(j)>a(i)Thent=a(j):a(j)=a(i):a(i)=tEndIfN