蓝桥杯练习 冒泡排序

冒泡排序

想法: 让一个数字和它相邻的下一个数字进行比较运算 如果前一个数字大于后一个数字，交换两个数据的位置。

例如：给定一个数组：nums = [6, 5, 3, 1, 8, 7, 2, 4]

输出为：nums=[1, 2, 3, 4, 5, 6, 7, 8]

---

（未优化）代码：

nums = [6, 5, 3, 1, 8, 7, 2, 4]
j = 0
while j < len(nums) - 1:
    i = 0
    while i < len(nums) - 1:
        if nums[i] > nums[i + 1]:
            nums[i], nums[i + 1] = nums[i + 1], nums[i]
        i += 1
    j += 1
print(nums)

---

解析：

• 代码中用了两处循环：

i代表两个数的比较，n个数需要比较n-1次，因此i

j代表比较的趟数，n个数需要比较n-1趟，因此j

python中交换数组元素：nums[i], nums[i + 1] = nums[i + 1], nums[i]

---

（优化）代码：

nums = [6, 5, 3, 1, 8, 7, 2, 4]
j = 0
while j < len(nums) - 1:
    flag = True
    i = 0
    while i < len(nums) - 1 - j:
        if nums[i] > nums[i + 1]:
            flag = False
            nums[i], nums[i + 1] = nums[i + 1], nums[i]
        i += 1
    if flag == True:
        break
    j += 1
print(nums)

解析：

• 每一趟比较次数的优化（i）

代码不需要每趟都比较len（nums）-1次 第一趟比较已经把最大的数放到后边，因此第二趟不需要与最后的数进行比较（只需要比较到倒数第二位即可），

第一趟比较时，j=0，多比较了0次

第一趟比较时，j=1，多比较了1次

第一趟比较时，j=2，多比较了2次 ~~~~~

以此类推 可以发现每趟比较次数i与j是有关系的，每一趟比较次数可以优化为i < len(nums) - 1 - j

• 比较趟数的优化（j）

第一趟：[6, 5, 3, 1, 8, 7, 2, 4]
第二趟：[5, 3, 1, 6, 7, 2, 4, 8]
第三趟：[3, 1, 5, 6, 2, 4, 7, 8]
第四趟：[1, 3, 5, 2, 4, 6, 7, 8]
第五趟：[1, 3, 2, 4, 5, 6, 7, 8]
第六趟：[1, 2, 3, 4, 5, 6, 7, 8]
第七趟：[1, 2, 3, 4, 5, 6, 7, 8]

可以发现第六趟的时候排序已经完成了，下边就不需要再进行循环了。

因此我们可以在外循环中定义个falg ，假定flag为True（假定排序已经完成），在内循环中加入flag = False（如果数据交换证明排序未完成），添加一个判断语句if flag == True:如果成立（证明排序已经完成）使用break跳出循环。

       每天学习一点点，加油，兄弟们。蓝桥杯准备中........