章節2-2.排序

所謂排序演算法是指可以將一列資料依照指定順序排列，可能是由小到大、大到小，或各種順序。
C++的STL提供了內建的sort函式，儘管如此，了解常見的排序演算法仍然十分重要，以下將介紹五種最常見的排序演算法：泡沫排序、選擇排序、插入排序、快速排序、合併排序，前三者為O(n²)複雜度、易於實作、概念簡單，後兩者為O(n log n)複雜度、為常見的高效率排序演算法。雖然O(n²)的排序演算法實際上不常用到，但其中泡沫排序是APCS觀念題中常出現的概念，也仍然需要留意。

泡沫排序（Bubble Sort）

通過反覆比較相鄰的元素並交換它們的位置來排序。每次遍歷序列時，排序在較後端的元素會如泡沫般逐步「上浮」到序列的尾端。
若要由小到大排列「5,2,9,1,4」，第一次遍歷數列時，過程如下：

由於此時已經排列好最後方的4個元素，只剩下最後1個沒有上浮，但由於其已經「沉」到底部，故順序已經是最前面，不必再繼續。
以下為範例程式碼。

#include<bits/stdc++.h>
using namespace std;
int a[1005];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-i-1;j++){
            if(a[j]>a[j+1]){
                int temp=a[j]; //利用temp變數暫存來交換a[j]、a[j+1]
                a[j]=a[j+1];
                a[j+1]=temp;
            }
            //if(a[j]>a[j+1])swap(a[j],a[j+1]);
            //或者利用swap()函式也能交換兩個變數的值
        }
    }
    for(int i=0;i<n;i++)cout<<a[i]<<' ';
}

以上是泡沫排序的寫法，可以發現其非常易於實作，尤其利用C++內建的swap函式來交換變數可以壓縮到約三行的程式碼。除此之外，雖然內層迴圈的上界設為j<n-i-1能避免多餘的變數比較，但就算將j的上界設為j<n-1其實也能執行，因此實作失敗的可能性不大。

選擇排序（Selection Sort）

以小到大排列為例，每次從「待排序」的部分中選出最小的元素，然後將其交換到「已排序」部分的尾端。如此重複進行，直到整個序列排序完成。
若要由小到大排序「29,10,14,37,13」(對應索引值[0,4])，過程如下。

由於此時的最後一個元素已經不用比較，並且保證其是每次遍歷皆未被選到的最大元素，故排序完成。
以下為範例程式碼。

#include<bits/stdc++.h>
using namespace std;
int a[1005];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n-1;i++){
        int minidx=i; //紀錄最小元素之索引值，由於是尋找[i,n-1]之最小值，將其初始化為i即可
        for(int j=i+1;j<n;j++){
            if(a[j]<a[minidx]){
                minidx=j;
            }
        }
        //交換找到的最小元素和元素i
        swap(a[i],a[minidx]);
    }
    for(int i=0;i<n;i++)cout<<a[i]<<' ';
}

插入排序（Insertion Sort）

插入排序是一步一步建立排序好的序列，對於還沒排序的元素，在排序好的序列中從後向前掃描，找到相應的位置並插入，最終將所有元素排進序列中。
例如由小到大排序「5,2,9,1,5」時過程如下。
最初可以直接將原序列的開頭當作已排序好的部分，而其餘部分則等待排序
已排序:「5」，未排序:「2,9,1,5」
接著將未排序部分中的每個元素依序取出，在已排序的部分中，從後向前尋找其該插入的位置，尋找方式為逐個比較，如果當前元素比要插入的元素大，就將當前元素向後移，空出位置給要插入的元素，直到比較到大於要插入的元素就是要插入的位子，或者已經比較完所有元素所以將其插在已排序序列的開頭。以下繼續排序過程

排序完成
以下為範例程式碼。

#include<bits/stdc++.h>
using namespace std;
int a[1005];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=1;i<n;i++){ //i為要插入元素的索引值，由於a[0]可以直接當作已排序，故i從1開始
        int now=a[i]; //由於已排列的部分存在[0,i-1]，插入時a[i-1]可以會擠到a[i]來，故先保存a[i]的值，則a[i]可以用來儲存已排列部分
        int j; //內層迴圈變數j，由於最後需要知道迴圈停止的j，故將j宣告在迴圈外
        for(j=i-1;j>=0&&a[j]>now;j--){ //從a[i-1]開始往前找插入的位置，其中j是比較到第幾項
            a[j+1]=a[j]; //now要插在a[j]前，則將a[j]的值向後推到a[j+1]
        }
        a[j+1]=now;
        //若迴圈是不符a[j]>now跳出，則a[j]是第一個<=now的元素，要插入在a[j+1]，因原本的a[j+1]已經向後移，可直接使a[j+1]=now
        //若迴圈是不符j>=0跳出，則j為-1、代表插入發生在已排列部分的開頭，將a[j+1]也就是a[0]設為now即可
    }
    for(int i=0;i<n;i++)cout<<a[i]<<' ';
}

以上就是三種時間複雜度為O(n²)的排序演算法，其時間複雜度之計算可以從迴圈之執行次數看出來，但其實由於泡沫排序、選擇排序內層迴圈執行次數是由n降到1，插入排序內層迴圈執行次數是由1升到n，故總執行次數都是n²/2左右而已。

以下開始介紹兩種複雜度為O(n log n)的排序演算法，在此之前由於此兩種演算法都與遞迴有關，不熟悉的可以先複習章節0-3。不過由於這些排序演算法通常不會自己實作，而是會直接採用內建的sort函式，因此也可以選擇暫時跳過實作部分，僅理解其運作過程就好。

