1跌捆、哈希
（1）開放尋址法（蹲坑位法）
1、取模找到該位置叫倍，若有人在坑里偷卧，則繼續(xù)找，知道有空坑就跳去下一個坑
2吆倦、保證取模后的位置在指定的范圍中听诸，需要考慮到負(fù)數(shù)取模的情況
-17 % 10 的計算結(jié)果如下：r = (-17) - (-17 / 10) x 10 = (-17) - (-1 x 10) = -7
17 % -10 的計算結(jié)果如下：r = 17 - (17 / -10) x (-10) = (17) - (-1 x -10) = 7
-17 % -10 的計算結(jié)果如下：r = (-17) - (-17 / -10) x (-10) = (-17) - (1 x -10) = -7
因此，int k = (x % N + N) % N;
3蚕泽、取N時晌梨，需要取比人數(shù)多的2~3倍的質(zhì)數(shù)
4、0x3f3f3f3f比10^9次方大须妻，不會被使用到派任，可以標(biāo)識為沒用過
開放尋址法代碼
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200003, INF = 0x3f3f3f3f;
int h[N];
int find(int x)
{
int t = (x % N + N) % N;
while(h[t] != INF && h[t] != x)
{
t ++;
if(t == N) t = 0;
}
return t;
}
int main()
{
memset(h, INF, sizeof h);
int n;
scanf("%d", &n);
while(n -- )
{
char op[2];
int x;
scanf("%s%d", op, &x);
if (*op == 'I') h[find(x)] = x;
else
{
if (h[find(x)] == INF) puts("No");
else puts("Yes");
}
}
return 0;
}
（2）拉鏈法：
紅色圈圈要取的是比10^5方大的質(zhì)數(shù)
拉鏈法代碼
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200003;
int h[N], e[N], ne[N], idx;
void insert(int x)
{
int t = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[t];
h[t] = idx ++;
}
bool find(int x)
{
int t = (x % N + N) % N;
for(int i = h[t];i != -1;i = ne[i])
{
if(e[i] == x)
return true;
}
return false;
}
int main()
{
int n;
scanf("%d", &n);
memset(h, -1, sizeof h);
while (n -- )
{
char op[2];
int x;
scanf("%s%d", op, &x);
if (*op == 'I') insert(x);
else
{
if (find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}
2、快速排序
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int q[N];
void quick_sort(int l, int r)
{
if(l >= r) return ;
int i = l - 1, j = r + 1;
int mid = q[l + r >> 1];
while(i < j)
{
do {i ++;} while(q[i] < mid);
do {j --;} while(q[j] > mid);
if(i < j) swap(q[i], q[j]);
}
quick_sort(l, j);
quick_sort(j + 1, r);
}
int main()
{
cin >> n;
for(int i = 1;i <= n;i ++) cin >> q[i];
quick_sort(1, n);
for(int i = 1;i <= n;i ++) cout << q[i] << " ";
cout << endl;
return 0;
}
3璧南、歸并排序
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100000 + 10;
int n;
int temp[N], q[N];
void merge_sort(int l, int r)
{
if(l >= r) return ;
int mid = l + r >> 1;
merge_sort(l, mid); merge_sort(mid + 1, r);
int i = l, j = mid + 1;
int k = 0;
while(i <= mid && j <= r)
{
if(q[i] <= q[j]) temp[k ++] = q[i ++];
else temp[k ++] = q[j ++];
}
while(i <= mid) temp[k ++] = q[i ++];
while(j <= r) temp[k ++] = q[j ++];
for(int i = l, j = 0; i <= r;i ++, j ++) q[i] = temp[j];
}
int main()
{
cin >> n;
for(int i = 1;i <= n;i ++) cin >> q[i];
merge_sort(1, n);
for(int i = 1;i <= n;i ++) cout << q[i] << " ";
return 0;
}
4掌逛、堆排序
如何手寫一個堆？
1司倚、插入一個數(shù) heap[++ size ] = x , up(size)
2豆混、求集合當(dāng)中的最小值 heap[1]
3篓像、刪除最小值 heap[1] = heap[size]; size--; down(1)
4、刪除任意一個元素 heap[k] = heap[size];size --; up(k)皿伺，down(k)
5员辩、修改任意一個元素 heap[k] = x; up(k)，down(k)
注意：4和5中鸵鸥，后兩個操作只會執(zhí)行一個奠滑，直接把兩個寫上，結(jié)果不變妒穴，不需判斷
（1）O(n)的復(fù)雜度進(jìn)行堆化
for(int i = n/2;i >= 1;i--) down(i);
（2）更改堆元素后重建堆時間：
推算過程：循環(huán)（n - 1）次宋税，每次都是從根節(jié)點(diǎn)往下循環(huán)查找，所以每一次時間是,總時間：
,因此讼油，堆排序的時間復(fù)雜度為
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], cnt;
void down(int u)
{
int t = u;
if(u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if(u != t)
{
swap(h[u], h[t]);
down(t);
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
swap(h[u], h[u / 2]);
u >>= 1;
}
}
int main()
{
scanf("%d%d", &n, &m);
/*
//O(n)
for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
cnt = n;
for(int i = n / 2;i >= 0;i --) down(i);*/
//O(nlogn)
for(int i = 1;i <= n;i ++)
{
cnt ++;
scanf("%d", &h[cnt]);
up(cnt);
}
while(m -- )
{
printf("%d ", h[1]);
h[1] = h[cnt --];
down(1);
}
puts("");
return 0;
}
