文章目錄
- 一、排序算法與時間複雜度
- 二、冒泡排序
一、排序算法與時間複雜度
1、十大排序算法
排序算法可以分為内部排序和外部排序，内部排序是資料記錄在記憶體中進行排序，而外部排序是因排序的資料很大，一次不能容納全部的排序記錄，在排序過程中需要通路外存。常見的内部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。用一張圖概括：
2、時間複雜度
- 平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。
- 線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸并排序；
- O(n1+§)) 排序，§ 是介于 0 和 1 之間的常數。希爾排序
- 線性階 (O(n)) 排序 基數排序，此外還有桶、箱排序。
3、排序的穩定性
- 排序後 2 個相等鍵值的順序和排序之前它們的順序相同
- 穩定的排序算法：冒泡排序、插入排序、歸并排序和基數排序。
- 不是穩定的排序算法：選擇排序、快速排序、希爾排序、堆排序。
4、名詞解釋
n：資料規模
k：“桶”的個數
In-place：占用常數記憶體，不占用額外記憶體
Out-place：占用額外記憶體
二、冒泡排序
1、冒泡介紹
冒泡排序（Bubble Sort）也是一種簡單直覺的排序算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。
作為最簡單的排序算法之一，冒泡排序就像 Abandon 在單詞書裡出現的感覺一樣，每次都在第一頁第一位，是以最熟悉。冒泡排序還有一種優化算法，就是立一個 flag，當在一趟序列周遊中元素沒有發生交換，則證明該序列已經有序。但這種改進對于提升性能來說并沒有什麼太大作用。
2、算法步驟
- 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
- 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大的數。
- 針對所有的元素重複以上的步驟，除了最後一個。
- 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。
3、動圖示範
def bubbleSort(arr):
for i in range(1, len(arr)): # 第一層周遊每個數字
for j in range(0, len(arr)-i): # 第二層用第一層選中的數字來和其他數字進行比較
if arr[j] > arr[j+1]: # 滿足條件，則交換順序
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
a = [3,5,15,2,26,27,4,19,36,47,28,50,19,48,44]
bubbleSort(a)
print(a)