接著在開始介紹O(n log n)的排序演算法之前，先解釋為何其複雜度是O(n log n)，兩者的概念皆是將原本的序列拆成兩塊排列，再將拆開的序列繼續拆兩塊直到剩下一個元素，而我們假設序列都恰好拆成一半好了，以n=16為例最後的結果大概會如下。

假設對於每段長度為m的片段，我們可以透過O(m)將其弄成排列好的樣子(當然前提是由兩個已經排列好的部分來處理)，那麼可以發現以上的圖每層總長皆為16，且共有5層。事實上將n值變大時，這些片段的每層總長度仍為n，且總層數約為log₂ n(考慮對數的定義，log₂ n是2的幾次方會等於n，故將n進行log₂ n次除2也會變1)。故所有片段的總長度，也可以理解為總複雜度，就會趨近O(n log n)。

快速排序（Quick Sort）

快速排序的主要概念是，通過選擇一個「基準點」將數列分成兩部分，一部分比基準點小，由小排到大時放在基準點左邊，另一部分大於等於基準點，由小排到大時放在基準點右邊，然後對這兩部分分別進行遞迴排序。

例如由小到大排序「5,8,1,6,3,2,10」，取第一個元素5作為基準點，然後遍歷後面的所有元素，將1,3,2分到小於基準點的部分，8,6,10分到大於等於基準點的部分，並在此過程將位置交換成「1,3,2,|5,|8,6,10」(左右兩部分的順序可能與原先順序不同，但不影響結果)，然後再對「1,3,2」(索引值[0,2])、「8,6,10」(索引值[4,6])的部分用同樣方式分別繼續進行排序，最終左半邊會排成「1,2,3」，右半邊會排成「6,8,10」然後就完成排序。

而關於單次切半的過程，詳細的實作方式是，假設要排序[l,r]區間，此時可以直接選取a[l]作為基準點，於是使用迴圈遍歷[l+1,r]的所有數，看每個數是該放在左邊還是右邊，我們同時使用變數j來記錄「左半邊的最後一個元素位置」，初始化為l，而後只要將a[j+1]與當前遍歷到的a[i]交換就能將a[i]放入左邊。
同樣以升序排列「5,8,1,6,3,2,10」為例，以下用|來分隔基準點與左半部、右半部，且直到最後結束遍歷才會把基準點放到左右半部之間。

然後就算是一次的切分完成，繼續進行剩下左右部分的排序即可。

假設排序前的序列是隨機打亂的，那麼我們直接取開頭當作基準點，分出來的兩個部份的大小會是隨機，平均下來的複雜度還是接近每次都完美平分的O(n log n)。
但如果我們選到的基準點剛好很小或很大，導致每次的基準點都不是正好切在序列的中間，那效率是不是會有差？
答案是沒錯，最壞情況下就是序列長度為n，基準點將序列分成大小0與n-1的部分，然後n-1的部分再被分成0跟n-2，最後總複雜度會變成O(n²)。因此在正式實作快速排序時，經常會將其與不同的排序演算法結合來避免最壞情況複雜度O(n²)。

以下是範例程式碼。由於快速排序的實作較複雜且通常不會需要自己實作，因此將其收合，有興趣的再自行點開。

#include<bits/stdc++.h>
using namespace std;
int a[100005];
void QuickSort(int l,int r){
    if(l<r){
        int j=l;
        for(int i=l+1;i<=r;i++){
            if(a[i]<a[l])swap(a[++j],a[i]);
        }
        swap(a[j],a[l]);
        QuickSort(l,j-1);
        QuickSort(j+1,r);
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    QuickSort(0,n-1);
    for(int i=0;i<n;i++)cout<<a[i]<<' ';
}

合併排序（Merge Sort）

將序列分成兩半，對這兩半分別排序，然後將兩個已排序的部分合併起來。相較於快速排序是隨機選擇基準點將序列分為兩部分，先切分再分別排序，合併排序是直接將序列從中間切成兩半，先排序這兩半後再合併起來。
合併的方式是，如果兩個序列都已經是排列好的狀況，如「1,4,8」與「3,6,7」，那麼就將兩個序列都從頭開始跑，將其中較小的那個取出並往後跑，也就是比較1、3取1，比較4、3取3，比較4、6取4，比較8、6取6，比較8、7取7，最後再將剩下沒跑完的序列全數放進合併的序列，得到「1,3,4,6,7,8」。
以下為範例程式碼。同樣由於自行實作的機會較少，將程式碼收合起來。

#include<bits/stdc++.h>
using namespace std;
int a[100005],al[100005],ar[100005];
void MergeSort(int l,int r){
    if(l<r){
        int mid=(l+r)/2;
        MergeSort(l,mid);
        MergeSort(mid+1,r);
        int lsize=mid-l+1,rsize=r-mid;
        for(int i=0;i<lsize;i++)al[i]=a[l+i];
        for(int i=0;i<rsize;i++)ar[i]=a[mid+1+i];
        int i=0,j=0,k=l; //i為al接下來要取元素的索引值，j為ar接下來要取元素的索引值，k為a即將放元素的索引值
        while(i<lsize&&j<rsize){
            if(al[i]<=ar[j])a[k++]=al[i++];
            else a[k++]=ar[j++];
        }
        while(i<lsize)a[k++]=al[i++];
        while(j<rsize)a[k++]=ar[j++];
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    MergeSort(0,n-1);
    for(int i=0;i<n;i++)cout<<a[i]<<' ';
}