Python算法札记1_冒泡排序

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

image.png

---

算法思想

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

经典排序算法学习笔记_冒泡算法
冒泡排序

---

通过一个简单的例子来进行说明，冒泡排序算法的具体过程，现在有一个列表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)：
  for j in range(length-1-i):    # 每次排序结束，j的次数都要减1，
    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) - i - 1):  # 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(bubbleList):
    listLength = len(bubbleList)
    while listLength > 0:
        for i in range(listLength - 1):
            if bubbleList[i] > bubbleList[i+1]:
                bubbleList[i], bubbleList[i+1] = bubbleList[i+1], bubbleList[i]
        listLength -= 1
    return bubbleList
 
if __name__ == '__main__':
    bubbleList = [3, 4, 1, 2, 5, 8, 0]
    bubble(bubbleList)
    print(bubbleList)