Python選擇排序的步驟與優(yōu)化方法
選擇排序（Selection Sort）是一種簡(jiǎn)單直觀的排序算法。它的基本思想是每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，存放在序列的起始位置，然后再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（或最大）的元素，放到已排序序列的末尾。重復(fù)這個(gè)過(guò)程，直到全部待排序的數(shù)據(jù)元素排完為止。
選擇排序的步驟可以總結(jié)如下：
-
遍歷待排序的序列，標(biāo)記當(dāng)前位置為最小元素的位置。
從標(biāo)記的位置后面的元素中找到一個(gè)比當(dāng)前最小元素還要小的元素，并更新標(biāo)記位置。
將標(biāo)記位置的元素與最小元素位置的元素進(jìn)行交換。
以標(biāo)記位置后面的元素為新的起始位置，重復(fù)步驟2和步驟3。
選擇排序的優(yōu)化方法有：
-
在每次遍歷時(shí)，同時(shí)找到最小元素和最大元素，并同時(shí)進(jìn)行交換。這樣可以減少交換次數(shù)，提高排序效率。
加入一個(gè)判斷，如果遍歷過(guò)程中沒(méi)有發(fā)生交換，即已經(jīng)完成排序，則提前終止排序過(guò)程。
下面是Python中的選擇排序代碼示例：
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_pos = i
max_pos = i
for j in range(i + 1, n):
if arr[j] arr[max_pos]:
max_pos = j
if min_pos != i:
arr[i], arr[min_pos] = arr[min_pos], arr[i]
if max_pos == i:
max_pos = min_pos
if max_pos != n - 1 - i:
arr[n - 1 - i], arr[max_pos] = arr[max_pos], arr[n - 1 - i]
if min_pos == n - 1 - i:
min_pos = max_pos
if min_pos != i:
arr[i], arr[min_pos] = arr[min_pos], arr[i]
return arr
# 測(cè)試
arr = [64, 25, 12, 22, 11]
print("排序前:", arr)
sorted_arr = selection_sort(arr)
print("排序后:", sorted_arr)
登錄后復(fù)制
以上代碼中，我們使用變量 min_pos 記錄最小元素的位置，使用變量 max_pos 記錄最大元素的位置。在每次遍歷中，通過(guò)比較更新這兩個(gè)位置，然后進(jìn)行交換。在列表長(zhǎng)度為奇數(shù)時(shí)，如果 min_pos 和 max_pos 的位置剛好重合于起始位置，我們需要對(duì)交換后的位置進(jìn)行檢查和處理。
