一匆背、簡(jiǎn)單選擇排序
1.1 簡(jiǎn)單選擇排序
- 屬于選擇排序
- 兩兩比較大小，找出極值（極大值或極小值）被放置在固定的位置身冀，這個(gè)固定位置一般指的是某一端
- 結(jié)果分為升序和降序排列
1.2 降序
- n 個(gè)數(shù)從左至右钝尸，索引從 0 開始到 n-1，兩兩一次比較搂根，記錄大值索引珍促，此輪所有數(shù)比較完畢，將大數(shù)和索引 0 數(shù)交換剩愧，若大數(shù)就是索引 0猪叙，不交換，第二輪，從 1 開始比較穴翩，找到最大值犬第，將它和索引 1 位置交換，若它就在索引 1 位置則不交換芒帕，以此類推歉嗓，每次左邊都會(huì)固定下一個(gè)大數(shù)
1.3 升序
- 和降序相反
示例.png
1.4 簡(jiǎn)單排序?qū)崿F(xiàn)
nums = [1, 9, 8, 5, 6, 7, 4, 3, 2]
length = len(nums)
for i in range(length):
maxindex = i
for j in range(maxindex + 1, length):
if nums[j] > nums[maxindex]:
maxindex = j
nums[i], nums[maxindex] = nums[maxindex], nums[i]
print(nums)
二、優(yōu)化實(shí)現(xiàn)
2.1 二元選擇排序副签，同時(shí)固定左邊最大值和右邊最小值
- 優(yōu)點(diǎn)
- 減少迭代元素的次數(shù)
-
length//2遥椿，通過幾次運(yùn)算就可發(fā)現(xiàn)規(guī)律 - 由于使用了負(fù)索引，為了計(jì)算方便淆储，所以增加了轉(zhuǎn)換為正索引
nums = [1, 9, 8, 5, 6, 7, 4, 3, 2]
length = len(nums)
for i in range(length // 2):
maxindex = i
minindex = -i -1
minorigin = length + minindex
for j in range(i + 1, length - i): # 每次左右各減少一個(gè)
if nums[j] > nums[maxindex]:
maxindex = j
if nums[-j -1] < nums[minindex]:
minindex = -j -1
else:
minindex = length + minindex # 調(diào)整為正索引
if i != maxindex:
nums[i], nums[maxindex] = nums[maxindex], nums[i]
if i == minindex:
minindex = maxindex # 若最小值交換過冠场，變更索引
if minindex != minorigin:
nums[minorigin], nums[minindex] = nums[minindex], nums[minorigin]
print(nums)
2.2 針對(duì)最大最小值相等優(yōu)化
- 若一輪比較后，極大值本砰、極小值相等碴裙，說明比較的序列元素全部相等，則跳出循環(huán)
nums = [1, 9, 8, 5, 6, 7, 4, 3, 2]
length = len(nums)
for i in range(length // 2):
maxindex = i
minindex = -i -1
minorigin = length + minindex
for j in range(i + 1, length - i): # 每次左右各減少一個(gè)
if nums[j] > nums[maxindex]:
maxindex = j
if nums[-j -1] < nums[minindex]:
minindex = -j -1
if nums[maxindex] == nums[minindex]: # 最大最小值相等点额，跳出循環(huán)
break
minindex = length + minindex # 調(diào)整為正索引
if i != maxindex:
nums[i], nums[maxindex] = nums[maxindex], nums[i]
if i == minindex:
minindex = maxindex # 若最小值交換過舔株，變更索引
if minindex != minorigin:
nums[minorigin], nums[minindex] = nums[minindex], nums[minorigin]
print(nums)
2.3 針對(duì) [1, 1, 1, 1, 2] 優(yōu)化
- 最小值兩個(gè)均為
1，不需交換还棱，針對(duì)此添加一個(gè)判斷進(jìn)行優(yōu)化
nums = [1, 9, 8, 5, 6, 7, 4, 3, 2]
length = len(nums)
for i in range(length // 2):
maxindex = i
minindex = -i -1
minorigin = length + minindex
for j in range(i + 1, length - i): # 每次左右各減少一個(gè)
if nums[j] > nums[maxindex]:
maxindex = j
if nums[-j -1] < nums[minindex]:
minindex = -j -1
if nums[maxindex] == nums[minindex]: # 最大最小值相等载慈，跳出循環(huán)
break
minindex = length + minindex # 調(diào)整為正索引
if i != maxindex:
nums[i], nums[maxindex] = nums[maxindex], nums[i]
if i == minindex:
minindex = maxindex # 若最小值交換過，變更索引
if minindex != minorigin and nums[minorigin] != nums[minindex]: # 索引不同珍手，值相等不需交換
nums[minorigin], nums[minindex] = nums[minindex], nums[minorigin]
print(nums)
三办铡、簡(jiǎn)單選擇排序總結(jié)
- 簡(jiǎn)單選擇排序需要數(shù)據(jù)一輪輪比較，并在每一輪中發(fā)現(xiàn)極值
- 沒有辦法知道當(dāng)前輪是否已經(jīng)達(dá)到排序要求琳要，但是可知道極值是否在目標(biāo)索引位置上
- 遍歷次數(shù)
1,...,n-1之和n(n-1)/2 - 時(shí)間復(fù)雜度
O(n^2) - 減少交換次數(shù)寡具，提高效率，性能略好與冒泡法
