冒泡法: 属于交换排序, 两两比较大小, 交换位置, 结果分为升序和降序排列.
1, 升序:
n 个数从左至右, 编号从 0 开始到 n-1, 索引 0 和 1 的值比较, 如果索引 0 大, 则交换两者位置, 如果索引 1 大, 则不交换. 继续比较索引 1 和 2 的值, 将大值放在右侧. 直至 n-2 和 n-1 比较完, 第一轮比较完成. 第二轮从索引 0 比较到 n-2, 因为最右侧 n-1 位置上已经是最大值了. 依次类推, 每一轮都会减少最右侧的不参与比较, 直至剩下最后 2 个数比较.
2, 降序:
和升序相反
3, 优化:
冒泡法需要数据一轮轮比较, 可以设定一个标记判断此轮是否有数据交换发生, 如果没有发生交换, 可以结束排序, 如果发生交换, 继续下一轮排序
最差的排序情况是, 初始顺序与目标顺序完全相反, 遍历次数 1,...,n-1 之和 n(n-1)/2
最好的排序情况是, 初始顺序与目标顺序完全相同, 遍历次数 n-1
4, 时间复杂度 O(n2)
- # -*- coding:utf-8 -*-
- # version:python3.7
- nums_list = [
- [1,2,3,4,5,6,7,8,9],
- [1,9,8,5,6,7,4,3,2],
- [9,8,7,6,5,4,3,2,1]
- ] #建立三组测试数据
- nums = nums_list[1]
- print(nums)
- length = len(nums)
- for i in range(length): #需要九趟
- flag = True #假定没有发生交换
- for j in range(length-1-i):
- if nums[j]> nums[j+1]:
- nums[j],nums[j+1] = nums[j+1],nums[j]
- flag = False #发生了交换
- if flag:
- break
- print(nums)
执行结果:
- [1, 9, 8, 5, 6, 7, 4, 3, 2]
- [1, 2, 3, 4, 5, 6, 7, 8, 9]
来源: https://www.cnblogs.com/zyybky/p/12517353.html