第66课 经典之冒泡排序
经典之冒泡排序（数组、冒泡排序）
回味经典，我们一起来探索冒泡排序。说到冒泡你一定见过，喝汽水的时候，汽水中常常会有许多小小的气泡，缓缓地从瓶底浮到水面。“冒泡排序”也因此得名，在排序过程中，较大（或较小）的元素会像气泡一样逐渐浮到数组的一端。
我们的任务是运用冒泡排序的方法将数组int arr[15]={23,45,12,24,67,16,8,98,54,43,46,45,109,68,86}按照从小到大的顺序排列。
核心思想
每种排序方法都有它自己的核心思想，只要掌握了核心思想，按照规则实现程序就可以了。
冒泡排序的核心思想：
依次将两两相邻的数字进行比较，将大数或小数放到一端。
冒泡排序的基本操作：
（1）按顺序比较两两相邻的元素。
（2）根据大小需求交换元素位置。
冒泡排序法的推演
来吧，试试对这样一组数字9、5、8、6、3进行冒泡排序，使得数字从小到大排列。
小数在前大数在后，将大数往后移动。
1．第一轮开始
（1）第一波比较相邻数字9和5。
（2）第二波比较相邻数字9和8。
（3）第三波比较相邻数字9和6。
（4）第四波比较相邻数字9和3。
（5）这5个数字，经过4波比较，将最大数字9找出来并且放到了最后。
2．第二轮开始，从头来，这是要找第二大的数字了
（1）第一波比较相邻数字5和8。
（2）第二波比较相邻数字8和6。
（3）第三波比较相邻数字8和3。
（4）这一轮共4个数字，经过3波比较，找出了第二大数字8放到了后面。
3．第三轮开始，从头来，找出第三大数字
（1）第一波比较相邻数字5和6。
（2）第二波比较相邻数字6和3。
（3）这一轮有3个数字，经过了2波比较，找出了6。
4．第四轮开始
2个数字，一轮比较
最终排序成功→3、5、6、8、9。
敲黑板
关键来啦，到底需要几轮比较，每一轮到底需要比较几波？
一起来总结和思考：
（1）5个数字，第一轮比较找出了9并且放到了最右端。按照冒泡排序的核心思想，每轮比较我们都找出了剩余数字中最大的数字并放到了最右边。
（3）每一轮又进行了多少波的比较呢？5个数字需要4波比较。每一轮比较的波数比参与比较的数字的数量少1。
程序逻辑
来吧，根据总结和思考以及冒泡排序的基本操作，我们编写代码。
假设有n个数字进行排序，组合成数组arr[n]。
（2）每轮需要多少波比较呢？
比较波数比参与比较的数字的数量少1，于是需要知道参与比较数字的数量。我们知道每一轮比较可以确定一个数字，那么i轮比较也就确定了i个数字，意味着剩余数量为n-i个。
然后波数再比剩余数量还少1，所以需要n-i-1波。这是内层循环。
（3）根据数字大小进行位置交换，这就回到之前学习过的互换。
尝试编写冒泡排序的程序吧！对比排序前和排序后数字顺序的变化。
运行程序：
排序前：23 45 12 24 67 16 8 98 54 43 46 45 109 68 86
排序后：8 12 16 23 24 43 45 45 46 54 67 68 86 98 109
敲黑板
冒泡排序3大要点：
（1）确定外循环次数，也就是需要几轮比较→参与排序的数字的数量- 1。
（3）根据排序的大小要求，决定if条件和交换顺序。
注意
程序中使用了arr[j+1]，很有可能会导致数组越界。
巩固练习
（1）根据课程中讲述的冒泡排序程序，数组{2,4,8,3,6,1}外循环完成一轮后，该数组会变成什么样子？（）
A．2,4,8,3,6,1
B．2,4,3,6,1,8
C．1,2,3,4,6,8
D．4,8,3,6,2,1
（2）完善以下程序，使得数字9,4,5,8,2,4,10,5,6,9从小到大排序。
//冒泡排序
for(int i=0;i<_________;i++){
for(int j=0;j<__________;j++){
if(arr[j]>arr[j+1]){
temp=arr[j+1]; arr[j+1]=arr[j]; arr[j]=temp;}
（3）编写一个C++程序，输入10个考试成绩得分（0~100），将成绩由大到小排序输出。
输入：
输入10个成绩得分，成绩之间用空格隔开。
输出：
按照由大到小的顺序输出成绩。
样例输入：
样例输出：