# 排序(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) //自訂義排序```
Sign in with Wallet
Connect another wallet