# 快速排序法
by: hush
---
## 概念
----
1. 先**隨機選擇**一個基準點(pivot)
2. 把比它小的元素放在它的左邊，大的放右邊
3. 對左右兩邊做重複步驟1, 2，直到剩一個元素
----
實作上會利用雙指標來進行步驟2
(白板解釋)
----
code:
```cpp=
#include<bits/stdc++.h>
#define int long long
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
void Quick_sort(int l,int r,int a[]) //[l,r]
{
if (l>=r) return;
int piv=l,lp=l,rp=r;
while (lp<rp)
{
while (lp<rp && a[rp]>a[piv]) rp--;
while (lp<rp && a[lp]<=a[piv]) lp++;
swap(a[lp],a[rp]);
}
swap(a[piv],a[lp]);
Quick_sort(l,lp-1,a);
Quick_sort(lp+1,r,a);
}
signed main()
{
//colinorz;
int n,a[100005]; cin >> n;
for (int i=0;i<n;i++) cin >> a[i];
Quick_sort(0,n-1,a);
for (int i=0;i<n;i++) cout << a[i] << ' ';
}
```
----
- 時間複雜度：
期望上每次可以把陣列平均分成兩半遞迴，遞迴的深度會是$O(log_2n)$層，每一層的迴圈加起來會跑完整個陣列，時間複雜度是$O(n)$，所以總時間複雜度是$O(n log n)$
----
但剛剛算的是**期望上**的，若在最差的情況下，每次基準點都選到最大值，那遞迴深度會到$O(n)$層，總時間複雜度會是$O(n^2)$，故基準點通常會隨機選擇
----
```cpp=10
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
int piv=rnd()%(r-l+1)+l,lp=l,rp=r;
```
----
{%youtube 8hEyhs3OV1w%}
---
## 快速選擇
----
快速選擇(quick select)是快速排序法的一個應用
用來尋找無序序列中第$k$大(小)的值
----
- 第一個想法：
先將序列排序好再$O(1)$查詢
----
但是其實只需要讓序列第$k$個值是對的就好
所以可以小改一下快速排序遞迴的部分
- 若$pivot=k$就結束
- 若$pivot\lt k$就只呼叫右半邊
- 若$pivot\gt k$就只呼叫左半邊
----
```cpp=7
int Quick_select (int l,int r,int k)
{
int piv=l,lp=l,rp=r;
while (lp<rp)
{
while (lp<rp&& a[rp]>a[piv]) rp--;
while (lp<rp&& a[lp]<=a[piv]) lp++;
if (lp<rp) swap (a[lp],a[rp]);
}
swap (a[piv],a[lp]);
if (lp==k) return a[lp];
if (lp<k) return Quick_select (lp+1,r,k);
return Quick_select (l,lp-1,k);
}
```
----
- 時間複雜度：
1. 期望上每次陣列會剩一半，感性理解就是有可能多也可能少且機率一樣，所以平均起來就是剩一半
2. 每次都會跑過剩下的陣列，總次數是$n+\frac{n}{2}+\frac{n}{4}+...\approx 2n$，時間複雜度是$O(n)$
----
但若每次都找到極端值也有可能會到$O(n^2)$，所以pivot也建議隨機選取，以免被邪惡測資搞
----
- 練習題：
[csdc251](https://csdc.tw/problem/251/)
----
- 題解：
用quick-select找第$k-n$大的值
建議使用I/O優化(時間很緊)
----
AC code
```cpp=
#include <bits/stdc++.h>
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
using namespace std;
int a[10005];
int quick_select (int l,int r,int k)
{
int piv=a[l],lp=l,rp=r;
while (lp<rp)
{
while (lp<rp&& a[rp]>piv) rp--;
while (lp<rp&& a[lp]<=piv) lp++;
if (lp<rp) swap (a[lp],a[rp]);
}
swap (a[l],a[lp]);
if (lp==k) return a[lp];
if (lp<k) return quick_select (lp+1,r,k);
return quick_select (l,lp-1,k);
}
int main()
{
colinorz;
int n,k; cin >> n;
for (int i=0;i<n;i++) cin >> a[i];
cin >> k;
cout << quick_select (0,n-1,n-k) << '\n';
}
```
---
# 謝謝大家
{"title":"快速排序法","description":"type: slide","contributors":"[{\"id\":\"b49547c8-0e7f-46d0-99b2-8a45dfee8e90\",\"add\":3539,\"del\":740}]"}