# 排序與搜尋
## 5/28 資訊讀書會
---
# 排序
----
## 排序
* 排序是將一群資料根據某種順序排列，通常是由小到大。
* c++有內建排序函式`sort()`可以將一段指標範圍內的資料依照預設或給定的比較方法做排序。
* 也可以自己寫排序。
----
## `sort()`函式
* `sort(begin, end, comp)`有兩個必要參數和一個預設參數。
* 前兩個參數是排序的起點和終點的指標(位置)，不過終點代表排序結束的下一位。
* 第三個參數是比較，預設是小的會在前面。
----
## `comp`比較運算
* `comp`的預設是嚴格小於，也就是前面的比後面的小才會成立。
* `comp`有列一個內建函式`greater`，也就是嚴格大於。
* `comp`函式必須是嚴格比較，也就是相等時不能回傳`true`，不然會卡住。
* `sort`會把回傳`true`的放前面。
----
### 例子：
```cpp=
#include <bits/stdc++.h>
using namespace std;
bool comp(pair<int, int> a, pair<int,int> b){
if(a.first+a.second==b.first+b.second){
return (a.first<b.first);
}
else return (a.first+a.second<b.first+b.second);
}
int main() {
int n=10;
pair<int,int> arr1[n];
// 隨機產生
for (int i=0;i<n;i++){
arr1[i]={rand()%10, rand()%10};
printf("(%d,%d) ", arr1[i].first, arr1[i].second);
}
printf("\n");
// 一般排序
sort(arr1, arr1+n);
for(int i=0; i<n; i++)
printf("(%d,%d) ", arr1[i].first, arr1[i].second);
printf("\n");
// 反向排序
sort(arr1, arr1+n, greater< pair<int,int> >());
for(int i=0; i<n; i++)
printf("(%d,%d) ", arr1[i].first, arr1[i].second);
printf("\n");
// 自訂排序
sort(arr1, arr1+n, comp);
for(int i=0; i<n; i++)
printf("(%d,%d) ", arr1[i].first, arr1[i].second);
printf("\n");
return 0;
}
```
### 一組結果
```
(3,6) (7,5) (3,5) (6,2) (9,1) (2,7) (0,9) (3,6) (0,6) (2,6)
(0,6) (0,9) (2,6) (2,7) (3,5) (3,6) (3,6) (6,2) (7,5) (9,1)
(9,1) (7,5) (6,2) (3,6) (3,6) (3,5) (2,7) (2,6) (0,9) (0,6)
(0,6) (2,6) (3,5) (6,2) (0,9) (2,7) (3,6) (3,6) (9,1) (7,5)
```
---
# 排序方法
----
## merge sort(合併排序法)
### 不建議自己寫
* merge sort是分治的方法，時間複雜度$O(NlogN)$。
* 核心程式是把兩串已經排好的資料合併成一串排好的資料，時間複雜度$O(N)$。
* 排列時會先不斷把資料分成兩半，直到每個都是一個，然後再不斷合併，總共執行$O(logN)$次。
----
## quick sort(快速排序法)
* quick sort會選擇一個值當基準，把所有比它大的放右邊，比它小的放左邊。於是基準就會在對的位置上，這個步驟的複雜度為$O(N)$。
* 然後會在兩邊再各自進行quick sort，直到每組只剩一個元素，此時就都會在正確的位置了。
* 平均時間複雜度$O(NlogN)$，最差複雜度$O(N^2)$，不過比merge sort省空間。
----
## bubble sort(泡沫排序法)
* bubble sort是每次掃過，發現有左邊比右邊小的，就交換左右。
* 因為每次掃過後，最大的都會移到右邊，所以右界可以每次少1。
* 最佳複雜度為$O(N)$，最差為$O(N^2)$。
* 因為每次未排序區內最大的都會浮上來，所以叫泡沫。
----
## selection sort(選擇排序法)
* 每次會在未排序區找到最小的，放在未排序區的左邊，加入已排序區。
* 複雜度$O(N^2)$。
----
## insertion sort(插入排序法)
* 一開始已排序區為第一個數字，每次排序會把未排序區的第一個放入已排序區。
* 要排序的會從尾端往回比較大小，將未排序區的數字插入到已排序區的適當位置。
* 複雜度$O(N^2)$。不過對於快排好的資料排序較快。
----
## comb sort(梳排序法)
* 改良自bubble sort和quick sort，不過bubble sort每次的間距都是1，而comb sort則是從全長遞減，通常是每次\*0.8。到1的時候再用bubble sort檢查與修正。
* 為了消除bubble sort中，在末端的小值會讓排序變很慢的問題。
* 時間複雜度最佳$O(N)$，最差$O(N^2)$。
* 因為在開始時效率較好，在間距便小時可改用insertion sort。
----
## shell sort(希爾排序法)
* 改良自insertion sort，不過往回比較的間距不是1，且會不斷變小。
* 最佳間距序列為(1, 5, 19, 41, 109,...)，為兩個數列的交錯合併。
第一個為 $9*4^i-9*2^i+1$，
另一個為 $2^{i+2}*(2^{i+2}-3)+1$。
* 最糟複雜度$O(Nlog^2N)$，比$O(NlogN)$差一點。
* 也可以用 $2^k-1$，最糟複雜度 $O(N^{3/2})$
* 對幾乎排好的資料組有$O(N)$複雜度。
----
## heap sort(堆積排序)
* heap sort是利用堆積的性質的排序法。把陣列變成最大堆積來排序。
* 堆積類似完全二元樹，並且每個子節點的索引都大於父節點。
* 節點i的左子節點在$2𝑖+1$，右子節點在$2i+2$
節點i的父節點在$(i+1)/2$
* 複雜度$O(NlogN)$
* [補充點這個](https://www.youtube.com/watch?v=Q1yi1eaqN7I)
---
# 程式區
### 不建議自己寫
----
## merge sort
```cpp=
void merge(int *arr, int L, int M, int R){
int l = L; // 左半部執行到第幾個
int r = M+1; // 右半部執行到第幾個
int tmp[R-L], i = 0; // i是tmp的索引
while((l<M)&&(r<R)){ // 左邊和右邊都沒跑完
// 把比較小的放進去，到下一個
if(arr[l]<arr[r]){
tmp[i]=arr[l];
l++;
}
else{
tmp[i]=arr[r];
r++;
}
i++;
}
while(l<=M){ //剩下的也放進去
tmp[i]=arr[l];
i++; l++;
}
while(r<=R){
tmp[i]=arr[r];
i++; r++;
}
for(i=0; L+i<R; i++) arr[i+L] = tmp[i];
return;
}
void mergesort(int *arr, int L, int R){
int M = (L+R+1)/2;
if(L<R){
mergesort(arr, L, M); //排序左半部
mergesort(arr, M, R); // 排序右半部
merge(arr, L, M, R); // 合併
}
return;
}
```
----
## quick sort
```cpp=
void quicksort(int *arr, int l, int r){
if(l==r) return;
int p = arr[r]; // 把pivot訂為結尾
int idx = l;
for(int i=l; i<r; i++){
if(arr[i] < p){
swap(arr[idx], arr[i]);
idx++;
}
}
swap(arr[r], arr[idx]); // 把pivot移到它最後的地方
quicksort(arr, l, idx-1); // 排序左半部
quicksort(arr, idx+1, r); // 排序右半部
return;
}
```
----
## bubble sort
```cpp=
void bubblesort(int *arr, int l, int r;){
bool u = true; // 還要不要繼續排
for(int i=l; i<r-1; i++){
u=false;
for(int j=l; j<r-1-i; j++)
if(a[j] > a[j+1]){
swap(a[j], a[j+1]);
u = true;
}
if(!u) break;
}
return;
}
```
----
## selection sort
```cpp=
void selectionsort(int *arr, int l, int r){
for(int i=l; i<r; i++){
int idx=i;
for(int j=i; j<r; j++){ // 找最小
if(arr[idx]>arr[j]) idx=j;
}
swap(arr[idx], arr[i]);
}
return;
}
```
----
## insertion sort
```cpp=
void insertionsort(int *arr, int l, int r){
for(int i=l+1; i<r; i++){
int ins = arr[i]; // 儲存要排序的數
int j=i-1; // 往回比大小
while(j>=l && arr[j]>ins){
arr[j+1] = arr[j]; // insert不會變
j--;
}
arr[j+1] = ins; // while退出時j會-1，所以要+1
}
return;
}
```
----
## comb sort
```cpp=
void comb_sort(int *arr, int l, int r){
double d = 0.8;
int g = r-l; // 間隔
bool u=true; // 還要不要排
while(u || g>1) {
if(g>1)
g=(int)(g*d);
u=false;
for(int i=0; l+i+g<r; i++)
if(arr[i] > arr[i + g]) {
swap(arr[i], arr[i + g]);
u=true;
}
}
}
```
----
## shell sort
```cpp=
void shellsort(int *arr, int l, int r){
int d=1;
while(d < (r-l) / 3) {
d = 3*d+1;
}
while(d>=1) {
for(int i=d; l+i<r; i++) {
for(int j=l+i; j>=l+d && arr[j]<arr[j-d]; j-=d) {
swap(arr[j], arr[j - d]);
}
}
d /= 3;
}
}
```
----
## heap sort
```cpp=
// 調整為最大堆積
void max_heap(int *arr, int l, int f, int r) {
// 左子節點索引
int s = l+2*(f-l)+1;
while(s<r){ // 子節點在範圍內
// 選大的子節點
if(s+1<r && arr[s]<arr[s+1])
s++;
if(arr[f]>arr[s]) // 父節點比子節點大，調整完畢
return;
else{ // 否則交換父子內容，再往下一層比較
swap(arr[f], arr[s]);
f = s;
s = l+2*(f-l)+1;
}
}
}
void heapsort(int *arr, int l, int r){
// 從最後一個父節點開始調整
for (int i=(r+l)/2-1; i>=l; i--)
max_heap(arr, l, i, r);
// 先把第一個(最大)和最後一個交換，再調整沒排好的，直到排完
for (int i=r-1; i>l; i--) {
swap(arr[l], arr[i]);
max_heap(arr, l, l, i);
}
}
```
---
# 搜尋
----
## 搜尋
* 在一群資料中尋找某筆資料，通常用線性搜尋或二分搜。
* 線性搜尋就是一個一個找過去，用在未排序的資料，時間複雜度O(N)。
* 資料如果已經排序好，就可以用二分搜，會比線性搜尋快很多，時間複雜度O(logN)。
----
## 二分搜
* 二分搜是每次都跟中間比較，比中間的大就把範圍縮減成中間到結束，較小的話則是變成開始到中間。
* 因為每次的範圍都會減半，所以最多花log(2,N)次，而存取陣列、比較都是O(1)。
----
## 程式
```cpp=
int bsearch(int *arr, int l, int r, int x) {
int m;
while (l<=r) {
m=(l+r)/2;
if(arr[m]==x) return m;
if(arr[m]<x) l=m+1; //右半邊
else r=m-1; //左半邊
}
return -1; //沒找到
}
```
----
## 三分搜
* 三分搜是用來找出一組從遞減變成遞增(或反過來)的資料的最小值。
* 利用上下界不斷縮小範圍，直到找到最小值。
----
## 程式(凹口向上)
```cpp=
int tsearch(int *arr, int l, int r) {
int ml, mr;
while (l<r) {
ml=(2*l+r)/3;
mr=(l+2*r)/3;
if(arr[ml]>arr[mr]) l=ml; // 左邊比較大，往右
else r=mr;
}
return arr[l];
}
```
{"title":"排序與搜尋","contributors":"[{\"id\":\"00ad9127-6491-4b3d-829b-7847a217f8e5\",\"add\":16063,\"del\":8630}]","description":"5/28 資訊讀書會"}