1.冒泡排序
1.1算法思想
冒泡排序是一種簡單的排序算法。通過重復地遍歷要排序的數列,一次比較兩個元素,從最開始的一對到最后的一對(相當于一個長度為2的滑動窗口),如果它們的順序錯誤(看從小到達排列還是從大到小排列)就把它們交換過來。如果是升序排列的話,每次遍歷都會把最大值交換到最右邊。然后重復這個過程,直到沒有再需要交換,也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頭部,就像冒泡一樣。
這個算法不需要額外的空間,空間復雜度為o(1),同時對n個數據要進行n-1次比較,才能將最大的數固定在數列尾部,所以要固定好n個數,需要進行(n-1)+(n-2)+……+1+0次操作,時間復雜度為o(n^2)
1.2算法過程
- 比較相鄰的元素。如果第一個比第二個大,就交換它們兩個;
- 對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最后一對,這樣在最后的元素應該會是最大的數;
- 針對所有的元素重復以上的步驟,除了最后一個;
- 重復步驟1~3,直到排序完成。
1.3 python實現
def
bubbleSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
for
i
in
range
(
n
)
:
# i在這里起到一個類似于計數的作用,看目前有多少個數排好序了
for
j
in
range
(
n
-
i
-
1
)
:
# 由于目前數組中,有i+1個數已經固定到數組尾部,因此只要對前n-i-1對數進行比較即可
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
)
)
# 輸出結果為 :[1, 2, 3, 3, 5, 6, 6, 7, 10]
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
