文章目錄
- 1.冒泡排序
- （1）基本邏輯
- （2）算法解析
- （3）完整版算法
- 1.從左向右比較，找最大值
- 2.從左向右比較，找最小值
- 3.優化方案
- （3）時間復雜度
- （4）冒泡排序的圖形演示：
- 2.選擇排序
- （1）基本邏輯
- （2）算法分步解析
- 1.從最左邊找最小值的索引
- 2.從最右邊找最大值的索引
- （3）完整算法
- 1.從左到右查找
- 2.從右向左查找
- （4）時間復雜度
- （5）選擇排序演練
1.冒泡排序
（1）基本邏輯
冒泡排序（英語：Bubble Sort）是一種簡單的排序算法。它重復地遍歷要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。遍歷數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。
冒泡排序算法的運作如下：
- 從左到右，依次比較相鄰的元素。如果第一個比第二個大（升序），就交換他們兩個。
- 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最右邊的元素肯定是所有數據里面的值最大的，對應的位置為（n-1）
- 除了最右邊的一個元素，我們再針對其他所有的元素重復以上的步驟。再循環1次，我們就能找到所有元素里面第二大的數字了，排在倒數第二個位置（n-2）
- 持續如上的操作，在我們排序n-1次的時候，就能確定n-1個元素的具體位置，剩余一個元素也肯定是最小的了。此時排序確定的元素的索引為1
如下的數據，我們從左到右開始，先將相鄰的兩個元素比較，依次往右邊移動比較，最終能找到所有數據里面最大的，如下圖所示：
- 每一次需要比較的總次數，按照如下列表展示：
（2）算法解析
- 第一輪排序，找到最大值的位置需要排列到索引為n-1的位置（n為所有元素的數量）。
- 下一輪，我們就可以從索引為0開始，直到n-2之間做相鄰2個比較了
- 最后一輪是index=1的元素，比較n-1次，就你能確定n個元素的排序位置了
# 如果我們只比較一輪，把最大的值放到列表最右邊，可以如下方式
n
=
len
(
mylist
)
for
i
in
range
(
n
-
1
)
:
if
mylist
[
i
]
>
mylist
[
i
+
1
]
:
mylist
[
i
]
,
mylist
[
i
+
1
]
=
mylist
[
i
+
1
]
,
mylist
[
i
]
# 比較是從左向右開始比較的，但是最大值是放在最右邊的
（3）完整版算法
1.從左向右比較，找最大值
def
bubble_sort
(
myList
)
:
n
=
len
(
myList
)
for
j
in
range
(
n
-
1
,
0
,
-
1
)
:
# 代表從最后一個元素向左到第二個元素，不包含index=0
for
i
in
range
(
j
)
:
# j代表其他需要比較的元素的索引，數量逐步減少
if
myList
[
i
]
>
myList
[
i
+
1
]
:
myList
[
i
]
,
myList
[
i
+
1
]
=
myList
[
i
+
1
]
,
myList
[
i
]
myList
=
[
54
,
26
,
93
,
17
,
77
,
31
,
44
,
55
,
20
]
bubble_sort
(
myList
)
print
(
myList
)
# [17, 20, 26, 31, 44, 54, 55, 77, 93]
最外面循環，代表找到每輪最大值的索引，從最右邊，一直正數第二個元素，對應range（n-1， 0， -1）
里面循環，代表從第一個元素，到最大元素前面的那個元素，所以用rang（0， j）表示
2.從左向右比較，找最小值
def
maoPao_min
(
alist
)
:
n
=
len
(
alist
)
for
i
in
range
(
0
,
n
-
1
)
:
for
j
in
range
(
i
+
1
,
n
)
:
if
alist
[
i
]
>
alist
[
j
]
:
alist
[
j
]
,
alist
[
i
]
=
alist
[
i
]
,
alist
[
j
]
# [17, 20, 26, 31, 44, 54, 55, 77, 93]
3.優化方案
def
maoPao_min
(
alist
)
:
n
=
len
(
alist
)
for
i
in
range
(
0
,
n
-
1
)
:
isSorted
=
False
for
j
in
range
(
i
+
1
,
n
)
:
if
alist
[
i
]
>
alist
[
j
]
:
alist
[
j
]
,
alist
[
i
]
=
alist
[
i
]
,
alist
[
j
]
isSorted
=
True
print
(
"every time "
,
alist
)
if
not
isSorted
:
break
print
(
"result"
,
alist
)
myList
=
[
17
,
19
,
21
,
44
,
54
,
93
]
maoPao_min
(
myList
)
# every time [17, 19, 21, 44, 54, 93]
# result [17, 19, 21, 44, 54, 93]
當排序到某個位置的時候，后面的所有其他元素排序都排好了。那么循環的話，一次都不需要置換元素，這種情況我們可以做個判斷，直接跳過所有循環即可
（3）時間復雜度
- 最優時間復雜度：O(n) （表示遍歷一次發現沒有任何可以交換的元素，排序結束。）
- 最壞時間復雜度：O(n2)
- 穩定性：穩定
（4）冒泡排序的圖形演示：
2.選擇排序
（1）基本邏輯
選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理如下：
- 首先，假設最左邊元素為最小值(min_index = 0)
- 其次，假設的最小值和其他元素比較，從左到右，相鄰2個元素依次比較大小，最終找到最小值的索引
- 然后，判斷假設的最小值的索引是否與真實的最小值的索引一樣，不一樣就直接互換元素的位置，這樣第一次循環就確定了所有元素中最小值的位置
- 最后，緊接著假設min_index = 1,依次重復如上步驟，找到其余元素中的最小值，直到假設的最小索引為倒數第二個元素的索引為止（倒數第二個與最后一個比較一次就結束了）
選擇排序的主要優點:
- 每次循環一遍，比較完所有元素之后，找到最小（大）值之后，才會互換位置，否者不會互換位置
- 如果某個元素位于正確的最終位置上，則它不會被移動
- 如果列表為n個元素，那么所有元素最多進行n-1次交換（每個元素都換到非自己本身的位置）
- 如果所有元素都需要移動位置，選擇排序屬于非常好的一種
下圖是每次找到最小值的索引，然后替換：
如下圖是每次找到一個最大值的索引，然后替換：
（2）算法分步解析
1.從最左邊找最小值的索引
alist
=
[
54
,
226
,
93
,
17
,
77
,
31
,
44
,
55
,
20
]
def
choiceSort
(
alist
)
:
n
=
len
(
alist
)
min_index
=
0
# 假設最左邊為最小值
for
i
in
range
(
1
,
n
)
:
# 需要拿最小索引右邊的所有元素與假設的比較
if
alist
[
min_index
]
>
alist
[
i
]
:
min_index
=
i
if
min_index
!=
0
:
alist
[
min_index
]
,
alist
[
0
]
=
alist
[
0
]
,
alist
[
min_index
]
choiceSort
(
alist
)
print
(
alist
)
# result [17, 226, 93, 54, 77, 31, 44, 55, 20]
2.從最右邊找最大值的索引
alist
=
[
54
,
226
,
93
,
17
,
77
,
31
,
44
,
55
,
20
]
def
choiceSort
(
alist
)
:
n
=
len
(
alist
)
max_index
=
n
-
1
# 假設最右邊為最大值的索引
for
i
in
range
(
n
-
2
,
-
1
,
-
1
)
:
# 需要拿倒數第二個索引，從右向左比較，直到第一個索引
if
alist
[
max_index
]
<
alist
[
i
]
:
max_index
=
i
if
max_index
!=
n
-
1
:
alist
[
max_index
]
,
alist
[
n
-
1
]
=
alist
[
n
-
1
]
,
alist
[
max_index
]
choiceSort
(
alist
)
print
(
alist
)
# result [54, 20, 93, 17, 77, 31, 44, 55, 226]
注意點：
- 從左到右找的時候，第二個索引到最后一個索引的表達式：range（2，n-1）
- 從右向左找的時候，倒數第二個索引，到正數第一個索引的表達式：range（n-2，-1，-1）
（3）完整算法
1.從左到右查找
def
selection_sort
(
alist
)
:
n
=
len
(
alist
)
# 需要進行n-1次選擇操作
for
i
in
range
(
n
-
1
)
:
min_index
=
i
# 記錄最小位置
for
j
in
range
(
i
+
1
,
n
)
:
# 從i+1位置到末尾選擇出最小數據
if
alist
[
j
]
<
alist
[
min_index
]
:
min_index
=
j
if
min_index
!=
i
:
alist
[
i
]
,
alist
[
min_index
]
=
alist
[
min_index
]
,
alist
[
i
]
alist
=
[
54
,
226
,
93
,
17
,
77
,
31
,
44
,
55
,
20
]
selection_sort
(
alist
)
print
(
alist
)
# [17, 20, 31, 44, 54, 55, 77, 93, 226]
2.從右向左查找
def
selection_sort
(
alist
)
:
n
=
len
(
alist
)
# 需要進行n-1次選擇操作
for
i
in
range
(
n
-
1
,
0
,
-
1
)
:
max_index
=
i
# 記錄最大值的索引
for
j
in
range
(
i
-
1
,
-
1
,
-
1
)
:
# 從i-1位置到起始位置選擇出最大值索引
if
alist
[
j
]
>
alist
[
max_index
]
:
max_index
=
j
# 如果選擇出的數據不在正確位置，進行交換
if
max_index
!=
i
:
alist
[
i
]
,
alist
[
max_index
]
=
alist
[
max_index
]
,
alist
[
i
]
selection_sort
(
alist
)
print
(
alist
)
# [17, 20, 31, 44, 54, 55, 77, 93, 226]
注意點：
從左到右假設最小值索引的時候：0--------n-2， 對應range(n-1)，到倒數第二個元素
此時，需要與其比較的其他數據的索引為：0+1------------n-1，對應的range（1， n）從第二個元素到最后一個元素
從右向左排序的時候，假設最右邊為最大值索引，n-1----------1，對應range(n-1, 0, -1)
此時，需要比較的其他元素的索引為：n-2--------0,對應的range(n-2, -1, -1)
（4）時間復雜度
- 最優時間復雜度：O(n2)
- 最壞時間復雜度：O(n2)
- 穩定性：不穩定（考慮升序每次選擇最大的情況）
（5）選擇排序演練
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
