Python中的選擇排序算法詳解
選擇排序是一種簡單但效率較低的排序算法，它的基本思想是每次從待排序的序列中找出最小（或最大）的元素，放到已排序序列的末尾。通過重復這個過程，直到所有元素都排序完畢。
選擇排序的步驟如下：
-
遍歷序列，找到最小（或最大）的元素。
將最小（或最大）的元素與當前遍歷位置的元素交換。
重復步驟1和步驟2，直到遍歷完整個序列。
下面我們來詳細解釋一下選擇排序算法，并給出具體的代碼示例。
首先，我們定義一個函數來實現選擇排序：
def selection_sort(arr):
n = len(arr)
for i in range(n):
# 找到未排序序列中的最小元素的索引
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
# 將最小元素與當前遍歷位置的元素交換
arr[i], arr[min_index] = arr[min_index], arr[i]
登錄后復制
現在，我們來測試一下選擇排序的效果：
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("排序后的數組:")
for i in range(len(arr)):
print(arr[i])
登錄后復制
運行上面的代碼，輸出結果如下：
排序后的數組: 11 12 22 25 64
登錄后復制
可以看到，選擇排序成功將數組按照升序排列。
選擇排序的時間復雜度為O(n^2)，其中n為待排序序列的長度。這是因為每次需要遍歷未排序序列中的所有元素來找到最小（或最大）的元素，需要執行n次比較。總共需要執行n-1輪遍歷，所以時間復雜度為O(n^2)。
選擇排序是一種不穩定的排序算法，即相同元素的相對順序可能會發生改變。這是因為選擇排序是通過不斷交換元素位置來實現的。例如，對于序列[3, 1, 3]，使用選擇排序算法排序后可能結果為[1, 3, 3]，原本相同的元素3的相對位置發生了改變。
雖然選擇排序的效率較低，但它的實現簡單直觀。在某些特定情況下，例如待排序序列的規模較小，或者對穩定性要求不高時，選擇排序可以作為一種簡單的排序方法。
總結起來，選擇排序是一種通過不斷找到未排序序列中的最小（或最大）元素，將其與當前遍歷位置的元素交換來完成排序的算法。雖然實現簡單，但時間復雜度較高，且不穩定。在實際應用中，選擇排序的使用場景較為有限。
