当前课程知识点：数据结构（Data Structures） > 7. Sorting > 7.4 Bubble Sort > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
各位同学大家好
我们接下来将学习
另外一种也比较常见的
简单排序算法
冒泡排序算法
所谓的冒泡 Bubble
是这么的一个过程
给定一个数据的序列
我们从最后一个位置开始
不断地进行相邻位置元素的比较
如果后面的元素要小于前面的
我们就进行一次数据的交换
我们来看一个例子
这里最后的元素15
和前面的23比较
因为后面的比前面小
所以我们进行一次交换
然后我们继续这种相邻位置的比较
我们将倒数第二个位置的15
和前面的14继续进行比较
因为后面的要大于等于前面的元素
满足排序的要求
所以不用交换
这个比较要继续下去
只要后面的元素比前面的小
我们要进行交换
直到最开始的两个元素
进行比较操作
这样一个从后往前相邻位置元素
进行比较和交换的过程
我们就称为
一个数据冒泡的过程
那么为什么叫冒泡呢
因为我们留意到
经过这样的一个过程之后
在一组数据中
最小的那个元素被交换到了
最前面的位置
这个最小的元素
在进行相邻位置比较的时候
总是会被交换到前面的位置
它一直会被交换到最前面的位置
这个最小的元素
就从序列中冒出来了
当然了 我们可以看到
经过一次冒泡之后
我们还是无法实现所有数据的排序的
所以我们可以想到
应该是需要多次冒泡
实际上我们通过N-1次冒泡
就可以实现这个排序的过程
为了方便分析
我们为每次冒泡
分配了一个序号
变量i记录了冒泡的序号
通过第一次冒泡
这个15会被交换到23的前面
14会被交换到28的前面
13会被交换到最前面
最小的元素13
经过一次冒泡之后
被交换到0号位置上
我们如果对这个序列
再一次进行冒泡
那么除了13之外
剩下的元素最小值14
将会被交换到1号位置
在经过一次冒泡
我们就会把剩下元素里面
最小的元素调整到
正确的排序位置上面去
经过N-1次类似这样的冒泡过程
所有的元素将会处在于
正确的位置上面
所以冒泡排序的过程非常简单
就是这样的一个N-1次
从后往前的冒泡过程
下面我们来看一下
冒泡排序算法的具体实现
这里的bubsort函数
它有两个参数
第一个是存放数据的数组A
第二个是数组中的元素个数N
因为我们需要N-1次冒泡
所以这里我们采用一个
执行N-1次的for循环
其中迭代变量i
它的取值范围是从0到N-2
在第二次冒泡的过程中
我们将会把数组中的
排行第i的元素
将它冒出来了
并且交换到i号位置上面去
为了实现这个冒泡
我们需要从后往前
进行相邻位置元素的比较
for循环来实现
这里迭代变量j
表示当前比较的位置
取值范围是从最后的位置N-1
到前面的i+1
每次我们将j位置的元素
和前面的j-1次的元素进行比较
如果后面的比前面的小
我们就被把这两个元素
进行一个交换
经过N-1次的冒泡之后
我们就得到了一个排好序的序列
下面我们来分析一下
冒泡排序它的算法复杂度
冒泡排序的过程是比较简单的
核心部分是由一个两层for循环来构成的
循环执行的次数
和序列中的数据的分布是没有关系的
只是和数据的个数N有关系
因此我们可以推导出来
冒泡排序它的算法复杂度
在最好的情况
最差的情况以及平均的情况下
都是O(n^2)
下面我们来分析一下
冒泡排序它的稳定性
我们通过一个例子
来去做稳定性的分析
在这个数组中有两个关键字
都是等于13的
我们用不同的颜色来进行区分
首先我们进行第一次冒泡
从后往前相邻位置的元素进行比较
因为15比23要小
所以进行交换
然后15和13进行比较
不用交换
13和28比较 要交换
这个时候两个13挨在了一起
两个13进行比较的时候
因为后面的13要大于等于
前面的13
那是满足序的要求的
所以不用交换
因此这两个13
它的先后顺序并没有发生改变
后面的13它不会超过前面的13
而跑到前面去
继续这个冒泡的过程
最终黑色的13
冒到了最前面
然后进行第二轮冒泡
红色的13将会出现在第二个位置
它也不会超过前面的黑色的13
我们可以看出
由于冒泡的排序过程中
总是相邻位置的元素
进行比较和交换
所以具有相同值的这些关键字
他们的先后位置不会发生变化
因此我们说冒泡排序
它是一种稳定的排序算法
我们最后把前面
所学习到的3个简单排序算法
进行一个对比
在大多数的情况下
插入排序 冒泡排序和选择排序
它们算法的复杂度
都是O(n^2)的平方
是一类相对比较慢的排序算法
但是也有一种情况
它是例外的
也就是说在最好的情况下
插入排序它是很快的
可以在O(n)的时间内完成
需要排序的序列
它越是接近有序的状态
那么插入排序
它的性能就会越接近这个O(n)
这一点可以被用来去创建
更加优化的算法
我们在后面将会学习到
更多的相关知识
这节课我们就讲到这里
下节课我们再见
-1. Introduction--1.1 Introduction of Data
-1.1 Introduction of Data Structure
--Introduction of Data Structure
-1.2 Data Structure and A
-1.2 Data Structure and Algorithm
--Video
-1.3 Asymptotic Analysis
-1.3 Asymptotic Analysis
--Video
-1.4 Simplifying Rules of
-1.4 Simplifying Rules of Asymptotic Analysis
--Video
-2.1 Introduction of List
-2.1 Introduction of List
--Video
-2.2 Array based List
-2.2 Array based List
--Video
-2.3 Insertion Operation on Array
-2.3 Insertion Operation on Array based List
--Video
-2.4 Remove Operation on Array based List
-2.4 Remove Operation on Array based List
--Video
-2.5 Linked list
-2.5 Linked list
--Video
-2.6 Insertion Operation on Linked list
-2.6 Insertion Operation on Linked list
--Video
-2.7 Remove Operation on Linked list
-2.7 Remove Operation on Linked list
--Video
-2.8 SetPos Operation on Linked list
-2.8 SetPos Operation on Linked list
--Video
-2.9 Stack
-2.9 Stack
--Video
-2.10 Application of Stack
--Video
-2.11 Queue
-2.11 Queue
--Video
-3.1 Definition of Binary Tree
-3.1 Definition of Binary Tree
--Video
-3.2 Implementation of Binary Tree
-3.2 Implementation of Binary Tree
--Video
-3.3Traversal
-3.3 Traversal
--Video
-3.4 Binary Search Tree
-3.4 Binary Search Tree
--Video
-3.5 Search on BST
-3.5 Search on BST
--Video
-3.6 Insertion on BST
-3.6 Insertion on BST
--Video
-3.7 Introduction of Heap
-3.7 Introduction of Heap
--Video
-3.8 Construction of Heap
-3.8 Construction of Heap
--Video
-3.9 Operations on Heap
--Video
-3.10 General Tree
--Video
-4.1 Definition of Searching
--Video
-4.2 Searching of Sorted Array
-4.2 Searching of Sorted Array
--Video
-4.3 Definition of Hash Table
--Video
-4.4 Collision in Hash Table
-4.4 Collision in Hash Table
--Video
-4.5 Extension of Linear Probing
--Video
-4.6 Insertion Operation of Hash Table
--Video
-4.7 Search Operation of Hash Table
-4.7 Search Operation of Hash Table
--Video
-5.1 Introduction of Index
--Video
-5.2 Linear Index
-5.2 Linear Index
--Video
-5.3 2-3 tree index
-5.3 2-3 tree index
--Video
-5.4 Implementation of 2-3 tree
-5.4 Implementation of 2-3 tree
--Video
-5.5 B-Tree
-5.5 B-Tree
--Video
-5.6 Insertion Operation on B+ Tree
--Video
-5.7 Deletion Operation on B+ Tree
--Video
-6.1 Definition of Graph
--Video
-6.2 Implementation of Graph
--Video
-6.3 Adjacency Matrix
--Video
-6.4 Adjacency List
--Video
-6.5 Graph Traversal - DFS
--Video
-6.6 Graph Traversal - BFS
--Video
-6.7 Topological Sort
--Video
-6.8 Shortest Path Problem
--Video
-6.9 Single Source Shortest Path
--Video
-6.10 Dijkstra Algorithm
--Video
-7.1 Sorting Problem
--Video
-7.2 Insertion Sort
--Video
-7.3 Selection Sort
--Video
-7.4 Bubble Sort
--Video
-7.5 Shell Sort
--Video
-7.6 Quick Sort
--Video
-7.7 Heap Sort
--Video
-7.8 Comparison
--Video
