用python實作冒泡排序和選擇排序（Python經典程式設計案例）

1.冒泡排序：

def bubble_sort(list):
    for i in range(0, len(list)):
        is_sorted = True
        for j in range(0, len(list) - i - 1):
            if list[j] > list[j + 1]:
                list[j], list[j + 1] = list[j + 1], list[j]
                is_sorted = False
        if is_sorted:
            return


list1 = [97, 3, 6, 1, 8, 5, -20, 100, 50, 200, -32, 123]
bubble_sort(list1)
print(list1)
           

執行結果如下圖：

2.選擇排序：

def choose_sort(list):
    list_len = len(list)
    for i in range(0, list_len):
        for j in range(i + 1, list_len):
            if list[i] > list[j]:
                list[i], list[j] = list[j], list[i]
                

list1 = [3, 6, 1, 8, 5, -20, 100, 50, 200]
choose_sort(list1)
print(list1)
           

執行結果如下圖：

3.選擇排序、冒泡排序、插入排序、快速排序：

# -*- encoding: utf-8 -*-
import random


# O(n^2)
def selection_sort(lyst):
    """選擇排序"""
    i = 0
    while i < len(lyst) - 1:
        min_index = i
        j = i + 1
        while j < len(lyst):
            if lyst[j] < lyst[min_index]:
                min_index = j
            j += 1
        if i != min_index:
            lyst[i], lyst[min_index] = lyst[min_index], lyst[i]
        i += 1


# O(n^2)
def bubble_sort(lyst):
    """冒泡排序"""
    # 外層循環len(lyst) - 1, j最大能取到倒數第二個值, j+1取到最後一個
    for i in range(1, len(lyst)):
        for j in range(0, len(lyst) - 1):
            if lyst[j] > lyst[j + 1]:
                lyst[j], lyst[j + 1] = lyst[j + 1], lyst[j]


# O(n^2)
def insertion_sort(lyst):
    """插入排序"""
    # i=1, 表示假定 lyst[0] 為有序資料, 下一個為無序資料
    for i in range(1, len(lyst)):
        item = lyst[i]
        j = i - 1
        while j >= 0:
            # 如果待排資料小于lyst[j], 就往後覆寫指派
            if item < lyst[j]:
                lyst[j + 1] = lyst[j]
                j -= 1
            # 因為lyst[j] 是目前有序數值中最大的數, 如果比它還大就直接跳出
            else:
                break
        # j 多減了1
        lyst[j + 1] = item


# O(nlogn)
# 兩種快速排序代碼
def quick_sort(lyst, left, right):
    """快速排序"""
    middle = (left + right) // 2
    # 基準點
    pivot = lyst[middle]
    if left < right:
        # 邊界
        boundary = left
        # 将基準點與最後一個點交換
        lyst[middle], lyst[right] = lyst[right], lyst[middle]
        # 周遊邊界右邊, 是否小于基準點
        for index in range(left, right):
            if lyst[index] < pivot:
                lyst[boundary], lyst[index] = lyst[index], lyst[boundary]
                boundary += 1
        lyst[boundary], lyst[right] = lyst[right], lyst[boundary]
        # 左右子清單
        quick_sort(lyst, left, boundary - 1)
        quick_sort(lyst, boundary + 1, right)


def quick_sort2(lyst, left, right):
    """快速排序的另一種實作"""
    if left >= right:
        return None
    # 基準點
    pivot = lyst[left]
    i, j = left, right
    while i < j:
        # 右分區向左
        while i < j and lyst[j] > pivot:
            j -= 1
        if i < j:  # 交換
            lyst[i], lyst[j] = lyst[j], lyst[i]
            i += 1
        # 左分區向右
        while i < j and lyst[i] < pivot:
            i += 1
        if i < j:  # 交換
            lyst[i], lyst[j] = lyst[j], lyst[i]
            j -= 1
    lyst[i] = pivot
    quick_sort2(lyst, left, i - 1)
    quick_sort2(lyst, i + 1, right)


def get_lyst(lyst):
    lyst.clear()
    for i in range(8):
        lyst.append(random.randint(1, 8))


def main():
    lyst = []
    print("selection_sort:")
    get_lyst(lyst)
    print(lyst)
    selection_sort(lyst)
    print(lyst)

    print("\nbubble_sort:")
    get_lyst(lyst)
    print(lyst)
    bubble_sort(lyst)
    print(lyst)

    print("\ninsertion_sort:")
    get_lyst(lyst)
    print(lyst)
    insertion_sort(lyst)
    print(lyst)

    print("\nquick_sort:")
    get_lyst(lyst)
    print(lyst)
    quick_sort(lyst, 0, len(lyst) - 1)
    print(lyst)

    print("\nquick_sort2:")
    get_lyst(lyst)
    print(lyst)
    quick_sort(lyst, 0, len(lyst) - 1)
    print(lyst)


if __name__ == '__main__':
    main()