Python中的選擇排序算法詳解

選擇排序是一種簡單但效率較低的排序算法，它的基本思想是每次從待排序的序列中找出最小（或最大）的元素，放到已排序序列的末尾。通過重復(fù)這個過程，直到所有元素都排序完畢。

選擇排序的步驟如下：

下面我們來詳細(xì)解釋一下選擇排序算法，并給出具體的代碼示例。

首先，我們定義一個函數(shù)來實現(xiàn)選擇排序：

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
        
        # 將最小元素與當(dāng)前遍歷位置的元素交換
        arr[i], arr[min_index] = arr[min_index], arr[i]

現(xiàn)在，我們來測試一下選擇排序的效果：

arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("排序后的數(shù)組:")
for i in range(len(arr)):
    print(arr[i])

運行上面的代碼，輸出結(jié)果如下：

排序后的數(shù)組:
11
12
22
25
64

可以看到，選擇排序成功將數(shù)組按照升序排列。

選擇排序的時間復(fù)雜度為O(n^2)，其中n為待排序序列的長度。這是因為每次需要遍歷未排序序列中的所有元素來找到最小（或最大）的元素，需要執(zhí)行n次比較。總共需要執(zhí)行n-1輪遍歷，所以時間復(fù)雜度為O(n^2)。

選擇排序是一種不穩(wěn)定的排序算法，即相同元素的相對順序可能會發(fā)生改變。這是因為選擇排序是通過不斷交換元素位置來實現(xiàn)的。例如，對于序列[3, 1, 3]，使用選擇排序算法排序后可能結(jié)果為[1, 3, 3]，原本相同的元素3的相對位置發(fā)生了改變。

雖然選擇排序的效率較低，但它的實現(xiàn)簡單直觀。在某些特定情況下，例如待排序序列的規(guī)模較小，或者對穩(wěn)定性要求不高時，選擇排序可以作為一種簡單的排序方法。

起來，選擇排序是一種通過不斷找到未排序序列中的最小（或最大）元素，將其與當(dāng)前遍歷位置的元素交換來完成排序的算法。雖然實現(xiàn)簡單，但時間復(fù)雜度較高，且不穩(wěn)定。在實際應(yīng)用中，選擇排序的使用場景較為有限。