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