# PAT 甲级 总结
# 一、数学类
常作为PAT中基本20分的小题，题目变化较为新颖，但基本思路不变。
# 1.1 素数
**埃式筛选法：**要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
int flag[maxn] = {false};
int prime[maxn], pNum = 0;
void findprime(int n)
{
flag[0] = flag[1] = true;
for (int i = 2; i <= n; i++)
{
if (!flag[i])
{
prime[pNum++] = i;
for (int j = i*i; j <= n; j+=i)
{
flag[j] = true;
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
欧拉筛法：在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。
int flag[maxn] = {false};
int prime[maxn];
void eulerSieve(int n)
{
fill(flag, flag + maxn, 0);
flag[0] = flag[1] = true;
fill(prime, prime + maxn, 0);
for (int i = 2; i <= maxn; i++) {
if (!flag[i]) {
prime[++prime[0]] = i;
}
for (int j = 1; j <= prime[0] && i * prime[j] <= maxn; j++) {
flag[i * prime[j]] = true;
if (i % prime[j] == 0) {
break;
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
[注]：
1、这里不是用 i 的倍数来消去合数，而是把 prime 里面纪录的素数，升序来当做要消去合数的最小素因子
2、对于 i%prime[j] == 0 就break的解释 ：
当 i 是prime[j]的倍数时，i = k*prime[j]，如果继续运算 j+1，i * prime[j+1] = prime[j] * k * prime[j+1]，
这里prime[j]是最小的素因子，当 i = k * prime[j+1] 时会重复，所以才跳出循环。
# 1.2 最大公约数
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a%b);
}
1
2
3
4
2
3
4
[注]：a>0, b>0
# 1.3 快速幂
long long ksm(long long a, int b)
{
long long base = a, ans = 1;
while (b != 0) {
if (b & 1 != 0)
{
ans *= base;
}
base *= base;
b >> 1;
}
return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
**[注]：**在数论里又叫反复平方法，这里要注意的是，当幂是奇数的时候，需要多乘一次底数（因为奇数整除2会扔掉一个底数因子）。
# 1.4 进制转换
使用字符串表示数字，a~z表示10~35
long long convert(string n, long long radix)
{
long long base = 1;
long long num = 0;
for (auto lt = n.rbegin(); lt != n.rend();lt++) {
int tmp = isdigit(*lt) ? *lt - '0' : *lt - 'a' + 10;
num += tmp*base;
base *= radix;
}
return num;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 1.5 字符串加法
//strlen(s1)>strlen(s2)
string addstring(string s1, string s2)
{
int carry = 0;
for (int i = (int)s1.size() - 1, t; i >= 0; i--) {
t = (s1[i] - '0') + (s2[i] - '0') + carry;
s1[i] = t % 10 + '0';
carry = t / 10;
}
if (carry > 0) s1.insert(s1.begin(), carry + '0');
return s1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 1.6 大数运算
struct bign
{
int len;
int d[110];
bign() {
len = 0;
memset(d, 0, sizeof(d));
}
};
bign convert(char s[])
{
bign a;
a.len = strlen(s);
for (int i = a.len - 1; i >= 0; --i)
{
a.d[a.len - 1 - i] = s[i] - '0';
}
return a;
}
bign add(bign a) {
bign c;
int carry = 0;
c.len = 0;
for (int i = 0; i < a.len; i++)
{
int temp = a.d[i] + a.d[a.len - 1 - i] + carry;
c.d[c.len++] = temp % 10;
carry = temp / 10;
}
if (carry != 0) {
c.d[c.len++] = carry;
}
return c;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# 二、二叉树
常作为PAT 中25分题出现，偶尔以30分的形式出现(2021.9.11 秋季)，其基本理论不难，不外乎以下情况：
1、中序 前序 构树 2、中序 后序 构树 3、层级 中序 构树 4、二叉搜索树 5、AVL树 6、堆 7、完全二叉树
根据历年考试的题目的趋势，主考点渐渐从树转向堆，即堆以完全二叉树的形式呈现
二叉树的考题能不建树就不建树，建树也用静态比较简单
# 2.1 序列转换
作为核心考点树里的核心，需要非常熟练理解掌握树序列的转化（不建树）。做题时有一个思想是，有了包含中序的两个序列，树就有了，其余问题都可在序列上进行。
**[注]：**理解是关键，不要死记硬背。
已知中序 前序，求层序、后序：
vector<int> pre, in,post, le[maxn];
//taril(0,0,n-1,0);
void taril(int root, int start, int end, int level)
{
if (start > end)
{
return;
}
int idx = pre[root];
int pos = start;
while (in[pos] != idx) pos++;
le[level].push_back(in[pos]); //记录层级
taril(root + 1, start, pos - 1, level + 1);
taril(root + 1, pos + 1, end, level + 1);
post.push_back(idx); //记录后序
return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
已知后序 前序，求层序、前序：
vector<int> pre, in,post, le[maxn];
//taril(n-1,0,n-1,0);
void taril(int root, int start, int end, int level) {
if (start > end)
{
return;
}
int idx = post[root];
int pos = start;
while (in[pos] != idx) pos++;
pre.push_back(in[pos]); //记录前序
le[level].push_back(in[pos]); //记录层级
taril(root - 1 - (end - pos), start, pos - 1, level + 1);
taril(root - 1, pos + 1, end, level + 1);
return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 2.2 堆 完全二叉树
用一个int heap[N+1]来记录（N个结点，标号从1开始）
完全二叉树最重要的核心性质就是要抓住对于某个下标 i ，其左子下标为 2 * i ，其右子下标为2 * i + 1
以大顶堆为例
向上调整：
void update(int low, int high)
{
int i = high, j = high >> 1;
while (j >= low) {
if (heap[i] > heap[j])
{
swap(heap[i], heap[j]);
i = j;
j = i >> 1;
}
else {
break;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
向下调整：
void downAdj(int low, int high)
{
int i = low, j = low << 1;
while (j <= high) {
if (j + 1 <= high&&heap[j]<heap[j + 1])
{
j++;
}
if (heap[i] < heap[j])
{
swap(heap[i], heap[j]);
i = j;
j = i << 1;
}
else {
break;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
堆排序：
void heapSort(int n) {
for (int i = n / 2; i > 0; i--) {
downAdj(i, n);
}
for (int i = n; i > 1; i--) {
swap(heap[1], heap[i]);
downAdj(1, i - 1);
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 2.3 二叉搜索树 BST
建树时采取从根结点开始的插入思想
1、对于每个结点，左边的小，右边的大(哪边取等于看题意)
2、BST树的中序就是数据从小到大的序列
# 2.4 AVL树
struct node {
int data;
node *lchild, *rchild;
int heigh;
};
int getHeight(node * root)
{
if (root == NULL) {
return 0;
}
return root->heigh;
}
int getBalance(node *root)
{
return getHeight(root->lchild) - getHeight(root->rchild);
}
void updateHeight(node *&root) {
root->heigh = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}
void L(node * &root)
{
node *tmp = root->rchild;
root->rchild = tmp->lchild;
tmp->lchild = root;
updateHeight(root);
updateHeight(tmp);
root = tmp;
}
void R(node * &root)
{
node * tmp = root->lchild;
root->lchild = tmp->rchild;
tmp->rchild = root;
updateHeight(root);
updateHeight(tmp);
root = tmp;
}
void insert(node* &root, int data)
{
if (root==NULL)
{
root = new node();
root->heigh = 1;
root->lchild = root->rchild = NULL;
}
else {
if (data < root->data)
{
insert(root->lchild, data);
if (getHeight(root) == 2) {
if (getHeight(root->lchild) == 1)
{
R(root);
}
else if (getHeight(root->lchild) == -1) {
L(root->lchild);
R(root);
}
}
}
else {
insert(root->rchild, data);
if (getHeight(root) == -2) {
if (getHeight(root->rchild) == -1)
{
L(root);
}
else if (getHeight(root->rchild) == 1) {
R(root->rchild);
L(root);
}
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
# 2.5 LCA问题
核心抓住中序来做，记录一下每个结点的中序位置，从根结点开始走（根左右的顺序），第一个中序位置在两个点中序位置之间的点，就是其最低共同祖先。
# 三、并查集
并查集的核心顾名思义，就是合并、查找、集合，其特殊用法可在最小生成树上体现
int father[maxn];
void init()
{
for(int i = 0;i < maxn,i++){
father[i]=i;
}
}
int findFather(int x)
{
int a = x;
while (x != father[x])
{
x = father[x];
}
while (a != father[a])
{
int z = father[a];
father[a] = x;
a = z;
}
return x;
}
//递推形式 包含路径压缩
int findfather(int a)
{
return father[a] == a ? a : (father[a] = findfather(father[a]));
}
void Union(int a, int b) {
int x = findfather(a);
int y = findfather(b);
if (x > y)
{
swap(x, y);
}
father[y] = x;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# 四、贪心算法
贪心主要有两种问题，分为简单贪心和区间贪心
**简单贪心：**比较好理解和思考；例如已有些单个数字怎样组合最大
区间贪心：
1、保证区间不相交，即任务调度
struct inteval {
int x, y;//x：开始 y：结束
};
vector<inteval> v;
bool cmp(inteval a, inteval b)
{
if (a.y != b.y)
{
return a.y > b.y;
}
return a.x < b.x;
}
int intevalUnion()
{
sort(v.begin(), v.end(), cmp);
int Lastx = v[0].x;
int ans = 1;
for (int i = 0; i<v.size(); i++) {
if (v[i].y <= Lastx) {
Lastx = v[i].x;
ans++;
}
}
return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2、区间选点，对于N个闭区间，求需要确定多少个点，才能使得每个区间至少存在一个点
几乎和上一个问题一模一样，将判断条件从 <= 改为 < 即可（因为闭区间端点的点在区间内，不需要新的点）
# 五、最短路径
PAT中30分的常考题型，主要有Dijkstra算法、Floyd算法、Bellman-Ford算法(暂时未考)
dijkstra：无负边权单源最短路径问题万能通法，可以回溯路径，选取多条件最优路径
struct node {
int v, w;
};
int dis[maxn];
vector<int> pre[maxn];
vector<node> adj[maxn];
void Dijkstra(int s)
{
fill(dis, dis + maxn, INF);
dis[s] = 0;
for (int i = 0; i < n + 1; i++)
{
int min = INF, u = -1;
for (int j = 0; j < n + 1; j++)
{
if (!vis[j] && min > dis[j]) {
u = j;
min = dis[j];
}
}
if (u == -1)
{
return;
}
vis[u] = true;
for (int j = 0; j < adj[u].size(); j++)
{
int v = adj[u][j].v;
int w = adj[u][j].w;
if (!vis[v]) {
if (dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
pre[v].clear();
pre[v].push_back(u); //记录前驱节点
}else if(dis[v] == dis[u] + w){
pre[v].push_back(u);
}
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
**Bellman-Ford算法：**如果有负边权的单源最短距离问题，dijkstra就不适用了
bool Bellman(int s,int n)
{
fill(d, d + maxn, INF);
dis[s] = 0;
for (int i = 0; i < n-1; i++)
{
for (int u = 0; u < n; u++)
{
for (int j = 0; j < adj[u].size(); j++)
{
int v = adj[u][j].v;
int w = adj[u][j].w;
if (dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
}
}
}
}
for (int u = 0; u < n; u++)
{
for (int j = 0; j < adj[u].size(); j++)
{
int v = adj[u][j].v;
int w = adj[u][j].w;
if (dis[v] > dis[u] + w)
{
return false;
}
}
}
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
SPFA算法是求单源最短路径的一种算法，它是Bellman-ford的队列优化，它是一种十分高效的最短路算法。
bool vis[maxn];
int num[maxn];
int d[maxn];
bool SPFA(int s,int n)
{
queue<int> q;
q.push(s);
d[s] = 0;
num[s]++;
vis[s] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u] = false;
for (int j = 0; j < adj[u].size(); j++)
{
int v = adj[u][j].v;
int dis = adj[u][j].dis;
if (d[v] > d[u] + dis)
{
d[v] = d[u] + dis;
if (!vis[v])
{
vis[v] = true;
q.push(v);
num[v]++;
if (num[v] >= n)
{
return false;
}
}
}
}
}
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
**全源最短距离：**当题目中结点个数在200这个量级时，可以优先考虑Floyd算法，因为算法非常简单简捷
int dis[maxn][maxn];
void Folyed() {
for (int k = 0; k <= n; k++)
{
for (int j = 0; j <= n; j++)
{
for (int i = 0; i <= n; i++)
{
if (dis[j][k] != INF&&dis[k][i] != INF&&dis[j][i] > dis[j][k] + dis[k][i])
{
dis[j][i] = dis[j][k] + dis[k][i];
}
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 六、最小生成树
最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树，主要有Prime算法、Kruskal算法两种，其是贪心算法在图论的体现。
Prime算法：可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。
struct node {
int v;
int w;
};
int n;
vector<node> adj[maxn];
int dis[maxn];
bool vis[maxn] = {false};
int prime(int s)
{
fill(dis, dis + maxn, INF);
dis[s] = 0;
int ans = 0;
for (int i = 0; i < n; i++)
{
int min = INF, u = -1;
for (int j = 0; j < n; j++)
{
if (!vis[j]&&dis[j]<min)
{
min = dis[j];
u = j;
}
}
if (u == -1)
{
return -1;
}
vis[u] = true;
ans += dis[u];
for (int j = 0; j <adj[u].size(); j++)
{
int v = adj[u][j].v;
int w = adj[u][j].w;
if (!vis[j] && dis[v] > w) {
dis[v] = w;
}
}
}
return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
Kruskal算法：此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。
const int maxe = 110;
const int maxv = 10010;
struct edge {
int u, v;
int cost;
}E[maxe];
int father[maxv];
bool cmp(edge a, edge b) {
return a.cost < b.cost;
}
int findfather(int a) {
int x = a;
while (a != father[a])
{
a = father[a];
}
while (x != father[x]) //路径压缩
{
int z = x;
x = father[x];
father[z] = a;
}
return a;
}
//n 顶点 m 边数
int kruskal(int n, int m)
{
int ans = 0, num_edge = 0;
for (int i = 0; i < n; i++)
{
father[i] = i;
}
sort(E, E + m, cmp);
for (int i = 0; i < m; i++)
{
int faU = findfather(E[i].u);
int faV = findfather(E[i].v);
if (faU != faV)
{
father[faU] = faV;
ans += E[i].cost;
num_edge++;
if (num_edge == n - 1)
{
break;
}
}
}
if (num_edge != n - 1)
{
return -1;
}
else {
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
# 七、拓扑排序
拓扑排序可以用于有向无环图的判断
int toplogical()
{
queue<int> q;
for (int i = 0; i < n; i++)
{
if (inDegree[i] == 0)
{
q.push(i);
}
}
while (!q.empty()) {
int x = q.front();
q.pop();
topOrder.push(x);
for (int i = 0; i < G[x].size(); i++)
{
int v = G[x][i].v;
int w = G[x][i].w;
inDegree[v]--;
if (inDegree[v] == 0)
{
q.push(v);
}
}
}
if (topOrder.size()==n)
{
return true;
}
else {
return false;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 八、关键路径
虽然到目前为止，关键路径没有考过，但是近年之前没考过的拓扑排序和Floyd算法都有考，故稍微了解准备一下关键路径。
1、在关键路径之前，有个最长路径的求法，在没有正环的图中，边权全部取相反数，使用Bellman-Ford算法即可。
2、而对于关键路径问题（有向无环图），除了动态规划的解法，比较常规的是使用拓扑排序。
具体过程：在拓扑排序的基础之上，进行一次正向拓扑和一次逆向拓扑，用ve[]数组和vl[]数组来更新每个事件最早和最晚的时间。
struct node {
int v, w;
};
vector<node> G[maxn];
int n,inDegree[maxn];
stack<int> topOrder;
int ve[maxn], vl[maxn];
vector<int> keyline[maxn];
int toplogical()
{
queue<int> q;
for (int i = 0; i < n; i++)
{
if (inDegree[i] == 0)
{
q.push(i);
}
}
while (!q.empty()) {
int x = q.front();
q.pop();
topOrder.push(x);
for (int i = 0; i < G[x].size(); i++)
{
int v = G[x][i].v;
int w = G[x][i].w;
inDegree[v]--;
if (inDegree[v] == 0)
{
q.push(v);
}
if (w + ve[x] > ve[v])
{
ve[v] = w + ve[x];
}
}
}
if (topOrder.size()==n)
{
return true;
}
else {
return false;
}
}
int CriticalPath()
{
fill(ve, ve + n, 0);
if (!toplogical())
{
return -1;
}
int maxLength = 0;
for (int i = 0; i < n; i++)
{
maxLength = max(maxLength, ve[i]);
}
fill(vl, vl + n, ve[n - 1]);
while (!topOrder.empty()) {
int x = topOrder.top;
topOrder.pop();
for (int i = 0; i < G[x].size(); i++)
{
int v = G[x][i].v;
int w = G[x][i].w;
if (vl[v] - w < vl[x]) {
vl[x] = vl[v] - w;
}
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < G[i].size(); j++)
{
int v = G[i][j].v, w = G[i][j].w;
int e = ve[i], l = vl[v] - w;
if (e == l)
{
keyline[i].push_back(w);
}
}
}
return maxLength;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
# 九、排序算法
# 9.1 堆排序
int heap[maxn];
//大顶堆
void update(int low, int high) {
int i = high, j = high >> 1;
while (j >= low) {
if (heap[i] > heap[j]) {
swap(heap[i], heap[j]);
i = j;
j = i >> 1;
} else {
break;
}
}
}
void downAdj(int low, int high) {
int i = low, j = low << 1;
while (j <= high) {
if (j + 1 <= high && heap[j + 1] > heap[j]) {
j++;
}
if (heap[j] > heap[i]) {
swap(heap[i], heap[j]);
i = j;
j = i << 1;
} else {
break;
}
}
}
void heapSort(int n) {
for (int i = n / 2; i > 0; i--) {
downAdj(i, n);
}
for (int i = n; i > 1; i--) {
swap(heap[1], heap[i]);
downAdj(1, i - 1);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 9.2 归并排序
void merge(int arr[])
{
for (int step = 2; step / 2 < n; step *= 2)
{
for (int i = 0; i < n; i += step)
{
sort(arr + i, arr + min(i + step, n));
}
}
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 9.3 插入排序
void insert(int arr[])
{
for (int i = 2; i < n; i++)
{
int tmp = arr[i], j = i;
while (j >= 2 && arr[j-1] > tmp) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = tmp;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 9.4 快速排序
void quickSort(int A[], int left, int right)
{
while (left < right)
{
int pos = Paritition(A, left, right);
quickSort(A, left, pos - 1);
quickSort(A, pos + 1, right);
}
}
int Paritition(int A[], int left, int right)
{
int tmp = A[left];
while (left < right)
{
while (right > left && A[right] > tmp)
{
right--;
}
A[left] = A[right];
while (left < right&&A[left] <= tmp)
{
left++;
}
A[right] = A[left];
}
A[left] = tmp;
return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33