算法札记2_冒泡算法

冒泡排序：冒泡排序无疑是最为出名的排序算法之一，从序列的一端开始往另一端冒泡，依次比较相邻的两个数的大小。重复性的工作直到没有可以交换的两个元素，说明数列已经排序完成。冒泡算法的时间复杂度为O(n2)。

image.png

算法思想

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 每次循环固定一个数，比较的次数依次减1
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

经典排序算法学习笔记_冒泡算法
冒泡排序
一文看懂冒泡排序算法
吴大佬-必须好好学习

图片发自简书App

通过一个简单的例子来进行说明，冒泡排序算法的具体过程，现在有一个列表list = [8, 2, 5, 9, 7]，如何通过冒泡算法实现排序：

1.jpg

首先比较第一个数字和第二个数字，发现8比2大，则8位置不动，整体还是[8,2,5,9,7]，此时指针右移一格

2.jpg

比较第二个数和第三个数的大小，发现2比5小，则交换它们的位置，5放到2的前面，变成[8,5,2,9,7]，指针右移一格

3.jpg

比较第三个数和第四个数的大小，发现2比9小，交换位置，变成[8,5,9,2,7]，指针右移一格。

4.jpg

比较第四个数和第五个的大小，发现2比7小，交换位置，变成[8,5,9,7,2]，指针右移发现已经到底。

第一轮的冒泡结束，第二轮开始

5.jpg

比较第一个和第二个数，8比5大，保持不变，指针右移

6.jpg

比较第二个和第三个数，发现5比9小，交换位置，变成[8,9,5,7,2]，只有指针右移。

7.jpg

比较第三个和第四个数，发现5也比7小，交换位置，变成[8,9,7,5,2]，指针右移；再比较第四个和第五个数字，5比2大，保持不变。

8.jpg

经过两轮的冒泡排序，变成了[8,9,7,5,2]的效果，经过多次循环的过程最终一定会变成[9,8,7,5,2]

Python代码实现

list1 = [1,7,3,5,2]

length = len(list1)

for i in range(length-1)：# 外层控制总的循环次数，需要length-1；最后一个数自己无需比较，写成length也无妨，一般写成length-1。同时i表示本轮结束后有i个数已经排好序

  for j in range(length-1-i):    #  内层循环控制每轮循环中比较的次数，但i轮之后排好序的i数无需进行排列。

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

      list1[j], list1[j+1] = list1[j+1], list1[j]

print(list1)

def bubble_sort(nums):

    for i in range(0, len(nums) - 1):   # 设置冒泡排序进行的次数

        for j in range(0, len(nums) - 1 - i):  # j为列表下标

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

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

    return nums

 

if __name__ == "__main__":

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

    bubble_sort(lists)

    print(lists)



# print(bubble_sort([1,9,3,5,2,8,4,6,10,7]))

def bubble(list1):

    length = len(list1)

    for i in range(length - 1):

        print(f"i = {i}")

        for j in range(length - 1 - i):

            print(f"j = {j}", end=" ")

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

                print("swap", end=" ")

                list1[j], list1[j+1] = list1[j+1], list1[j]

        print(list1)

• i代表循环的总轮数为列表的长度len(list1)；外层
• j代表每次循环中比较的次数
  • 减1：最后一个数不需要比较
  • 减i：i轮之后无需再比较已经排好序的i个数

优化

def bubble(list1):

    length = len(list1)

    for i in range(length - 1):

        flag = False   # 设置一个标志位

        for j in range(length - 1 - i):

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

                list1[j], list1[j+1] = list1[j+1], list1[j]

                flag = True    # 如果两个元素之间交换了位置，标志位设为True

        if flag == False:  # 等价于if  not flag

            break  # 如果经历一个循环之后还是False，结束循环

    return list1