常見的排序算法
- 冒泡排序（Bubble Sort）
- 選擇排序（Selection Sort）
- 插入排序（Insertion Sort）
- 快速排序（Quick Sort）
- 希爾排序 (Shell Sort）
- 歸并排序 (Merge Sort)
冒泡算法的思想
冒泡排序算法的運作如下：
- 比較相鄰的元素男公。如果第一個比第二個大（升序）弃衍，就交換他們兩個瑰排。
- 對每一對相鄰元素作同樣的工作断凶，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。
- 針對所有的元素重復以上的步驟群嗤，除了最后一個。
- 持續(xù)每次對越來越少的元素重復上面的步驟兵琳，直到?jīng)]有任何一對數(shù)字需要比較狂秘。
下面來用python實現(xiàn)冒泡排序
#_*_coding:utf-8_*_
def bubble_sort(a):
#a is a list
if not a:
return
length = len(a)
for i in range(0, length - 1):
for j in range(0, length - i -1):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1],a[j]
if __name__ == '__main__':
list1 = [34,12,1,8,9,19,12]
print(list1)
bubble_sort(list1)
print(list1)
分析一下上面的程序可以得出：
1.時間復雜度O(n^2)
- 如果原來的序列本來就是有序的話，如果按照上述算法躯肌，時間復雜度依舊是O(n^2), 對此可以進行算法優(yōu)化者春，可以加入內(nèi)循環(huán)計數(shù)器用來記錄交換的次數(shù)，如果內(nèi)循環(huán)計數(shù)器始終為零清女，則表示該數(shù)列是有序的钱烟，就不用進行外循環(huán)了，算法復雜度可以O（n）
優(yōu)化算法實現(xiàn)為:
#_*_coding:utf-8_*_
def bubble_sort(a):
#a is a list
if not a:
return
length = len(a)
for i in range(0, length - 1):
**count = 0**
for j in range(0, length - i -1):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1],a[j]
**count += 1**
**if count == 0:
return**
if __name__ == '__main__':
#list1 = [34,12,1,8,9,19,12]
list1 = [1,2,3,4,5]
print(list1)
bubble_sort(list1)
print(list1)
冒泡算法時間復雜度總結(jié)
- 最優(yōu)時間復雜度：O(n) （表示遍歷一次發(fā)現(xiàn)沒有任何可以交換的元素，排序結(jié)束拴袭。）
- 最壞時間復雜度：O(n2)
- 穩(wěn)定性：穩(wěn)定
