冒泡排序PPT教学课件

稳定排序
冒泡排序是一种稳定的排序算法 ，相同元素的相对位置不会改变
。
冒泡排序的缺点
时间复杂度高
冒泡排序的时间复杂度为O(n^2)，在数据量大时 效率较低。
易受数据分布影响
如果待排序数据集已经部分有序，冒泡排序的性 能会受到影响。
交换操作频繁
冒泡排序需要多次遍历数据，进行大量的交换操 作。
其他排序算法的比较
01
选择排序
选择排序的时间复杂度也是O(n^2)，但它的空间复杂度为O(1)，且在
数据量较大时比冒泡排序略快。
02
插入排序
插入排序的时间复杂度同样是O(n^2)，但它的空间复杂度也是O(1)。
在数据量较小或部分有序的情况下，插入排序的性能优于冒泡排序。
03
快速排序
快速排序是一种分治算法，其平均时间复杂度为O(nlogn)，远优于冒
冒泡排序 PPT 课件
目录
• 冒泡排序简介 • 冒泡排序算法实现 • 冒泡排序的时间复杂度分析 • 冒泡排序的优缺点比较 • 冒泡排序的应用实例 • 总结与展望
01 冒泡排序简介
什么是冒泡排序
冒泡排序是一种简单的排序算法，通过重复地遍历待排序的 序列，比较相邻的两个元素，若它们的顺序错误则交换它们 ，直到没有需要交换的元素为止。
终实现数组的有序排列。由于其算法简单且稳定，冒泡排序在某些场景下是高效的。
冒泡排序在字符串匹配中的应用
总结词
基础、适用
VS
详细描述
在字符串匹配中，冒泡排序可以作为算法 的一部分，用于对字符数组进行排序。通 过将待匹配的字符串与模式串中的字符进 行比较和交换，冒泡排序可以帮助算法更 快地找到匹配项或排除不可能的匹配。尽 管冒泡排序在字符串匹配中的效率不是最 高，但由于其简单易实现，仍被广泛使用 。

