瞭解排序法是學習演算法的必經之路。所謂排序法，就是將一堆沒有排序過的數字由小到大（或大到小）排列好的演算法。把這些排序法視覺化後就會像以下的這個療癒影片： 大致暸解何謂排序法後，就讓我們先來了解最簡單的排序法：有 O(n²) 時間複雜度的選擇排序法！ 時間複雜度為 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 個步驟。何謂排序法？
O(n²)：選擇排序法 (Selection Sort)
找最小值
丟到左邊
選擇排序的時間複雜度
找到最小值
丟到最左邊
結合找到最小值與丟到最左邊
把上面的兩個結果加起來，(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] 的陣列，在下面的圖中，我們把尚未排序過的數字用紅色標示，這輪要插入的值以橘色標示，排序過的以藍色標示。
從上面可以看到，插入排序法的步驟就像我們玩撲克牌在整牌的時候一樣，只是我們在插入排序法時一次只會插入一個數，而撲克牌在整牌的時候我們有時會同時插入兩三張牌。
接下來，讓我們用慢動作再複習一次：
//commons.wikimedia.org/wiki/File:Insertion-sort-example.gif看完插入排序的慢動作後，讓我們一起來分析它的時間複雜度的部分吧！
插入排序的時間複雜度
觀察插入排序法的時間複雜度，我們要同時複習一個在上一篇文章中提到的觀念：
通常程式步驟的時間複雜度會是用程式執行會碰到的最壞狀況 (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 截止喔！～//bit.ly/2BUQmvn
Want to Learn More? Weekly I/O!
Weekly I/O is a project where I share my learning Input/Output. Every Sunday, I write an email newsletter with five things I discovered and learned that week.
Sign up here and let me share a curated list of learning Input/Output with you 🎉
使用二分搜尋法 (binary search) 在一個整數陣列中搜尋特定數值中，下列何者為非？ (A) 陣列中的數值必須已依大小排序，否則不保證搜尋結果正確。 (B) 二分搜尋法不能處理資料不存在的狀況。 (C) 若陣列大小擴增為 N 倍，線性搜尋法 (linear search) 所需計算量平均擴增 N
倍，但二分搜尋法只會擴增 $\sqrt{N}$ 倍。 (D) 若只需要搜尋一次，使用「線性搜尋法」會比「將陣列排序再作二分搜尋法」更有效率。演算法
重要觀念
參考資料
107 北市
4.
5.
在某個程式語言中，若 a 與 b 為兩個整數變數： a/b 運算是「a 除以 b」，例如 3/2 為 1.5。 a//b 運算是「小於且最靠近 a/b 的整數」，例如 3/2 為 1。 a%b 運算是「取 a 除以 b 的餘數」，且必定滿足 a = b´(a//b) + (a%b)。 請問若 a 為介於 0 到 10000（含）的值，a % -1234 不可能是下列哪個值？ (A) 0 (B) 3 (C) -3 (D) 都有可能
23.
下列陣列內容的改變為哪一個排序法的執行過程？ (A) 堆積排序法 (heap sort) (B) 合併排序法 (merge sort) (C) 泡沫排序法 (bubble sort) (D) 選擇排序法 (selection sort)
106 北市
2.
有 1,000 張已經依照數字號碼排好序的統一發票，若要知道頭獎號碼（只有一組號碼）有沒有在這些發票中，可以利用二元搜尋法，最多要比較幾次就能確認？ (A) 9 次 (B) 10 次 (C) 11 次 (D) 12 次
10.
以泡沫排序法（bubble sort）將下列七個數字 27, 16, 4, 98, 0, 56, 39 由小排到大，則需經過幾次的交換（interchange）動作？ (A) 8 (B) 9 (C) 10 (D) 以上皆否
14.
泡沫排序法 (Bubble sort) 在最佳狀態 (best case) 下的時間複雜度為何？ (A) O(1) (B) O(N) (C) O(logN) (D) O(NlogN)
16.
若有 10 個正整數使用選擇排序法 (selection sort) 來排序，在最壞的狀況下，排序過程中所需的交換 (swap) 次數最多為多少？ (A) 9 次 (B) 10 次 (C) 90 次 (D) 100 次
105 北市
6.
假設我們有一千筆資料，如果資料未經排序整理，則我們平均要搜尋 X 次才能找到所需要的資料，但如果資料已經排序整理，則我們平均只要搜尋 Y 次，請問 X 大約是 Y 的幾倍？ (A) 2 倍 (B) 1000 倍 (C) 10 倍 (D) 100 倍
8.
帥慶和高弟在玩猜數字遊戲，帥慶先寫下一個介於 1 至 1000 的數字，高弟能不斷提問 「這個數字是否介於 xx 及 yy」 (xx, yy 都是介於 1 與 1000 的數字)，而帥慶一定會誠實的回答。如果高弟利用最佳策略，請問不管帥慶寫下哪一個數字，高弟只需要提問幾次就一定可以得出答案？ (A) 999 (B) 500 (C) 32 (D) 10
17.
有一個二維字元陣列 maze，其初始值如下表右方所示。請問呼叫 dfs(maze,4,2) 之後，此陣列中還有多少個 O？（注意:陣列索引值從 0 起算。）
function dfs (char maze[][], int x, int y) { if (maze[x][y] != ‘O’) return; maze[x][y] = ‘X’; for i = -1 to 1 do { for j = 0 to 1 do { dfs (maze, x+i, y+j); } } }
char maze[6][7] = { “XXXXXXX”, “XOXXXOX”, “XOXOOXX”, “XOOOXOX”, “XXOOOXX”, “XXXXXXX” };
(A) 7 (B) 3 (C) 0 (D) 13
18.
從一個 7x7 的二維陣列 maze 的 maze[4][5] 位置開始施行廣度優先搜尋 (breadth-first search, BFS)，展開節點時的次序是上、右、下、左，請問 maze[3][3]（用＊標記）這個位置是第幾個被展開來的？下圖已標記出前 9 個被展開的節點。 (A) 16 (B) 17 (C) 18 (D) 19
22.
若以一個陣列儲存一些正整數，並將該陣列的數字由大到小排列。接下來以二元搜尋法 (Binary Search) 搜尋該陣列，並依序寫下搜尋過程的數值，下列何者不可能是正確搜尋過程的數值？ (A) 50, 100, 150, 200, 249, 314, 5000 (B) 500, 34, 4, 1 (C) 156, 1245, 947, 742, 1000, 999 (D) 42453, 5924, 724, 2109, 1999, 1990, 1997