一、排序算法的稳定性
二、冒泡排序
a、重复比较相邻的元素,如果前面的比后面的大,就交换它们两个
b、每次遍历整个数组,遍历完成后,下一次遍历的范围往左缩1位
c、重复前面步骤,直到排序完成
三、代码块
n个数组循环n-1次
def bobbleSort(nums):
n = len(nums) # 得到数组的长度
for i in range(n - 1): # n个数组循环n-1次
for idx in range(0, n - 1 - i):
if nums[idx] > nums[idx + 1]:
nums[idx], nums[idx + 1] = nums[idx + 1], nums[idx]
print(nums)
bobbleSort([6, 5, 4, 3, 2, 1])
时间复杂度为：O(n^2)；当我的数组为test=[1,2,3,4,5,6,7]时，它原本就是有序的了，不需要执行换位操作，但是第5，6行代码还会去执行，时间复杂度也为O(n^2)
四、冒泡排序优化
代码中加入标志flag=False，如果flag=False，那么说明本轮排序没有进行任何变量交换，数组已经时有序的了
时间复杂度为O(1)
def bobbleSort(nums):
n = len(nums) # 得到数组的长度
for i in range(n - 1): # n个数组循环n-1次
flag=False
for idx in range(0, n - 1 - i):
if nums[idx] > nums[idx + 1]:
nums[idx], nums[idx + 1] = nums[idx + 1], nums[idx]
flag=True
print(nums)
#如果flag为false，那么说明本轮排序没有进行任何变量交换
#数组已经是有序的了
if not flag:
break
#时间复杂度为O(1)
bobbleSort([1, 2, 3, 4, 5, 6])
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/123549.html
