圖解排序算法及實作——選擇排序（Selection sort）

選擇排序（Selection sort）是一種簡單直覺的排序算法，也叫直接選擇排序。

思路

設 左邊為有序區，右邊亂序區。從右邊剩下的亂序數字中找最小，放到左邊。（反過來也是可以的）

具體操作： 多次比較，一次交換。每次從右邊剩餘數字中選最小，與亂序區最左邊的元素交換，使左邊有序區邊界右移。

複雜度

平均時間複雜度 О(n²)

最壞時間複雜度 О(n²)

最優時間複雜度 О(n²)

圖例

推薦VisuAlgo，一個資料結構和算法動态可視化的網站。

圖檔來源： 【圖解算法】排序算法——冒泡排序、選擇排序

來源：維基百科

python實作

def SelectionSort(arr):
    ''' 
    選擇排序思路：左邊有序區，右邊亂序區。從右邊剩下的亂序數字中找最小，放到左邊。（反過來也是可以的）

    具體操作： 多次比較，一次交換。每次從右邊剩餘數字中選最小，與亂序區最左邊的元素交換，
              使左邊有序區邊界右移。

    複雜度： O(n^2)
    '''
    n = len(arr)

    # arr為空和arr隻有一個元素時，不進入以下循環，不執行任何操作。 
    # 即暗含了邊界檢查： if n==1 or n==0: return lst
    # 以下各Sort()函數同理
    for i in range(n):

        # 多次比較：尋找[i, n-1]區間裡的最小值
        minIndex = i
        for j in range(i+,n):
            if arr[j]<arr[minIndex]:
                minIndex = j

        # 一次交換
        if i != minIndex:
            arr[i],arr[minIndex] = arr[minIndex],arr[i]