前言

昨天介紹一些比較基本的排序演算法，今天介紹進階的排序演算法與 C++ 內更方便使用的函式

更快的排序

以下的排序法會利用一些遞迴或是其他技巧來避免掉許多不必要的排序，複雜度基本上最佳可達，比一些基本排序法的快上不少

合併排序法（Merge Sort）

顧名思義，這個排序法需要合併，再往回想，需要合併就代表一定有分割，因此，我們在實作上通常會利用分治法（Divide and Conquer）先把長度為 n 的陣列一直二分直到 2 陣列都只剩 1 個元素然後處理排序的部分後再合併來完成排序，如果看不太懂的話我們拿個例子出來看看

Code:

void merge(int p,int q){
    int pe = (p + q) / 2;
    for(int i = p,j = pe + 1,k = p;i <= pe || j <= q;k++){
        if(j > q || (i <= pe && arr[i] <= arr[j])){
            mtemp[k] = arr[i];
            i++;
        }else{
            mtemp[k] = arr[j];
            j++;
        }
    }
    for (int i = p;i <= q;i++){
        arr[i] = mtemp[i];
    }
}
void msort(int p,int q){
    if (p == q){
        return;
    }
    msort(p,(p + q) / 2);
    msort((p + q) / 2 + 1,q);
    merge(p,q);
}

時間複雜度：
將陣列二分的部分理解為要除以 2 幾次到最後才會剩 1，所以這個部分為 ，合併陣列的部分為 ，總和為

快速排序法（Quick Sort）

快速排序基本上是所有排序演算法中最快的（有些特例會不符），簡單來說快速排序就是以某一個數當作基準，然後比基準小的數放在基準左邊，比基準大的放在基準右邊，然後重複動作直到排序完成為止，而如果真的不太理解，那就找個例子來看看

Code:

void qsort(int p,int q){
	int i,j;
	if (p >= q){
		return;
	}
	for (i = p,j = p + 1;j <= q;j++){
		if(arr[j] < arr[p]){
			i++;
			swap(arr[i],arr[j]);
		}
	}
	swap(arr[p],arr[i]);
	qsort(p,i - 1);
	qsort(i + 1,q);
}

時間複雜度：
基本上可以視為跟合併排序一樣為 ，但如果每次所分完的資料都集中到同一邊，也就是最慘情況，那就會是 ，最明顯的例子就是拿已經排序好的資料去排序

STL 內建的 sort 與比較函式

基本

要用內建的 sort 前要先載入 algorithm 函式庫

#include <algorithm>

sort 可將將指定範圍內的元素由小到大排序。

sort(arr + 0,arr + n);

這樣就可以排序 index = 0 ~ n - 1 的資料

sort(&arr[0],&arr[n]);

所以如果只想排序 index = i ~ j 的部分也可以這麼做

sort(arr + i,arr + j + 1);

sort 函式也可以對 string 進行排序，會按照字典序由小到大

時間複雜度：
根據 wiki 說明，他是混合的排序法，大概有三個原則

1. 資料少到一定數量時是用 Insertion Sort
2. 多到一定數量時用 Heap Sort
3. 其他是用 Quick Sort

平均下來時間複雜度為

比較函式

基本

呼叫時在後面加上第三個參數，為函式名稱

sort(arr,arr + n,cmp);

至於比較函式的撰寫方式與宣告如下
可以想成這是預設的排序(不加第三個參數)

bool cmp(int a,int b){
    return a < b;
}

而如果要將資料由大到小可以寫成

bool cmp(int a,int b){
    return a > b;
}

更複雜的資料

這邊以 ZJ a915 做說明，這一題會需要對 x,y 座標做排序，因此可以用 struct （結構）建立一個新的資料型別來存取 x,y 座標再做排序，AC Code如下

#include <bits/stdc++.h>
using namespace std;
struct point{
    long long x,y;
};
point a[1010];
bool cmp(point a,point b){
    if(a.x != b.x){
        return a.x < b.x;
    }else{
        return a.y < b.y;
    } 
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long n;
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> a[i].x >> a[i].y;
    }
    sort(a,a + n,cmp);
    for(int i = 0;i < n;i++){
        cout << a[i].x << " " << a[i].y <<"\n";
    } 
    return 0;
}

穩定排序（Stable Sort）

基本上穩定排序就是如果依照你的排列方式比下來完全相同的話他會依照順序來做排序，而如果題目有這個要求的話，那可能就不能用不穩定的排序法，包括基於 quick sort 的 intro sort，因為 quick sort 是不穩定排序

排序方法	時間	穩定與否
選擇排序		N
氣泡排序		Y
插入排序		Y
合併排序		Y
快速排序		N

因此，C++ 也有內建一個穩定排序，使用方式為

stable_sort(arr,arr + n);

使用方式跟基本的 sort 都一樣，差別在於 stable_sort 是以 merge sort 來實作的，因此為穩定排序

應用

排序可以應用在許多地方，以下舉幾個例子

• 方便搜尋
• 可以尋找重複資料（重複的資料會被排在一起）
• 找最大與最小值

預告

明天會帶幾題排序相關的題目，讓大家瞭解排序可以應用在什麼地方，也可以讓大家更看一下 C++ 內建排序的方便程度