---
# System prepended metadata

title: 排序(sort)

---

# 排序(sort)
## 基本介紹
排序，顧名思義就是將一個陣列中的所有元素依照特定順序去做排列，若要使用此函式需引用名為 ```algroithm``` 的標頭檔
```cpp
#include <algorithm>
```

收錄在 ```algorithm``` 的 ```sort``` 是最快的排序演算法，時間複雜度約為 $O(n\ log\ n)$，當然也有其他時間複雜度較慢的排序演算法，如泡沫排序法或合併排序法，但在此章節暫不介紹

*所以不要覺得自己能手刻出比 ```std::sort``` 還快的排序方法 ||邱O家曾經想做過||*
## 在傳統 array 中使用 sort 凾式
==```sort``` 的預設排序方式是遞增喔==
```cpp=
#include <iostream>
#include <algorithm> //這很重要!!!
using namespace std;

int main(){

    int arr[10] = {5, 6, 3, 8, 7, 9, 10, 2, 1, 4}; // 排序前的陣列

    sort(arr, arr+10); 
    // 假設你要從 arr[i] 排序到 arr[j], 你就會要打 sort(arr + i, arr + j + 1);
    // 像這裡就是由 arr[0] 排到 arr[9] 的結果, 當然 i 跟 j 也可以自己改改看

    for(int i = 0; i < 10; i++){
        cout << arr[i] << ' '; 
    }
    // 輸出排序完的陣列
    cout << '\n';
    
    return 0;
}
```
```
1 2 3 4 5 6 7 8 9 10
```
## 在 vector 中使用 sort 函式
==```sort``` 的預設排序方式是遞增喔==
```cpp=
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    vector<int> vec;
    vec.push_back(4);
    vec.push_back(2);
    vec.push_back(3);
    vec.push_back(5);
    vec.push_back(6);
    vec.push_back(1);
    // 排序前的陣列

    sort(vec.begin(), vec.end()); 
    // 假設你要從 vec[i] 排序到 vec[j], 你就會要打 sort(vec.begin() + i, vec.end() - vec.size() + j);
    // 不要看我註解那行然後覺得很麻煩，如果要重頭排到尾的話，直接打我16行那一行就好了
    // 像這裡就是由 vec[0] 排到 vec[5] 的結果, 當然 i 跟 j 也可以自己改改看

    for(int i = 0; i < vec.size(); i++){
        cout << vec[i] << ' '; 
    }
    // 輸出排序完的陣列
    cout << '\n';
    
    return 0;
}
```
```
1 2 3 4 5 6
```

## 將陣列中的元素以遞減排序
在```std::sort```中的預設排序方式是遞增(less), 若是要遞減的話, 可參考以下寫法

使用 ```greater``` 函式
:::spoiler code
```cpp=
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    vector<int> vec;
    vec.push_back(4);
    vec.push_back(2);
    vec.push_back(3);
    vec.push_back(5);
    vec.push_back(6);
    vec.push_back(1);
    // 排序前的陣列

    sort(vec.begin(), vec.end(), greater<int>());
    
    for(int i = 0; i < vec.size(); i++){
        cout << vec[i] << ' '; 
    }
    // 輸出排序完的陣列
    cout << '\n';
    
    return 0;
}
```
:::
當然也可以用遞增排序完之後再用```reverse```換成遞減
:::spoiler code
```cpp=
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    vector<int> vec;
    vec.push_back(4);
    vec.push_back(2);
    vec.push_back(3);
    vec.push_back(5);
    vec.push_back(6);
    vec.push_back(1);
    // 排序前的陣列

    sort(vec.begin(), vec.end());
    
    //comment 起來的是第一種寫法, 直接for迴圈交換頭尾
    /*
    for(int i = 0; i < vec.size() / 2; i++){
        int temp = vec[vec.size() - i - 1];
        vec[vec.size() - i - 1] = vec[i];
        vec[i] = temp;
    }
    */
    
    //也可用reverse函式
    reverse(vec.begin(), vec.end());

    for(int i = 0; i < vec.size(); i++){
        cout << vec[i] << ' '; 
    }
    // 輸出排序完的陣列
    cout << '\n';
    
    return 0;
}
```
:::

## 自定義排序方法
在此簡單舉兩個例子
### 在 pair 內先比 second 的大小再比 first 的排序
:::spoiler code
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


