C 檢索和排序

部份內容由 Hello 演算法 提供

一、冒泡排序

冒泡排序（bubble sort）透過連續地比較與交換相鄰元素實現排序。這個過程就像氣泡從底部升到頂部一樣，因此得名冒泡排序。

如下圖所示，冒泡過程可以利用元素交換操作來模擬：從陣列最左端開始向右走訪，依次比較相鄰元素大小，如果“左元素 > 右元素”就交換二者。走訪完成後，最大的元素會被移動到陣列的最右端。

第1步

第2步

第3步

第4步

第5步

第6步

第7步

演算法流程

設陣列的長度為 $n$ ，泡沫排序的步驟如下圖所示。

1. 首先，對 $n$ 個元素執行“冒泡”，將陣列的最大元素交換至正確位置。
2. 接下來，對剩餘 $n - 1$ 個元素執行“冒泡”，將第二大元素交換至正確位置。
3. 以此類推，經過 $n - 1$ 輪“冒泡”後，前 $n - 1$ 大的元素都被交換至正確位置。
4. 僅剩的一個元素必定是最小元素，無須排序，因此陣列排序完成。

示例程式碼

def bubble_sort(nums: list[int]):
    """泡沫排序"""
    n = len(nums)
    ## 外迴圈：未排序區間為 [0, i]
    for i in range(n - 1, 0, -1):
        ## 內迴圈：將未排序區間 [0, i] 中的最大元素交換至該區間的最右端
        for j in range(i):
            if nums[j] > nums[j + 1]:
                ## 交換 nums[j] 與 nums[j + 1]
                nums[j], nums[j + 1] = nums[j + 1], nums[j]

二、選擇排序

選擇排序（selection sort）的工作原理非常簡單：開啟一個迴圈，每輪從未排序區間選擇最小的元素，將其放到已排序區間的末尾。

設陣列的長度為 $n$ ，選擇排序的演算法流程如下圖所示。

1. 初始狀態下，所有元素未排序，即未排序（索引）區間為 $[0, n-1]$ 。
2. 選取區間 $[0, n-1]$ 中的最小元素，將其與索引 $0$ 處的元素交換。完成後，陣列前 1 個元素已排序。
3. 選取區間 $[1, n-1]$ 中的最小元素，將其與索引 $1$ 處的元素交換。完成後，陣列前 2 個元素已排序。
4. 以此類推。經過 $n - 1$ 輪選擇與交換後，陣列前 $n - 1$ 個元素已排序。
5. 僅剩的一個元素必定是最大元素，無須排序，因此陣列排序完成。

第1步

第2步

第3步

第4步

第5步

第6步

第7步

第8步

第9步

第10步

第11步

示例程式碼

def selection_sort(nums: list[int]):
    """選擇排序"""
    n = len(nums)
    ## 外迴圈：未排序區間為 [i, n-1]
    for i in range(n - 1):
        ## 內迴圈：找到未排序區間內的最小元素
        k = i
        for j in range(i + 1, n):
            if nums[j] < nums[k]:
                k = j  ## 記錄最小元素的索引
        ## 將該最小元素與未排序區間的首個元素交換
        nums[i], nums[k] = nums[k], nums[i]

三、插入排序

插入排序（insertion sort）是一種簡單的排序演算法，它的工作原理與手動整理一副牌的過程非常相似。

具體來說，我們在未排序區間選擇一個基準元素，將該元素與其左側已排序區間的元素逐一比較大小，並將該元素插入到正確的位置。

下圖展示了陣列插入元素的操作流程。設基準元素為 base ，我們需要將從目標索引到 base 之間的所有元素向右移動一位，然後將 base 賦值給目標索引。

演算法流程

插入排序的整體流程如下圖所示。

1. 初始狀態下，陣列的第 1 個元素已完成排序。
2. 選取陣列的第 2 個元素作為 base ，將其插入到正確位置後，陣列的前 2 個元素已排序。
3. 選取第 3 個元素作為 base ，將其插入到正確位置後，陣列的前 3 個元素已排序。
4. 以此類推，在最後一輪中，選取最後一個元素作為 base ，將其插入到正確位置後，所有元素均已排序。

示例程式碼

def insertion_sort(nums: list[int]):
    """插入排序"""
    ## 外迴圈：已排序區間為 [0, i-1]
    for i in range(1, len(nums)):
        base = nums[i]
        j = i - 1
        ## 內迴圈：將 base 插入到已排序區間 [0, i-1] 中的正確位置
        while j >= 0 and nums[j] > base:
            nums[j + 1] = nums[j]  ## 將 nums[j] 向右移動一位
            j -= 1
        nums[j + 1] = base  ## 將 base 賦值到正確位置