選擇排序

今天我們來聊一下同樣比較基礎的排序算法-選擇排序。選擇排序是一種非常直觀的排序算法，復雜度為 $O(n^2)$，和前面介紹的兩種算法一樣不需要額外的空間。

1. 選擇排序算法原理

選擇排序的思路是最容易想到的：首先遍歷一次列表，找到列表中的最小值，交換到第一個位置； 接下來從第二個位置開始遍歷列表，找到最小值，交換到第二個位置上。如此執行下去，直到遍歷操作走最后一位上時停止。此時，列表已經完成排序。

2. 選擇排序算法過程分析

從上面的算法過程可以看到，該算法的時間復雜度是比較固定的，每次遍歷都是比較剩余所有數據，因此其時間復雜度（包括最好、最壞情況和平均）均為 $O(n^2)$；而空間復雜度則為 $O(1)$，我們只需要一個臨時變量保存每次遍歷的最小值即可。下面來看一個選擇排序的一個示例圖：

算法的過程差不多已經理清楚了，接下來我們實現這樣的排序算法，同樣會分成兩種數據結構的實現：數組和鏈表。

2. 選擇排序的 Python 實現

2.1 數組版的選擇排序

對于數組版的選擇排序，實現的代碼如下：

def choose_sort(nums):
    """
    選擇排序
    """
    for i in range(len(nums) - 1):
        min_val = nums[i]
        # 標記最小值位置
        k = i
        for j in range(i + 1, len(nums)):
            # 每次遍歷，找到本輪剩余元素的最小值，同時記錄相應位置
            if nums[j] < min_val:
                min_val = nums[j]
                k = j
        # 每次遍歷數組后找到最小值，交換當前位置與本輪最小值的位置
        if k != i:
            nums[i], nums[k] = nums[k], nums[i]

2.2 鏈表版的選擇排序

同樣，對于鏈表版的選擇排序，我們需要用示意圖來描述下這個選擇排序的過程，這樣才能更好幫助我們實現代碼。

依據上面的示意圖，我們給出如下鏈表的選擇排序方法。其中，各個變量的說明在示意圖中已有體現，且代碼中也給出了部分注釋，幫助大家更好理解算法過程。

def choose_sort_link(head):
    """
    排序鏈表
    """
    first = head
    while first.next:
        p = first
        min_val = p.val
        # 指向最小節點的位置
        k = p
        while p:
            if p.val < min_val:
                min_val = p.val
                k = p
            p = p.next
        # 交換最小位置和遍歷的起始位置的值
        first.val, k.val = min_val, first.val
        first = first.next 
    return head

這個對鏈表排序的題目在 leetcode 上也是有的，題號為148。我使用該代碼進行了測試，發現無法通過最后得測試，這并非代碼實現問題，而是題目本身的效率要求。后續讀者可以使用其他排序算法來完成對鏈表的排序，通過該題題解。

3. 小結

今天的內容比較簡單，選擇排序在理解上比冒泡排序還要直觀和簡單，同樣前三節排序算法的平均時間復雜度都是 $O(n^2)$，后面我們會介紹兩類非常經典和高效的排序算法，尤其是快速排序算法，幾乎代表了排序算法中的最優解，也是各個筆試和面試?？嫉闹R點。

Tips：文中動圖制作參考：https://visualgo.net/zh/sorting。