//以下這個函式若放在sort中, sort就會依照函式所寫之判斷方式去排序
bool cmp(pair<int,int> p1, pair<int, int> p2){
    if(p1.second == p2.second){
        return p1.first > p2.first; 
        //若函式回傳true, 代表p1會被排在p2的左邊
    }
    return p1.second > p2.second;
    //以此程式碼為例, 將會先比較second再比較first並以遞減排序
}

int main(){
    vector<pair<int,int>> vec;
    vec.push_back({1, 2});
    vec.push_back({3, 1});
    vec.push_back({5, 2});
    vec.push_back({1, 6});
    sort(vec.begin(), vec.end(), cmp);
    //在sort函式中放入自訂義之cmp函式即可依自己設計的方式排序
    for(int i = 0; i < vec.size(); i++){
        cout << vec[i].first << ' ' << vec[i].second << '\n';
    }

}
```
:::
### 將兩個字串以字典序排序
[維基百科中對於字典序的介紹](https://zh.wikipedia.org/zh-tw/%E5%AD%97%E5%85%B8%E5%BA%8F)
:::spoiler code
```cpp=
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool cmp(string a, string b){
    for(int i = 0; i < min(a.size(), b.size()); i++){
        if(a[i] == b[i]) continue;
        return a[i] < b[i];
    }
    return a.size() < b.size();
}

int main(){
    int n;
    cin >> n;
    vector<string> vec;
    for(int i = 0; i < n; i++){
        string str;
        cin >> str;
        vec.push_back(str);
    }
    sort(vec.begin(), vec.end(), cmp);
    for(int i = 0; i < n; i++){
        cout << vec[i] << '\n';
    }

}
```
:::
## 練習題
### [Zerojudge a233. 排序法~~~ 挑戰極限](https://zerojudge.tw/ShowProblem?problemid=a233)
:::spoiler AC code
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> vec(n);
    for(int i = 0; i < n; i++){
        cin >> vec[i];
    }
    sort(vec.begin(), vec.end());
    for(int i = 0; i < n; i++){
        cout << vec[i] << ' ';
    }
    cout << '\n';
}
```
:::
### [Zerojudge a225. 明明愛排列](https://zerojudge.tw/ShowProblem?problemid=a225)
:::spoiler AC Code
```cpp=
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> vec;
bool cmp(int a, int b){
    if(a % 10 == b % 10){
        return a > b;
    }
    return (a % 10) < (b % 10);
}
int main(){
    int n;
    while(cin >> n){
        vec.resize(n);
        for(int i = 0; i < n; i++){
            cin >> vec[i];
        }
        sort(vec.begin(), vec.end(), cmp);
        for(int i = 0; i < n; i++){
            cout << vec[i] << ' ';
        }
        cout << '\n';
    }

}
```
 
:::
### [Zerojudge a528. 大數排序](https://zerojudge.tw/ShowProblem?problemid=a528)
:::spoiler AC Code
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(pair<bool,string> a, pair<bool,string> b){
    if(a.first != b.first) return a.first;
    if(!a.first){
        if(a.second.size() != b.second.size()) return a.second.size() < b.second.size();
        for(int i = 0; i < a.second.size(); i++){
            if(a.second[i] != b.second[i]) return a.second[i] < b.second[i];
        }
    }else{
        if(a.second.size() != b.second.size()) return a.second.size() > b.second.size();
        for(int i = 0; i < a.second.size(); i++){
            if(a.second[i] != b.second[i]) return a.second[i] > b.second[i];
        }
    }
    
    return false; //這很重要
}

int main(){
    vector<pair<bool, string>> vec;
    int n;
    while(cin >> n){
        vec.resize(n);
        for(int i = 0; i < n; i++){
            string s;
            cin >> s;
            if(s[0] == '-'){
                vec[i] = make_pair(1, s.substr(1));
            }else{
                vec[i] = make_pair(0, s);
            }
        }
        sort(vec.begin(), vec.end(), cmp);
        for(int i = 0; i < n; i++){
            if(vec[i].first) cout << '-'; 
            cout << vec[i].second << '\n';
        }
    }
}
```
:::
## 總結
```sort```總結來說有以下四種用法

在 $array$ 中 : 
* ```sort(arr, arr+n) //預設遞增排序```
* ```sort(arr, arr+n, cmp) //自訂義排序```

在 $vector$ 中 : 
* ```sort(vec.begin(), vec.end()) //預設遞增排序```
* ```sort(vec.begin(), vec.end(), cmp) //自訂義排序```