冒泡法排序
• 冒 泡 法 排 序 流 程 图
Y
A(j)<A(j+1) Y 交换A(j)和A(j+1)的值
j=j+1 j<n-i N i=i+1
N
i>n-1 Y 输出排序结果 结束
N
• 程序代码
控 制 共 需 几 轮 排 序
Dim A(4) As Integer Dim i, j, t, k As Integer For k = 0 To 4 A(k) = Val(InputBox(“请输入第” & k + 1 & “个学生成绩: ")) Next k For i = 1 To 4 输入语 For j = 0 To 4 - i 句 If A(j) < A(j + 1) Then t = A(j) A(j) = A(j + 1) 数值交 A(j + 1) = t 换 End If Next j Next i For k = 0 To 4 Print A(k) Next k 输出语 句
90
440 478
460
• 算法分析—从大到小排序:
对相邻两个数进行比较,将较大的调到前面,
两两比较一轮之后,最小的一个数被放置在 最后面;接着从头开始重复执行以上操作, 次小的数被放置在倒数第二位,依次类推, 数列由后往前逐渐成型。
• 冒泡法第一轮:
使最小的数放在最后一个位置上
第1次
第2次
冒泡法排序算法
任课教师 訾振辉
• 排序的概念
所谓排序,就是指将一个无序序列排列成一
个有序序列的过程。
• 生活中大家常见的排序有哪些?
队列排序
成绩排序
广播操
体育课
现场模拟体育课排队
• 冒泡法排序的概念
“冒泡法”排序也叫“起泡法”排序,是一种
比较简单、易懂的排交换排序方法,它通过 将相邻元素进行比较和交换,逐步将一个无 序序列排列为一个有序序列。
495
478 442
495
478 460
460 440
460 440
460 440
442 440
• 第三轮排序:
第1次 495 第2次 495 结果 495
• 第四轮排序:
第1次 495 结果 495
478
460 442 440
478
460 442 440
478
460 442 440
478
460 442 440
• 课堂小结
冒泡法排序是通过顺序扫描数组元素,将
相邻两个数进行比较,将小数调到前面, 大数调到后面。 如果有 n 个数,则要进行 n-1轮排序。 在第 i 轮排序中,要进行 n-i 次两两比较。 可以从前往后排序,也可以从后往前排序。
• 实践:
For i = 0 To '变量i用来控制排序共需几轮 For j = 4 To Step -1 '变量j用来控制两两比较的 次数 If A(j) < A(j - 1) Then 交换A(j) 和 A(j - 1)的值 End If Next j Next i
例1:用冒泡法对下表中五位学生的成绩进
行排序(从高到底)。
考试成绩表
学号 姓名 语文 数学 英语 信息技术 体育 总分
001
002
钱梅宝
张平光
88
100
98
98
82
100
85
97
89
100
442
495
003 004
005
许动明 唐琳
郭建锋
89 98
97
87 96
94
87 89
89
85 99
90
92 96
返回
• 补充代码
Dim A(4) As Integer Dim i, j, t, k As Integer For k = 0 To 4 A(k) = Val(InputBox("请输入第" & k + 1 & "个数:")) Next k For i = 0 To ? '变量i用来控制排序共需几轮 For j = 4 To ? Step -1 '变量j用来控制两两比较的次数 If A(j) < A(j - 1) Then '下面引入变量t进行数值交换 t = A(j) A(j) = ? A(j - 1) = t End If Next j Next i For k = 0 To 4 Print A(k)
返回
• 队列排序要求
只能从队伍的一端排序
只能对相邻的两个学生进行比较
如果第一轮比较没有达到目标,从头进行第 二轮比较,以此类推直至完成排序。 最终要把队伍排成一个有序序列(从高到低 或者从低到高)
返回
控 制 两 两 比 较 的 次 数
• 课堂练习
例2:对5个元素“4,1,2,5,3”的序列进行升
序排序。见课本P58. 任务1:认真读题,并找到图3-14中冒泡法的 排序特点。 任务2:把课本第58页实践练习中的伪代码填 写完整。 任务3:把学生练习文件夹中冒泡排序的代码 补充完整,并运行程序,验证结果。
478
460 442 440
• 冒泡法的思想是:(从大到小)
将大数调到前面,小数调到后面。
顺序扫描数组元素,将相邻两个数进行比较,
• 冒泡法排序的特点是:
如果有 n 个数,则要进行 n-1 轮排序。 在第 i 轮排序中,要进行 n-i 次两两比较。
开始 向A(n-1)中 读入Hale Waihona Puke 个元素 i=1,j=0第3次
第4次
结果 495 442 478 460
442
495 440
495
442 440
495
442 440
495
442 478
478 460
478 460
478 460
440 460
440
• 冒泡法第二轮:
使次小的数放在倒数第二个位置
第1次
第2次
第3次
结果
495
442 478
495
442 478