Python实现冒泡排序
Python实现冒泡排序
一、冒泡排序简介
冒泡排序(Bubble Sort)是一种常见的排序算法,相对来说比较简单。
冒泡排序重复地走访需要排序的元素列表,依次比较两个相邻的元素,如果顺序(如从大到小或从小到大)错误就交换它们的位置。重复地进行直到没有相邻的元素需要交换,则元素列表排序完成。
在冒泡排序中,值最大(或最小)的元素会通过交换慢慢“浮”到元素列表的“顶端”。就像“冒泡”一样,所以被称为冒泡排序。
二、冒泡排序原理
冒泡排序的原理如下:
1. 比较相邻的两个元素。如果第一个比第二个大则交换他们的位置(升序排列,降序则反过来)。
2. 从列表的开始一直到结尾,依次对每一对相邻元素都进行比较。这样,值最大的元素就通过交换“冒泡”到了列表的结尾,完成第一轮“冒泡”。
3. 重复上一步,继续从列表开头依次对相邻元素进行比较。已经“冒泡”出来的元素不用比较(一直比较到结尾也可以,已经“冒泡”到后面的元素即使比较也不需要交换,不比较可以减少步骤)。
4. 继续从列表开始进行比较,每轮比较会有一个元素“冒泡”成功。每轮需要比较的元素个数会递减,一直到只剩一个元素没有“冒泡”时(没有任何一对元素需要比较),则列表排序完成。
以列表 [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] 进行升序排列为例。列表的初始状态如下图。
要进行升序排列,则大的元素要依次“冒泡”到列表的结尾。
1. 从列表的开头,比较相邻的两个元素,如果第一个值比第二个值大则交换。10小于17,不需要交换。
2. 向列表的结尾方向“走访”,比较第二组相邻的元素(第二个和第三个),如果不是从小到大则交换。17小于50,不需要交换。
3. 继续“走访”,比较第三组相邻的元素,如果不是从小到大则交换。50大于7,所以需要交换。
4. 对顺序错误的元素进行位置交换。交换50和7的位置。
5. 一直“走访”到结尾,第一轮“冒泡”结束后,值最大的元素“冒泡”到了列表的结尾。50“冒泡”到了列表结尾。
在下一轮“冒泡”中,不需要再将50进行比较,需要比较的元素个数减1。
6. 从列表开头,重复下一轮“冒泡”,每进行一轮“冒泡”,需要比较的元素都少一个,直到没有元素对需要比较时,整个列表排序完成。排序结果如下图。
三、Python实现冒泡排序
# coding=utf-8
def bubble_sort(array):
for i in range(1, len(array)):
for j in range(0, len(array)-i):
if array[j] > array[j+1]:
array[j], array[j+1] = array[j+1], array[j]
return array
if __name__ == '__main__':
array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
print(bubble_sort(array))
运行结果:
[5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]
代码中,i 表示第几轮“冒泡”,j 表示“走访”到的元素索引。每一轮“冒泡”中,j 需要从列表开头“走访”到 len(array) – i 的位置。
四、冒泡排序的时间复杂度和稳定性
1. 时间复杂度
在没有特殊说明时,一般都是计算最坏时间复杂度。
在冒泡排序中,最坏的情况是元素列表的初始状态是完全逆序排列的,需要进行 n-1 轮“冒泡”,每一轮“冒泡”需要进行 n-i 次比较和交换操作。i 的平均值为 n/2 ,时间复杂度为 T(n)=n(n-1)/2 ,再乘每次操作的步骤数(常数,不影响大O记法),所以冒泡排序的时间复杂度为 O(n^2) 。
2. 稳定性
排序算法的稳定性指,当元素列表中有相等的元素时,相等元素的相对次序是否固定不变,如果相对次序固定不变,则排序算法是稳定的,反之。
在冒泡排序中,每次比较两个元素,当元素的大小顺序错误时才会进行交换,如果元素列表中有两个相等的元素,它们最终肯定会相邻在一起,但对它们比较时不会进行交换,相对次序是保持不变的。所以冒泡排序是一种稳定的排序算法。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/181421.html原文链接:https://javaforall.cn
相关文章
- Python 进行 SSH 操作,实现本地与服务器的链接,进行文件的上传和下载
- 用python画圣诞树、樱花树、卡通图案及打包成exe文件[通俗易懂]
- Python实现 —【简易】12306爬虫[通俗易懂]
- 【说站】python链表实现左移和右移
- 【说站】python格式化经纬度的方法
- python爬虫库_python爬虫实战百度云盘
- 冒泡排序python实现_冒泡排序python代码优化
- Python:利用python代码编程实现将视频的avi格式转换为MP4格式
- python上的表白代码_用Python实现表白代码
- 数据结构与算法Python_数据结构与算法python语言实现
- Python之服务巡检
- 谷歌浏览器WebKit/Chrome时间戳与普通Unix时间戳互转 - 带Python/PHP实现
- Python 实现动态的工厂模式
- Python基础语法-内置函数和模块-自定义模块
- 现代 Python 代码的密码管理之道
- Python index()方法:检测字符串中是否包含某子串
- 利用python实现冒泡排序详解编程语言
- Python实现快速连接Redis数据库(python连接redis)
- 出版商统计出最受欢迎的编程语言:Python 居首
- Python如何使用MySQL构建立连接(python怎么连接mysql)
- Python脚本实现Linux命令快捷控制(python执行linux命令)
- 利用Python实现文本数据导入Redis库(文本数据导入redis)
- 25 行 Python 代码实现人脸检测——OpenCV 技术教程
- python搭建简易服务器分析与实现
- python实现的一只从百度开始不断搜索的小爬虫
- python冒泡排序算法的实现代码
- python实现监控windows服务并自动启动服务示例
- Python实现3行代码解简单的一元一次方程