選擇排序基本資訊

選擇排序是一種排序演算法，特別是就地比較排序。它具有 O(n2) 時間複雜度，使其在大型列表上效率低下，並且通常比類似的插入排序更差。選擇排序因其簡單性而著稱，並且在某些情況下具有優於更復雜演算法的效能優勢，特別是在輔助儲存器有限的情況下。

該演算法將輸入列表分為兩部分：已經排序的專案子列表，在列表的前面（左側）從左到右構建，以及剩餘要排序的專案的子列表佔用其餘部分。名單。最初，排序的子列表為空，未排序的子列表是整個輸入列表。該演算法通過查詢未排序子列表中的最小（或最大，取決於排序順序）元素，與最左邊的未排序元素（將其按排序順序）交換（交換），並將子列表邊界向右移動一個元素來繼續。

選擇排序的虛擬碼：

function select(list[1..n], k)
 for i from 1 to k
     minIndex = i
     minValue = list[i]
     for j from i+1 to n
         if list[j] < minValue
             minIndex = j
             minValue = list[j]
     swap list[i] and list[minIndex]
 return list[k]

選擇排序的視覺化：

https://i.stack.imgur.com/LZepY.gif

選擇排序示例：

https://i.stack.imgur.com/CaSlf.jpg

輔助空間： O(n)
時間複雜度： O(n^2)