# 排序、二分搜
---
# C++內建排序
## sort()函式
----
sort()有兩個輸入、一個非必要輸入
分別是排序起點、終點，和比較方法
起點和終點為迭代器或指標，比較方法則是
----
排序會從起點排到終點前一個，
內建的排序會比自己寫的排序快，所以除非有特殊需求，不然不用自己寫
----
可以對傳統陣列排序
```cpp=
int arr[] = {4, 1, 5, 1, 2, 0};
sort(arr, arr+6);
for(int i:arr){ // 這樣可以
cout<<i<<' ';
} // 0 1 1 2 4 5
cout<<'\n';
```
----
也可以對STL的vector排序
```cpp=
vector<int> v = {4, 1, 3, 1, 2};
sort(v.begin(), v.end()); // 從最開始排序到最後一個
// .end()代表的是最後一項的下一項，所以不用再加1
for(int i:v){
cout<<i<<' ';
} // 1 1 2 3 4
cout<<'\n';
```
----
也可以對部分的陣列排序
```cpp=
// 傳統陣列
int arr[] = {4, 1, 5, 1, 2, 0};
sort(arr+1, arr+5); // 從索引[1]排序到索引[5-1]
for(int i:arr){
cout<<i<<' ';
} // 4 1 1 2 5 0
cout<<'\n';
// vector
vector<int> v = {4, 1, 3, 1, 2};
sort(v.begin()+1, next(v.end(), -1)); // 迭代器可以直接加
// 也可以用next()來移動
for(int i:v){
cout<<i<<' ';
} // 4 1 1 3 2
cout<<'\n';
```
----
## 例題 [ZJ a104](https://zerojudge.tw/ShowProblem?problemid=a104)
重複輸入直到結束
每次給要排序的數量和數列
輸出由小到大排序好的數列
補充:如果要輸入到結束，可以用while(cin>>n)
----
## 解答
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
while(cin>>n){
vector<int> v(n);
for(int i=0; i<n; ++i){
cin>>v[i];
}
sort(v.begin(), v.end());
for(int i=0; i<n; ++i){
cout<<v[i]<<' ';
}
cout<<'\n';
}
return 0;
}
```
---
# 改變排序比較
c++有內建的方法可以讓我們把sort變成降序
但如果是一些內容物不能比較的陣列(像是二維陣列)就要用一些自己的方法
----
```cpp=
vector<int> v = {4, 1, 3, 1, 2};
sort(v.begin(), v.end(), greater<int>()); // 改成大的在前面
// 要注意型態
for(int i:v){
cout<<i<<' ';
} // 4 3 2 1 1
cout<<'\n';
```
----
預設是less\<T\>，可以改成greater\<T\>
要注意，在排序中，相等不應該回傳真
否則在某些排序法中會出錯
要排序string的內容，要用less\<char\>或
greater\<char\>
---
# 自訂比較方法
---
## 方法一
# 比較函式
----
以一個bool函式，做為第三個參數傳入
兩個參數都要是目標類型
----
### 範例
比vector\<int\>
看哪個的總和比較小
```cpp=
bool compare (vector<int> v1, vector<int> v2){
int s1=0, s2=0;
for(int i=0; i<v1.size(); i++){
s1+=v1[i];
s2+=v2[i];
}
if(s1<s2)
return true;
else
return false;
}
```
----
```cpp=
vector<int> v1 = {2, 1, 3, 4, 2}, v2 = {3, 2, 0, 1, 4};
cout<<compare(v1, v2)<<'\n'; // 直接比兩個陣列
vector<vector<int>> v;
v.push_back(v1); v.push_back(v2); // 放進二微陣列
sort(v.begin(), v.end(), compare);
for(vector<int> vi:v){
for(int i:vi)
cout<<i<<' ';
cout<<'\n';
}
cout<<'\n';
```
輸出
```
0 (代表False)
3 2 0 1 4
2 1 3 4 2
```
---
## 方法二
# 運算子多載
----
宣告一個bool類型函式，接著
operator加上比較符號(通常是<)，代表運算子多載
接著，有兩個參數，都是要比較的類型
最後，寫好要怎麼比
----
### 範例
比vector\<int\>
先比大小，再比每一項
```cpp=
bool operator < (vector<int> v1, vector<int> v2){
// 宣告運算子多載
if(v1.size()<v2.size()) // 先比陣列大小
return true;
if(v1.size()>v2.size())
return false;
for(int i=0; i<v1.size(); ++i){// 再逐項比較
if(v1[i]<v2[i])
return true;
if(v1[i]>v2[i])
return false;
}
return false; // 如果上面比完都沒回傳，代表兩個一樣
}
```
----
接著，我們可以直接用這個來比較，也可以用sort()來比vector\<int\>了
```cpp=16
vector<int> v1 = {4, 1, 3, 1, 2}, v2 = {1, 2, 5, 4, 6};
cout<<(v1<v2)<<'\n'; // 直接比陣列
vector<vector<int>> v;
v.push_back(v1); v.push_back(v2); // 放入二維陣列
sort(v.begin(), v.end()); // 改成大的在前面
for(vector<int> vi:v){
for(int i:vi)
cout<<i<<' ';
cout<<'\n';
}
cout<<'\n';
```
輸出
```
1 (代表True)
1 2 5 4 6
4 1 3 1 2
```
---
# 二分搜
----
## 搜尋
搜尋是在給一個元素的情況下
找到對應的索引值
最簡單的方法是逐一存取，只是會花不少時間
----
二分搜必須在已經排好的資料中搜尋
首先，取得在陣列中央的值，比較和目標比較
如果比目標小，代表目標更大，就減少了一半的搜索範圍
如果筆目標小，也一樣減少了一半範圍
重複直到找到或確定不在陣列中
----
程式範例
```cpp=
// v 是一個已經排序好的vector
int bisearch(vector<int> v, int target, int begin, int end){
int l=begin, r=end, m; // l跟r是目標可能在的範圍
while(l<=r){
m=(l+r)/2; // 每次取中間
if(v[m]==target){ // 如果找到了
while(v[m]==target) --m; // 找到這些相同數字的第一個
return m+1;
}
if(v[m]<target) l = m+1; // 在m左邊的都不可能
else r = m-1; // 在m右邊的都不可能
}
return -1; // 如果沒找到(通常會在外面處理沒找到的情況)
}
```
----
## 例題 [ZJ f679](https://zerojudge.tw/ShowProblem?problemid=f679)
給定一由小到大排序的數列及其大小
找到目標編號是否在數列中
----
## 例題解答
```cpp=
#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int n;
bool bisearch(int x){
int l=0, r=n, m;
while(l<=r){
m=(l+r)/2;
if(v[m]==x) return true;
if(v[m]>x) r=m-1;
else l=m+1;
}
return false;
}
int main()
{
int q, x;
cin>>n>>q;
v.resize(n,0);
for(int i=0; i<n; i++){
cin>>v[i];
}
for(int i=0; i<q; i++){
cin>>x;
if(bisearch(x))
cout<<"Yes\n";
else
cout<<"No\n";
}
return 0;
}
```
---
# 額外補充
---
# 排序法
不會講太細，有興趣可以查
----
## 泡沫排序
每一輪會從第一項跟第二項比，到最後兩項相比
每次比較會把小的放前面，大的放後面
因為每一輪都會讓最大的到最後而稱作泡沫
如果有一輪都沒執行交換就代表排好了
時間複雜度$O(n^2)$
----
## 插入排序
每次取未排序的第一項，找到它應該要
在已排序區的位置(搜尋)
時間複雜度$O(n^2)$
----
## 合併排序
每次將資料分成兩半，直到剩下一個時不再分割
接著將資料以原本的分割順序合併，並同時排序
時間複雜度$O(n\ logn)$，但空間需求較大
----
## 快速排序
每次從資料中選出一個基準
比基準小的放一邊，比較大的放另一邊
接著兩邊再各自選出基準排序
持續直到排序結束
時間複雜度$O(n\ logn)$
---
# sort()
# lambda匿名函式
---
lambda匿名函式可以在函式內寫函式
```cpp=
vector<vector<int>> v={{2,4,2,3},{2,0,2,5}};
sort(v.begin(), v.end(),
[](vector<int> v1, vector<int> v2){ // 宣告lambda函式
int n=min(v1.size(), v2.size());
for(int i=0; i<n; i++){ // 先逐項比，直到其中一個的最後
if(v1[i]<v2[i])
return true;
if(v1[i]>v2[i])
return false;
}
if(v1.size()<v2.size()) // 最後比陣列大小
return true;
return false;// 沒有比較小
});
for(auto vi:v){
for(int i:vi)
cout<<i<<' ';
cout<<'\n';
}
```
輸出
```
2 0 2 5
2 4 2 3
```
{"description":"排序是將資料以給定的比較方法排列","contributors":"[{\"id\":\"00ad9127-6491-4b3d-829b-7847a217f8e5\",\"add\":6483,\"del\":947}]","title":"排序、二分搜"}