使用選擇排序法每回合會找出最小的資料然後將最小的資料與最左邊的資料互換請問每回合最左邊資料的編號為何

Question

何謂排序法？

瞭解排序法是學習演算法的必經之路。所謂排序法，就是將一堆沒有排序過的數字由小到大（或大到小）排列好的演算法。把這些排序法視覺化後就會像以下的這個療癒影片：

大致暸解何謂排序法後，就讓我們先來了解最簡單的排序法：有 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] 的陣列，在下面的圖中，我們把尚未排序過的數字用紅色標示，這輪要插入的值以橘色標示，排序過的以藍色標示。

從上面可以看到，插入排序法的步驟就像我們玩撲克牌在整牌的時候一樣，只是我們在插入排序法時一次只會插入一個數，而撲克牌在整牌的時候我們有時會同時插入兩三張牌。

接下來，讓我們用慢動作再複習一次：

https://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 截止喔！～https://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 🎉

選擇排序法 (Selection Sort)

生活中經常要用到排序、分類，例如：

將成績由高到低排序
將喜好程度由高到低排序
將可回收的垃圾分類
將筆電的價錢排序
...

對電腦來說，我們可以將排序問題轉化成以下形式

題目 - 排序

輸入說明

第1列: 1個整數N，代表接下來有幾個數字。 ( 1 <= N <= 100 )

第2列: N個待排序的整數

輸出說明

將輸出由小到大排序

input

12
50 25 76 38 19 58 29 88 44 22 11 34

output

11 19 22 25 29 34 38 44 50 58 76 88

處理排序問題有很多方法，以下介紹其中一種適合入門的選擇排序法

概念

將數字們分成2類，未排序 和 已排序

一開始所有數字都是未排序

重複 N 次：

從未排序的數字中挑出最小的數字，放入已排序的最尾端。

依照上述

第1次可以挑到所有數字中第1小的數字 (最小的數字)

第2次可以挑到所有數字中第2小的數字

...

第N次可以挑到所有數字中第N小的數字 (最大的數字)

最後就由小到大排完了

實際操作

已排序	未排序
空	50 25 76 38 19 58 29 88 44 22 11 34
11	50 25 76 38 19 58 29 88 44 22 34
11 19	50 25 76 38 58 29 88 44 22 34
11 19 22	50 25 76 38 58 29 88 44 34
11 19 22 25	50 76 38 58 29 88 44 34
11 19 22 25 29	50 76 38 58 88 44 34
11 19 22 25 29 34	50 76 38 58 88 44
11 19 22 25 29 34 38	50 76 58 88 44
11 19 22 25 29 34 38 44	50 76 58 88
11 19 22 25 29 34 38 44 50	76 58 88
11 19 22 25 29 34 38 44 50 58	76 88
11 19 22 25 29 34 38 44 50 58 76	88
11 19 22 25 29 34 38 44 50 58 76 88	空

code

想像在sort裡的 for( i=0 ; i<N ; i++ )中
- num[0] ~ num[i-1] 是已排序
- num[i+1] ~ num[N-1] 是未排序
- num[i]是現在正要增加的 已排序的最尾端
- 用變數交換，把num[i]換成未排序裡最小的數字

#include<iostream>
using namespace std;

int main()
{
    int num[100];
    int N;
    int i, j, tmp;

    //[input]
    cin >> N;
    for( i=0 ; i<N ; i=i+1 )
    {
        cin >> num[i];
    }

    //[sort]
    for( i=0 ; i<N ; i=i+1 )
    {
        for( j=i+1 ; j<N ; j=j+1 )
        {
            if( num[i] > num[j] )
            {
                //變數交換
                tmp = num[i];
                num[i] = num[j];
                num[j] = tmp;
            }
        }
    }

    //[output]
    for( i=0 ; i<N ; i=i+1 )
    {
        cout << num[i] << " ";
    }
    cout << endl;

    return 0;
}

題目練習

Zerojudge a104 排序 http://zerojudge.tw/ShowProblem?problemid=a104

延伸閱讀

泡沫排序法 http://emn178.pixnet.net/blog/post/93779892-%E6%B0%A3%E6%B3%A1%E6%8E%92%E5%BA%8F%E6%B3%95(bubble-sort)
選擇、插入、氣泡排序 http://openhome.cc/Gossip/AlgorithmGossip/SelectionInsertionBubble.htm
演算法筆記 - 排序 http://www.csie.ntnu.edu.tw/~u91029/SequenceManipulation.html