Python元组与字符串操作（10）——冒泡法

冒泡法

属于交换排序，元素两两比较大小，交换位置，结果可升序或降序排列

nums = [2,5,1,6,7,9,8,3,4]

for i in range(len(nums)):    ##计数器0~8

    flag = True    ##假定达到目标排序，可以提前结束

    for j in range(len(nums)-1-i):

        if nums[j] > nums[j+1]:

            nums[j],nums[j+1] = nums[j+1],nums[j]

            ##temp = nums[j]

            ##nums[j] = nums[j+1]

            ##nums[j+1] = temp

            flag = False    ##发生交换，继续下一轮排序

    if not flag:

        break

print(nums)

[1, 2, 3, 4, 5, 6, 7, 8, 9]

冒泡法总结

冒泡法需要数据一轮轮比较

可以设定一个标记判断此轮是否有数据交换发生，如果没有发生交换，可以结束排序，如果发生交换，继续下一轮排序

最差的排序情况是，初始顺序与目标顺序完全相反，遍历次数1，...，n-1之和n(n-1)/2

最好的排序情况是，初始顺序与目标顺序完全相同，遍历次数n-1

时间复杂度O(n**2)