2021-01-01

Python bubble sort 泡沫排序法

本篇 ShengYu 介紹排序法中最簡單經典的泡沫排序法 bubble sort，並且由 Python 來實作泡沫排序法 bubble sort。

泡沫排序法 bubble sort 基本原理

泡沫排序法 bubble sort 的原理是將兩個相鄰的數值相比，假如前一個數值比後一個數值大時，就互相對調，實作時就是使用兩層迴圈，針對該串列掃兩次，最終將能獲得排序好的升序串列(由小到大)，
讓我來舉個簡單的例子吧！假如今天有一串數字串列 3,2,4,5,1 要使用泡沫排序 bubble sort，

第一次迴圈排序步驟如下，所以第一次迴圈就能把最大的數值 5 給交換到最後了，剩餘要排序的數值還有 4 個，

2,3,4,5,1
2,3,4,5,1
2,3,4,5,1
2,3,4,1,5

第二次迴圈排序步驟如下，第二次迴圈，就把第二大的數值 4 給交換到倒數第二個了，剩餘要排序的數值還有 3 個，

1
2
3

2,3,4,1,5
2,3,4,1,5
2,3,1,4,5

第三次迴圈排序步驟如下，第三次迴圈，就把第三大的數值 3 給交換到倒數第三個了，剩餘要排序的數值還有 2 個，

1 2	2,3,1,4,5 2,1,3,4,5

第四次迴圈排序步驟如下，第四次迴圈，就把第三大的數值 2 給交換到倒數第四個了，剩餘要排序的數值還有 1 個，

1,2,3,4,5

迴圈結束，排序完成，

Python 實作泡沫排序法 bubble sort

由上述的簡單例子推演可以了解了泡沫排序 bubble sort 基本原理後，接著就開始練習用 Python 來寫程式，那我們來看看 Python 泡沫排序怎麼寫吧！

python3-bubble-sort.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def bubble_sort(nums):
    n = len(nums)
    for i in range(n-1):
        for j in range(n-i-1):
            if nums[j] > nums[j+1]:
                temp = nums[j]
                nums[j] = nums[j+1]
                nums[j+1] = temp
            
nums = [3,2,4,5,1]
print("排序前 = %s" % nums)
bubble_sort(nums)
print("排序後 = %s" % nums)

Python 程式跑出來的結果如下，經過泡沫排序法 bubble sort 排序後的結果的確是由小排到大。

1 2	排序前 = [3, 2, 4, 5, 1] 排序後 = [1, 2, 3, 4, 5]

下一篇介紹 selection sort 選擇排序法