冒泡排序

  首先必須講冒泡排序，作為面試官最常出的最簡單題型，可見其重要性和普及性。冒泡排序顧名思義，就是一組排序列表，從頭到尾兩兩比較，大的排在後方，代碼如下：

def bubble_sort(l):
 for i in range(len(l),-1,-1): #從後往前遍歷，這樣可以不用再對最後已排好序的重新排序
 for j in range(1,i): #從前往後，末尾是i，也就是還未還排好序的
 if l[j-1] > l[j]: #如果前面大，就和後面的調換順序
 l[j-1],l[j] = l[j],l[j-1]
 return l

可以看到用Python寫出的冒泡排序僅僅6行就解決了，並且代碼非常的簡單，但這裡有個缺點，也就是無論是最好情況還是最壞情況都是O(n^2)的時間複雜度，那實際上可以這樣優化。如果是最好情況，也就是數組本身已經排好序的話，那表示未交換過，所以通過標誌位來標記當一輪排序通過後未交換過，則說明已經排好序即可。優化後的代碼：

def bubble_sort(l):
 for i in range(len(l),-1,-1):
 flag = 1 #每次新一輪開始就增加標誌位
 for j in range(1,i):
 if l[j-1] > l[j]:
 l[j-1],l[j] = l[j],l[j-1]
 flag = 0 #如果交換則標誌位為0
 if flag == 1: #判斷標誌位決定是否有必要繼續往下遍歷
 return l
 return l

那分析下時間複雜度和空間複雜度！因為排序都是在數組裡進行交換排序的，所以空間複雜度為O(1)，也就是內存消耗為0(原地排序)；時間複雜度的話最好是比較n-1次，所以為O(N)，最壞則是有序度為0，則為n*(n-1)/2，即O(n2)的時間複雜度。那平均是多少呢？這裡可以用估算的方法，假如以交換來說，最好時是沒有交換，最壞是比較了n*(n-1)/2，所以平均是n*(n-1)/4，那比較肯定比交換要多幾倍，所以最大不會超過O(n2)。另外因為冒泡比較時相等的不會交換，所以其是穩定算法！

嗨嘍：正在學習python的小夥伴或者打算學習的，可以私信小編“01”領取資料！

插入排序

  相比於冒泡排序，插入排序可以說是非常具有實用性的語言，並且現在很多語言還是會利用插入排序作為其排序的一部分來實現！

  插入排序就是從左到右分為兩堆，左邊是排好序的，右邊是待排序的，每次從右邊取一個數依次跟左邊相比較，小於哪個數就排在哪個數前面，直到碰到比它大的數為止！代碼如下：

def insert_sort(l):
\tfor i in range(1,len(l)):
\t\tfor j in range(i,-1,-1): #從左邊的最後一個數開始比較
\t\t\tif l[j-1] > l[j]: #如果比最後一個數小，則排在其前邊
\t\t\t\tl.insert(j-1,l.pop(j))
\t\t\telse: #如果比最後一個數大，則排在其後邊
\t\t\t\tbreak
\treturn l

三個角度分析插入排序，首先沒有開闢空間，所以是原地排序，O(1)的空間複雜度；由於比較時不比較相等的情況，所以相等的情況不會交換位置，即是穩定的排序算法；那時間複雜度呢？最好當然是滿有序度(即排好序的)，則每次比較右邊的都比左邊的大，break出來，則僅需O(n)次比較，最壞是有序度為0，則每次相當於都要比較一遍全數組，即為n*(n+1)/2為O(n2)的時間複雜度，平均來說，相當於每次都是往數組中插入一個數，而往數組中插入一個數為O(n)，所以n個數需要O(n2)的時間複雜度。

選擇排序

  選擇排序作為三大排序中的最基礎，其沒有多少可講，而且因為無論最好、最壞、平均都是O(n2)的時間複雜度，所以我們瞭解即可。

  選擇排序就是每次從左到右選第一個數依次比較到最後，所以即使是有序的，每個數也都要比較n次，那麼n個數就要比較n2的次，即O(n2)時間複雜度，代碼如下：

def choose_sort(l):
\tfor i in range(len(l)):
\t\tfor j in range(i+1,len(l)): #從左邊那個數的後面一個知道最後依次比較
 if l[i] > l[j]: #不斷地比較，把最小的數移到最左邊
 l[i],l[j] = l[j],l[i]
 return l

從三個角度分析，以此類推，則為原地排序，O(1)的空間複雜度；因為未涉及相等的判斷，所以是穩定性排序，而時間複雜度則最好、最好、平均都是O(n2)。

快速排序

  快速排序簡稱快排，可以說是面試官最喜歡考得排序算法之一了！和冒泡並列，而相對於冒泡，快速排序的思想要更好得多！

最後多說一句，小編是一名python開發工程師，這裡有我自己整理了一套最新的python系統學習教程，包括從基礎的python腳本到web開發、爬蟲、數據分析、數據可視化、機器學習等。想要這些資料的可以關注小編，並在後臺私信小編：“01”即可領取！