Python程式設計：排序算法之冒泡排序

清單排序

• 将無序清單變為有序清單
• 輸入：無序清單
• 輸出：有序清單

常見的排序算法

名稱	時間複雜度	空間複雜度
冒泡排序	O(n^2)	O(1)
選擇排序
插入排序
快速排序	mid
堆排序	high
歸并排序
基數排序	少見
希爾排序
桶排序

排序算法關鍵點：

• 有序區
• 無序區

• 清單每兩個相鄰的數，如果前邊的比後邊的大，那麼交換這兩個數

代碼實作

import random

# 冒泡排序，從小到大排序O(n^2)
def bubble_sort(lst):
    count = 0
    n = len(lst) - 1  # 9 總周遊次數，比序列總數少1
    for i in range(n): # 0-8
        for j in range(n-i): # 8-0
            if lst[j]>lst[j+1]:  # 前者比後者大則交換
                lst[j], lst[j+1] = lst[j+1], lst[j]
            count += 1
    print("count: %s", count)

# 冒泡排序改進，從小到大排序
def bubble_sort_1(lst):
    count = 0
    n = len(lst) - 1  # 9 總周遊次數，比序列總數少1
    for i in range(n): # 0-8
        exchange = False
        for j in range(n-i): # 8-0
            if lst[j]>lst[j+1]:  # 前者比後者大則交換
                lst[j], lst[j+1] = lst[j+1], lst[j]
                exchange = True
            count += 1
        if exchange==False:  # 如果周遊結束沒有任何交換,說明已經有序
            break

    print("count: %s", count)


lst = list(range(10))
# random.shuffle(lst) #打亂順序
bubble_sort(lst)
# count: %s 45

bubble_sort_1(lst)
# count: %s 9

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