定義
選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)。如果某個(gè)元素位于正確的最終位置上，則它不會(huì)被移動(dòng)。選擇排序每次交換一對元素，它們當(dāng)中至少有一個(gè)將被移到其最終位置上，因此對n個(gè)元素的表進(jìn)行排序總共進(jìn)行至多n-1次交換。在所有的完全依靠交換去移動(dòng)元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N。
算法步驟
- 首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?。
- 再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。
- 重復(fù)第二步，直到所有元素均排序完畢。
動(dòng)圖分析
過程分析
這六個(gè)數(shù)組成的無序序列[5,9,3,6,2,7]，由小到大排序。
按照選擇排序算法，過程如下：
-
第一次選擇，找到最小值2，和第一個(gè)數(shù)字交換，第一次結(jié)果為：[2,9,3,6,5,7]
-
第二次選擇，由于數(shù)組第一個(gè)位置已經(jīng)是有序的，所以只需要查找剩余位置，找到其中最小的數(shù)字3，然后和數(shù)組第二個(gè)位置的元素交換，第二次結(jié)果為：[2,3,9,6,5,7]
-
第三次選擇，找到最小數(shù)5，然后和數(shù)組第三個(gè)位置的元素進(jìn)行交換，第三次結(jié)果為：[2,3,5,6,9,7]
-
第四次選擇，找到最小數(shù)6，由于6就在第四個(gè)位置，自己和自己交換位置，第四次結(jié)果為：[2,3,5,6,9,7]
-
第五次選擇，找到最小數(shù)7，和數(shù)組第五個(gè)位置元素進(jìn)行交換，第五次結(jié)果為：[2,3,5,6,7,9]
-
最后一個(gè)到達(dá)了數(shù)組末尾，沒有可對比的元素，結(jié)束選擇。
python實(shí)現(xiàn)選擇排序
def selection_sort(arr):
n = len(arr)
# 交換次數(shù)
count_swap = 0
# 循環(huán)次數(shù)
count_iter = 0
# 需要進(jìn)行n-1次選擇
for i in range(n - 1):
# 記錄最小數(shù)位置
min_index = i
# 從i+1位置到末尾選擇出最小的數(shù)字
for j in range(i+1, n):
count_iter += 1
if arr[j] < arr[min_index]:
min_index = j
# 如果位置不對，進(jìn)行交換
if min_index != i:
arr[i], arr[min_index] = arr[min_index], arr[i]
count_swap += 1
print("第{}次選擇排序結(jié)果為：{}".format(i+1, arr))
print("選擇排序交換次數(shù)為：{}".format(count_swap))
print("選擇排序循環(huán)次數(shù)為：{}".format(count_iter))
return arr
if __name__ == '__main__':
arr = [5, 9, 3, 6, 2, 7]
print(selection_sort(arr))
結(jié)果：
第1次選擇排序結(jié)果為：[2, 9, 3, 6, 5, 7]
第2次選擇排序結(jié)果為：[2, 3, 9, 6, 5, 7]
第3次選擇排序結(jié)果為：[2, 3, 5, 6, 9, 7]
第4次選擇排序結(jié)果為：[2, 3, 5, 6, 9, 7]
第5次選擇排序結(jié)果為：[2, 3, 5, 6, 7, 9]
選擇排序交換次數(shù)為：4
選擇排序循環(huán)次數(shù)為：15
[2, 3, 5, 6, 7, 9]
選擇排序優(yōu)化（二元選擇排序）
優(yōu)化思路：既然我們能一次找到最小值，那么最大值肯定也能找到，同時(shí)確定最大、最小值，減少迭代次數(shù)，達(dá)到優(yōu)化目的。
代碼實(shí)現(xiàn)：
def selection_sort(arr):
n = len(arr)
# 交換次數(shù)
count_swap = 0
# 循環(huán)次數(shù)
count_iter = 0
# 一次確定兩個(gè)值，減半
for i in range(n // 2):
# 記錄最小值位置
min_index = i
# 記錄最大值位置,負(fù)索引
max_index = -i - 1
# 記錄原始最大值位置
maxorigin = max_index
# 每次左邊 +1 向右邊走， 右邊也需要 +1 向左走
for j in range(i+1, n - i):
count_iter += 1
if arr[min_index] > arr[j]:
min_index = j
if arr[max_index] < arr[-j -1]:
max_index = -j -1
# 如果最大和最小值相等，剩下的數(shù)據(jù)一定是重復(fù)的，不需要比較
if arr[max_index] == arr[min_index]:
break
# 如果位置不對，進(jìn)行交換
if i != min_index:
arr[i], arr[min_index] = arr[min_index], arr[i]
count_swap += 1
# 如果最大值被交換過，更新索引
if i == max_index or i == n + max_index:
max_index = min_index
if maxorigin != max_index:
arr[maxorigin], arr[max_index] = arr[max_index], arr[maxorigin]
count_swap += 1
print("第{}次選擇排序結(jié)果為：{}".format(i+1, arr))
print("選擇排序交換次數(shù)為：{}".format(count_swap))
print("選擇排序循環(huán)次數(shù)為：{}".format(count_iter))
return arr
if __name__ == '__main__':
arr = [5, 9, 3, 6, 2, 7]
print(selection_sort(arr))
結(jié)果：
第1次選擇排序結(jié)果為：[2, 7, 3, 6, 5, 9]
第2次選擇排序結(jié)果為：[2, 3, 5, 6, 7, 9]
第3次選擇排序結(jié)果為：[2, 3, 5, 6, 7, 9]
選擇排序交換次數(shù)為：4
選擇排序循環(huán)次數(shù)為：9
[2, 3, 5, 6, 7, 9]
時(shí)間復(fù)雜度
- 最優(yōu)時(shí)間復(fù)雜度：O(n^2)
- 最壞時(shí)間復(fù)雜度：O(n^2)
穩(wěn)定性
考慮升序每次選擇最大的情況，所以選擇排序是不穩(wěn)定排序算法