{t=s[j];s[j]=s[j+1];s[j+1]=t;}
printf(“%d %d %d %d %d \n”,s[0],
s[1], s[2], s[3], s[4]); }
s[0] s[1] s[2] s[3] s[4]
23795
16
冒泡法演示(升序) 下一步
j=4时，4<4 为假，循环
结束，该轮
变量与变量的 值
程序段： #include<stdio.h>
的大小，将 较大数存入
s[1]
main()
n5 i0
{ int s[10]={2,9,3,7,5}, n=5, i,j,t;
for(i=0;i<n-1;i++) for(j=0;j<n-1-i;j++)
值为4
if(s[j]>s[j+1])
j0
变量与变量的 值
程序段： #include<stdio.h>
的大小，将 较大数存入
s[2]
main()
n5 i0
{ int s[10]={2,9,3,7,5}, n=5, i,j,t;
for(i=0;i<n-1;i++) for(j=0;j<n-1-i;j++)
值为4
if(s[j]>s[j+1])
j1
{t=s[j];s[j]=s[j+1];s[j+1]=t;}
printf(“%d %d %d %d %d \n”,s[0],
s[1], s[2], s[3], s[4]); }
s[0] s[1] s[2] s[3] s[4]

2
第一趟冒泡结果
2
3
a[2] a[3]
3
4
4
1
for(i=0;i++;i<3) 实现一趟冒泡的代码为： if(a[i]<a[i+1])
{ temp=a[i]; a[i]=a[i+1]; a[i+1]=temp;
}
a[0]、a[1]、 a[2] 分别两两比较交换，小数沉 底到a[2]
a[0] a[1] a[2] a[3]
冒泡排序
n个数排序，需要进行n-1趟冒泡
a[0]、a[1]、 a[2]、 a[3]分别两两比较并交换， 使小数沉底到a[3]
a[0] a[1] a[2] a[3]
第一次比较
1
2
3
4
第二次比较
2
1
3
4
第三次比较
2
3
1
4
第一趟冒泡结果
2
3
4
1
第一趟冒泡，小数沉底到a[3]
a[0] a[1]
比较前：
1
if (a[max]<a[j]) max=j;
temp=a[0]; a[0]=a[max]; a[max]=temp;
第二趟：从3个元素中选出最大者，将其换入 a[1]中
过程为：令max表示最大元素的序号（初值max=1），a[1]到
a[3]逐一比较，找出最大元素的位置，a[1]与其互换，使最
大值位于a[1]。 a[0]
a[2] a[3]
3
4
2
1
4个数排序，需 要执行3趟冒泡。
每一趟冒泡，需 要数据进行两两 比较并交换。
选择排序
n个数排序，需要进行n-1趟选择

2.提高练习
• For i = 1 To n ' 设共有n名同学 • For j = n To i+1 step -1 • If a(j) > a(j-1) Then • c = a(j - 1) • a(j - 1) = a(j) • a(j) = c
•
2.提高练习
• t = b(j - 1) • b(j - 1) = b(j) • b(j) = t • End If • Next j • Next i • For i = 1 To n • List2.AddItem Str(a(i)) + " • Next i • End Sub
2.提高练习
a(i)
b(i)
2.提高练习
• 解决此问题的算法流程图如图所示，相应的 排序部分程序如下： • Dim a(1 To n) As Single • Dim b(1 To n) As String • Private Sub Command1_Click() • Dim i As Integer , j As Integer • Dim c As Single , t As String
交换d(j) 和d(j-1)的值
冒泡排序第二趟
d (1)
15
29 38 35 j-1 j
15
d (2)
d (3) d (4)
29
35 38
j-1 j
15 29
35
38
第2次冒泡排序时 j 从 4 开始到3
算法分析
第2次冒泡排序时 j 从 4 开始到3 For j=4 to 3 step -1
if d(j)<d(j-1) then
两个数进行数据交换， 就像两杯水进行交换， 需要再拿一个空杯

;) )
i++ 是 i <=6
否 结束
}
9
按照这种画法第二趟、第三趟、第四趟排序的流程图 怎样画？怎样把整个冒泡排序的流程图画出来？
开始
i=0
是
否
rR[i[]1>]>r[Ri +[21]]
tt==Rr[[i2]]
rR[i[1]=]=r[Ri [+21]]
rR[i[+21]=]=t t
分析：后面的排序只要 按照这种方法不断进行就 行了。
for(i=0;i<7-j;i++) if(r[i]>r[i+1]) {t=r[i]; r[i]=r[i+1]; r[i+1]=t;}
printf("The sorted numbers:\n"); for(i=0;i<8;i++) printf("%4d",r[i]); system("pause"); }
不断的这样画下去要画多少个
类似的选择结构？
8
…
二.画出第一趟排序的算法流程图： 用简洁的循环结构进行表示 根据流程图完善程序：
开始
i=0
是 r[ri[]0>]>r[ri[+1]1] 否 tt==rr[[i0]] r[Rir[]01=]=r[rRi[+[12]1]] r[ir[+11]]==t t
for( ; if ( {
我们预计最多一共要经过多少趟排序呢？
5
初始
序号
1
2
3
4
5
6
7
8
数据 49

冒泡排序的基本原理是对存放原始数据的数 组，按从前往后的方向进行多次扫描，每次 扫描称为一趟。当发现相邻两个数据的次序 与排序要求的大小次序不符合时，即将这两 个数据进行互换。这样，较小的数据就会逐 个向前移动，好象气泡向上浮起一样。
2020年10月2日
3
做一做：
下面我们请几位同学上来讲台为我们演示 一下这种排序的过程，首先按照被叫到的 顺序排列，再用这种方法由低到高进行排 序。
2020年10月2日
4
例：用冒泡排序的方法将下面一组无序数组 排成从小到大
{ 49,38,65,97,76,13,27,49 }
分析：首先为了方便分析，我们把所给的数据 先用一个表格列出来，如下：
2020年10月2日
5
原数据和序号
序 号
1
2
3
4
趟9排3序8 的6步5 骤9：7 76 13 27 49
R[1], R[2], R[3], R[4], R[5], R[6], R[7], R[8]
分析：
是
开始 R[1]>R[2]
第一步做什么？ 否
t:=R[1] R[1]:=R[2]
R[2]:= t
如这会何这样有交样交什换行换么数吗数问据？据题，，？
是 R[2]>R[3] 否
t:=R[2] R[2]:=R[3]
经过第二趟排序，实把现第了二什大么的目数的沉？到倒数第二个位置了!
2020年10月2日
7
观察原数据与第一、二趟排序后的数据
序 号
1
2
3
4
5
6
7
8
序数 据号49 138 625 97 3 76 143 27 5 49 6
7

冒泡排序的名称由来
• 名称由来：冒泡排序的名字来源于越小的元素会经过交换 慢慢“浮”到数列的顶端，如同气泡一样浮到水面上。
冒泡排序的基本思想
01
基本思想：通过不断地比较相邻 的两个元素，并进行交换，使得 较大的元素逐渐“冒泡”到数列 的末端。
02
重复以上过程，直到整个数列有序。
冒泡排序的算法步
总结词：简洁明了
详细描述：Python语言实现冒泡排序算法，代码简洁，易于理解。通过相邻元素比较和交换，使得每 一趟都能将最大的数移到正确的位置。
使用Java实现冒泡排序
总结词：结构严谨
详细描述：Java语言实现冒泡排序算法，代码结构严谨，适 合初学者学习。通过双重循环实现元素的比较和交换，能够 保证排序的正确性。
尽管冒泡排序在实际应用中可能不是最高效的算法， 但其简单易懂的特点使其成为教学和初学者学习排序 算法的常用选择。
THANKS.
优化交换过程
使用临时变量来交换元素，而不是通过多次赋值操作，这样可以减少交换过程中的操作 次数。
优化小数组的排序
使用快速排序或归并排序
对于小数组，使用快速排序或归并排序可能更为高效。 当数组大小小于一定阈值时，可以切换到其他排序算 法。
预处理小数组
对于小数组，可以通过预处理的方式将其排序，然后 将其存储在预定义的数组中，以减少排序时间。
使用C实现冒泡排序
总结词：高效快速
详细描述：C语言实现冒泡排序算法，利用指针和数组操 作，使得代码更加高效。通过减少不必要的比较和交换， 能够提高排序的效率。
冒泡排序的性能分
04
析
时间复杂度分析
01
最好情况：O(n)
02
最坏情况：O(n^2)

13 27 30
13 27
13
27
13
27 30 38 49
30
38
76 97 13
13 27 97 27 97 30 30 97
30 65 27
65 30 76
65
76 97
初 始 序 列
第 二 趟
第 三 趟
第 四 趟
第 五 趟
第 六 趟
第 七 趟
排 序 结 果
排序过程： （1）比较第一个数与第二个数，若为逆序a[0]>a[1]，则交换 （2）依次类推，比较第二个数与第三个数，直至第n-1个数和第n个数比 较为止——第一趟冒泡排序结束，结果最大的数被安置在最后一个元素位 置上。 （3）对前n-1个数进行第二趟冒泡排序，结果使次大的数被安置在第n-1
？
几个小问题
如何排逆序？
？
几个小问题
如何排逆序？ 改进
谢 谢！
常用的排序算法
冒泡排序 选择排序 插入排序 堆排序 归并排序 基数排序
快速排序
希尔排序
常用的排序算法
冒泡排序 选择排序 插入排序 堆排序 归并排序 基数排序
快速排序
希尔排序
• 冒泡排序（Bubble Sort），是一种较简单的排序算法。 • 通过无序区中相邻记录关键字间的“比较”和位置的“ 交换”，实现关键字较大（或较小）的记录向序列“一 端”移动，从而达到记录按关键字递增（或递减）顺序 排列的目的。 • 这个算法的名字由来是因为越大（或越小）的元素会经 由交换慢慢“浮”到数列的顶端，故名。
个元素位置。
（4）重复上述过程，共经过n-1趟冒泡排序后，排序结束。
开始
流程图
对数组元素 a[1] 到a[n]进行输入

在一组地址连续的存储单元中，即以数组作为存储结构。在这种情况下，
排序过程是对数据本身进行物理重排，即通过关键字之间的比较判断，将
数据移到合适的位置。另一种存储方式是以链表作为存储结构，排序过程
中无须移动数据，仅需修改指针即可。
以数组为例，每个数组元素都对应存储一个数据。如下图所示，存储在
数组元素d[0]中的数据是23，d[1]中存储的是20，等等。
另一种写法：
n=len(a)
flag=True
#flag值为True表示一遍加工中发生过交换
i=1
while i<=n-1 and flag==True:
flag=False
for j in range(n-1,i-1,-1):
if a[j]<a[j-1]:
a[j],a[j-1]=a[j-1],a[j]
d
23
20
13
18
14
11
0
1
2
3
4
5
如果对数组d中的6个数据按升序进行排序，即调整数组d中所有数据的存
储位置，使最小的数据存储在d[0]中，次小的数据存储在d[1]中……最大
的数据存储在d[5]中。数组d中的所有数据满足：d[0]≤d[1]≤d[2]≤d[3]
≤d[4]≤d[5]。
这里两个数组元素的比较：d[i]≤d[j](i=0,1,…,5;j=0,1,…5)，指的是d[i]中
原始数据
第1遍完成后的数据为
第2遍完成后的数据为
第3遍完成后的数据为
A.21,18,16,15,9,7,5,3
B.21,18,16,15,9,3,7,5
C.21,18,16,15,9,7,3,5

冒泡排序
什么是冒泡排序
冒泡排序是在一列数据中把较
小的数据逐次向上推移的一种排 序技术。
冒泡排序算法把待排序的n个元素的数 组看成是垂直堆放的一列数据，从最下面的 一个元素起，自下而上地比较相邻的两个元 素中的数据，将较小的数据换到上面的一个 元素中。重复这一过程，直到处理完最后两 个元素中的数据，称为一遍加工。
if a(j)<a(j-1) then 交换a(j) 和a(j-1)的值
Next j
Next j
第三遍 i=3
J从4到4
For j=4 to 4 step -1
if a(j)<a(j-1) then 交换a(j) 和a(j-1)的值
Next j
for i = 1 To 3
i=1…2…3
For jF=o4rtoji+=14 sTteop i-1+ 1 Step -1
原始序列
a(1) 36 a(2) 27 a(3) 32 a(4) 18
最终序列
a(1) 18 a(2) 27 a(3) 32 a(4) 36
四个数据怎样冒泡？
第一遍冒泡 J从4到2 i=1
For j=4 to 2 step -1
第二遍 J从4到3
i=2
For j=4 to 3 step -1
if a(j)<a(j-1) then 交换a(j) 和a(j-1)的值
任务1：写出详细比较过程 任务2：比较趟数？每趟比较次数？比较和交换的原则？
冒泡排序的四种方式比较
冒泡方式 比较趟数 每趟比较次数 比较、交换规则
自下而上 从小到大
自下而上 从小到大
自上而下 从小到大
自上而下 从大到小
3

运行结果：
谢谢！
学习永远 不晚。 JinTai College
感谢您的阅读！ 为 了 便于学习和使用， 本文档下载后内容可 随意修改调整及打印。
ห้องสมุดไป่ตู้
for(i=1;i<=7;i++) {
for(j=1;j<=8-i;j++) { if(R[j]>R[j+1]) { T=R[j]; R[j]=R[j+1]; R[j+1]=T; } }
} printf("排序后的数字是："); for(i=1;i<=8;i++)
printf("%d",R[i]; }
用冒泡排序法排列一组数
主讲：朱令
冒泡排序
教学目标：理解冒泡排序的原理 理解冒泡排序的流程图 加深对变量的使用的理解
教学难点：冒泡排序的原理和流程图
冒泡原理：质量大的（大的数据）下沉 质量小的（小的数据）上浮
方法：下沉法和上浮法
例：将一组无序数组排成从小到大 { 49,38,65,97,76,13,27,49 }
原数据和序号 序号 1 2 3 4 5 6 7 8 数据 49 38 65 97 76 13 27 49
第一趟下沉的步骤： 序号 1 2 3 4 5 6 7 8 数据 38 49 65 9776 791673 19237 29479 4997
经过一趟下沉，把最大的数沉到最底了
用流程图把这一趟下沉描述出来：
i=1, T=0
是
否
R[i] R[i 1]
T=R[i]
R[i]=R[i+1]
R[i+1]=T
i=i+1

a[2]与a[3]不交换
工业职业技术学院
t
程序设计基础----冒泡排序
冒泡排序算法分析与实现
第一轮比较
初值 条件 循环体
for( int j=0; j<4; j++ ) j变为3
｛ if ( a[3]>a[3+1] ) 如果前一个数大于后一个数
{ t=a[3];
a[3]=a[3+1]; t为中间变量，使得两数交换
{ t=a[j]; a[j]=a[j+1]; a[j+1]=t; ｝}
t为中间变量，使得两数交换
0
1
2
3
4
164
157
161
168
160
t
工业职业技术学院
程序设计基础----冒泡排序
冒泡排序算法分析与实现
第一轮比较
初值 条件 循环体
for( int j=0; j<4; j++ )
j代入初始值0
｛ if ( a[0]>a[0+1] ) 如果前一个数大于后一个数
比较 N-i 次 N个数
程序设计基础----冒泡排序
冒泡排序算法分析与实现
int a[5]={164,157,161,168,160}
工业职业技术学院
程序设计基础----冒泡排序
冒泡排序算法分析与实现
第一轮比较
初值 条件 循环体
for( int j=0; j<4; j++ )
｛ if ( a[j]>a[j+1] ) 如果前一个数大于后一个数
程序设计基础----冒泡排序
冒泡排序数据演示
第 三 轮 冒 泡 比 较