1.冒泡排序
1.1算法思想
冒泡排序是一種簡單的排序算法。通過重復(fù)地遍歷要排序的數(shù)列，一次比較兩個元素，從最開始的一對到最后的一對（相當(dāng)于一個長度為2的滑動窗口），如果它們的順序錯誤（看從小到達(dá)排列還是從大到小排列）就把它們交換過來。如果是升序排列的話，每次遍歷都會把最大值交換到最右邊。然后重復(fù)這個過程，直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因?yàn)樵叫〉脑貢?jīng)由交換慢慢“浮”到數(shù)列的頭部，就像冒泡一樣。
這個算法不需要額外的空間，空間復(fù)雜度為o（1），同時對n個數(shù)據(jù)要進(jìn)行n-1次比較，才能將最大的數(shù)固定在數(shù)列尾部，所以要固定好n個數(shù)，需要進(jìn)行（n-1）+（n-2）+……+1+0次操作，時間復(fù)雜度為o（n^2）
1.2算法過程
- 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
- 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對，這樣在最后的元素應(yīng)該會是最大的數(shù)；
- 針對所有的元素重復(fù)以上的步驟，除了最后一個；
- 重復(fù)步驟1~3，直到排序完成。
1.3 python實(shí)現(xiàn)
def
bubbleSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
for
i
in
range
(
n
)
:
# i在這里起到一個類似于計數(shù)的作用，看目前有多少個數(shù)排好序了
for
j
in
range
(
n
-
i
-
1
)
:
# 由于目前數(shù)組中，有i+1個數(shù)已經(jīng)固定到數(shù)組尾部，因此只要對前n-i-1對數(shù)進(jìn)行比較即可
if
numList
[
j
]
>
numList
[
j
+
1
]
:
temp
=
numList
[
j
]
numList
[
j
]
=
numList
[
j
+
1
]
numList
[
j
+
1
]
=
temp
return
numList
numList
=
[
3
,
10
,
7
,
1
,
3
,
5
,
6
,
2
,
6
]
print
(
bubbleSort
(
numList
)
)
# 輸出結(jié)果為 ：[1, 2, 3, 3, 5, 6, 6, 7, 10]
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
