初學者學演算法｜排序法入門：選擇排序與插入排序法
程式麻瓜的程式知識課（五）
在初學者學演算法系列的第一篇文章中，我們認識了演算法這個玩意兒，也對評斷演算法好壞的工具「時間複雜度」有了基本的概念。而在上一篇文章中，我們了解了簡單的三種演算法：陣列讀取、簡易搜尋與二分搜尋。
在這篇文章中，我們會進階到演算法的經典課：排序法。除了介紹何謂排序法外，我們也會介紹兩個最簡單，擁有 O(n²) 複雜度的排序法：選擇排序法與插入排序法。
目錄：常見的六種時間複雜度與演算法
- O(1)：陣列讀取
- O(n)：簡易搜尋
- O(log n)：二分搜尋
- O(n²)：選擇排序法、插入排序法
- O(n logn)：合併排序法
- O(2^n)：費波那契數列
何謂排序法？
瞭解排序法是學習演算法的必經之路。所謂排序法，就是將一堆沒有排序過的數字由小到大（或大到小）排列好的演算法。把這些排序法視覺化後就會像以下的這個療癒影片：
大致暸解何謂排序法後，就讓我們先來了解最簡單的排序法：有 O(n²) 時間複雜度的選擇排序法！
O(n²)：選擇排序法 (Selection Sort)
時間複雜度為 O(n²) 的演算法，代表著執行步驟會跟著輸入 n 成次方比例的增加。最基礎的排序法之一：選擇排序法(Selection Sort) 是 O(n²) 複雜度的代表。
基本來說，選擇排序只需要重複執行兩個步驟，分別是：
找最小值
- 從「未排序好的數字」中找到最小值
丟到左邊
- 把最小值丟到「未排序好的數字」的最左邊，把它標示成已排序好
假設有一個 [41, 33, 17, 80, 61, 5, 55] 的陣列，我們用圖的例子來一步一步理解選擇排序是如何進行，在下面的圖中，我們把尚未排序好的數字用紅色標示，這輪找到的最小值以橘色標示，排序好的以藍色標示。
在上面的例子中，我們可以看到每一輪中我們會從還沒排序好的所有數字中找到最小的。
按照這個方式，我們可以在第一輪中找到整個陣列中最小的，第二輪找到第二小的，以此類推，把他們依序放到排序好數列的最後面，就可以確保每一個數字都排序正確。
了解了選擇排序進行的過程後，接下來就輪到分析時間複雜度的部分啦！
選擇排序的時間複雜度
觀察選擇排序的時間複雜度，我們同樣把步驟拆成兩個部分討論。
找到最小值
首先我們要先瞭解，從 n 個還沒排序好數字中找到最小值，需要 n 個步驟。
最常見找最小值的方法就是：我們先設陣列的第一個數字是「目前的最小值」，然後往後把陣列的數值一個一個讀取。
如果讀取的下個數比最小值大，就什麼都不用做。而如果讀取到的數比「目前的最小值」小，就把「目前的最小值」換成這個數。重複這個方法把所有陣列裡的數都讀過一遍，就能確保目前的最小值為整個數列的最小值。實際例子如下圖：
知道了找到最小值的步驟後，讓我們觀察一下上面進行的過程。第一個回合要從 7 個數字中找到最小值，需要 7 個步驟。第二個回合則是從 6 個數字中找，需要 6 個步驟，以此類推：如果總共要排序的數字有 n 個，則第一個回合需要 n 個步驟，第二回合需要 n-1 個，一直到最後一個回合需要 1 個步驟為止。
經過神秘數學運算（n+(n-1)+(n-2)+…+1) 後，我們可以得知總共的步驟數等於 n * (n+1) / 2 個步驟。
丟到最左邊
丟到最左邊就相對很好理解，每次找到最小的數字時，我就跟「未排序好的數字」中的第一個數字交換位子，並把它標示成已排序好。這樣每一個回合都剛好只需要 1 個步驟，總共 n 個回合，所以需要 n 個步驟。
結合找到最小值與丟到最左邊
把上面的兩個結果加起來，(n * (n+1) / 2) + n = n * (n+3) / 2。回想一下我們在這篇提到的，時間複雜度只取最高次方項並省略所有係數，因此雖然選擇排序的步驟數是 n * (n+3) / 2，其時間複雜度我們還是會記為 O(n²)。
選擇排序法在程式碼中的例子，對於程式新手可能需要花比較一點點時間理解。如果你是對程式有一定理解的人，可以嘗試動手實做看看（可以想想要如何實作找最小值，接下來再實作選擇排序就會輕鬆很多）。而如果下方的程式碼對於讀者還有些吃力的話，可以先多多熟悉語法後回來複習即可。
Numbers = [41,33,17,80,61,5,55]
length = len(Numbers)
for i in range(length-1):
min_index = i
for j in range(i+1, length):
if Numbers[min_index] > Numbers[j]:
min_index = j
Numbers[min_index], Numbers[i] = Numbers[i], Numbers[min_index]
print(Numbers)O(n²)：插入排序法 (Insertion Sort)
同樣擁有 O(n²) 時間複雜度，插入排序法 Insertion Sort 則是另外一個非常常見的排序法。簡單來說，插入排序法就是你玩撲克牌時用到的排序法。
讀一個數字
- 從「未排序過的數字」中讀取一個數
插入合適位置
- 把這個讀取的數往前插入一個位置
現在，我們重新使用 [41, 33, 17, 80, 61, 5, 55] 的陣列，在下面的圖中，我們把尚未排序過的數字用紅色標示，這輪要插入的值以橘色標示，排序過的以藍色標示。
從上面可以看到，插入排序法的步驟就像我們玩撲克牌在整牌的時候一樣，只是我們在插入排序法時一次只會插入一個數，而撲克牌在整牌的時候我們有時會同時插入兩三張牌。
接下來，讓我們用慢動作再複習一次：
看完插入排序的慢動作後，讓我們一起來分析它的時間複雜度的部分吧！
插入排序的時間複雜度
觀察插入排序法的時間複雜度，我們要同時複習一個在上一篇文章中提到的觀念：
通常程式步驟的時間複雜度會是用程式執行會碰到的最壞狀況 (Worst Case) 來表示
在這邊，我們要用另外一種方法分析時間複雜度：我們分別從排序法會遇到的最佳狀況與最壞狀況來分析。
最佳狀況
排序法遇到的最佳狀況會是什麼呢？直觀地想，如果一個陣列在讀取前就剛好已經排序好了，那麼我們在做排序法時，通常可以花比較少的步驟數。
回想插入排序法的兩個步驟，每一輪的「讀一個數字」我們需要一個步驟（不知道為何需要一個步驟可以回去上一篇中複習陣列讀取），而「插入合適位置」則因為每個數字剛好都在合適位置了，所以不需要再做任何動作。
因此，在最佳狀況，每一輪需要一個步驟，總共要做 n 輪，所以時間複雜度是非常單純的 O(n)。
O(n) 的時間複雜度可說是工程師夢寐以求的美妙設計，然而，我們在前面就先警告過大家了，最壞狀況 (Worst Case) 才是我們計算時間複雜度時最關心的。
最壞狀況
排序法遇到的最壞狀況會是什麼呢？直觀地想，如果我們要將一個陣列由小到大排列，但陣列在我們排序前剛好是由大到小排列時，我們需要花最多的步驟數才能排列好。
再次回想插入排序法的兩個步驟，每一輪的「讀一個數字」我們同樣需要一個步驟，而「插入合適位置」我們在第一輪需要比較一個（把 61 跟 80 比），第二輪兩個（把 55 跟 80、61 比），第三輪三個，以此類推。
因此，在最壞狀況，我們在「插入合適位置」需要 1+2+3+…+n 個步驟，在「讀一個數字」需要總共 n 個步驟， 經過神秘計算後， 就會得到和選擇排序法相同的 n * (n+3) / 2 個步驟，其時間複雜度我們記為 O(n²)。
插入排序法在程式碼中的例子如下，同樣地，如果下方的程式碼對於讀者還有些吃力的話，可以先多多熟悉語法後回來複習即可。
Numbers = [41,33,17,80,61,5,55]
length = len(Numbers)
for i in range(1, length):
position = i
value = Numbers[i]
while position > 0 and Numbers[position-1] > Numbers[position]:
Numbers[position], Numbers[position-1] = Numbers[position-1], Numbers[position]
position -= 1
print(Numbers)小結
在這篇文章中，我們了解了經典的演算種類：排序法，並認識了最簡單的兩種排序法選擇排序法 (Selection Sort) 與插入排序法 (Insertion Sort)。同樣擁有 O(n) 的時間複雜度，但在分析插入排序法的時間複雜度時，我們分別分析了它的最佳狀況 (Best Case) 與最壞狀況 (Worst Case)。
為了讓讀者也有小小的練習機會，讀者也可以回頭分析選擇排序法的最佳狀況與最壞狀況的分別需要的步驟數，並試看看分析兩者有什麼差別。
在下一篇文章中，我們將從 O(n²) 的排序法加速到 O(n log n)，認識更進階的排序法。
想要準時收看新文章嗎？快追蹤 AppWorks School 的粉專與 Medium Publication 吧！
【AppWorks School Batch #12 限時招生中】
AppWorks School 將開設 Android、iOS、Front-End 與 Backend Class 四個不同技能的訓練班次，全程免費，透過線上學習 4 週，駐點集訓 16 週的專案導向訓練，幫助你成為軟體工程師。
歡迎想成為軟體工程師的朋友，把握機會申請，報名到 7/22 23:59 截止喔！～https://bit.ly/2BUQmvn
嗨，我是程維，目前在美國 Google 擔任軟體工程師。如果你對入門機器學習、深度學習、人工智慧和大語言模型有興趣，我目前在準備一系列入門的文章。歡迎在這個網頁表單輸入你的電子信箱，我會在寫好的第一時間將文章寄送給你。
