voidunion(int p, int q){ int pid = find(p); int qid = find(q); // p和q已经在相同的分量之中 if (pid == qid) return; // 将p的分量重命名为qid for (int i = 0; i < id.length; ++i) { if (id[i] == pid) id[i] = qid; } }
2-2 quick-union
轨迹:
思想: 每次联通时只联通根节点
访问id数组的次数:
(每调用一次root(node)需要访问数组的次数为node的树深)
1 2 3 4 5 6 7 8 9 10 11 12 13
intfind(int p){ // 找根结点 while (p != id[p]) p = id[p]; return p; }
voidunion(int p, int q){ int proot = find(p); int qroot = find(q); if (proot == qroot) return; id[proot] = qroot; }
2-3 weighted-quick-union
思想: 利用一个sz数组记录每棵树的大小, 并总是将较小的树连接到较大的树上
访问数组的次数(id数组和sz数组):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
intfind(int p){ while (p != id[p]) p = id[p]; }
voidunion(int p, int q){ int proot = find(p); int qroot = find(q); if (proot == qroot) return; if (sz[proot] < sz[qroot]) { id[proot] = qroot; sz[qroot] += sz[proot]; } else { id[qroot] = proot; sz[proot] += sz[qroot]; } }
quick-union和weighted-quick-union的对比:
2-4 路径压缩+quick-union
思想: 在查找根节点的同时将每个结点直接指向上上一级结点, 以达到扁平化的效果
1 2 3 4 5 6 7
intfind(int i){ while (i != id[i]) { id[i] = id[id[i]]; // 核心 i = id[i]; } return i; }
2 归并排序
作业: 2.2.2 2.2.3 2.2.4 2.2.5 2.2.8
1 | 原地归并的抽象方法
merge(int[] a, int lo, int mid, int hi) -> 将a[lo..mid]和a[mid + 1, hi]归并为有序的a[lo…hi]
思想: 利用一个辅助数组将a复制一份然后依次比较
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
int i = lo, j = mid + 1; for (int k = lo; k <= hi; ++k) { aux[k] = a[k]; } for (int k = lo; k <= hi; ++k) { if (i > mid) a[k] = aux[j++]; elseif (j > hi) a[k] = aux[i++]; elseif (aux[j] < aux[i]) a[k] = aux[j++]; else a[k] = aux[i++];
}
2 | 自顶向下的归并排序
思路: 递归
核心代码:
1 2 3 4 5 6 7
voidsort(int a[], int lo, int hi){ if (hi <= lo) return; int mid = lo + (hi - lo) / 2; sort (a, lo, mid); sort (a, mid + 1, hi); merge(a, lo, mid, hi); }
轨迹: (trace)
3 | 自底向上的归并排序
思路: 先两两归并, 再四四归并…..
核心代码:
1 2 3 4 5 6 7 8
voidsort(int a[]){ int N = a.size(); aux = newint[N]; for (int sz = 1; sz < N; sz *= 2) { for (int lo = 0; lo < N - sz; lo += sz * 2) merge(a, lo, lo + sz - 1, min(lo + sz + sz - 1, N - 1)); } }
轨迹:
3 快速排序
作业: 2.3.1 2.3.2 2.3.3 2.3.4 2.3.5
1 | 算法
1 2 3 4 5 6
voidsort(int []a, int lo, int hi){ if (hi <= lo) return; int j = partition(a, lo, hi); //进行切分 sort(a, lo, j - 1); sort(a, j + 1, hi); }
partition
切分使得数组满足如下条件:
对于某个j, a[j]已经确定
a[lo]到a[j-1]的所有元素不大于a[j]
a[j+1]到a[hi]的所有元素不小于a[j]
实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
intpartition(int []a, int lo, int hi){ int i = lo, j = hi + 1; int v = a[lo]; // 切分元素 while (1) { while (a[++i] < v) if (i == hi) break; // 从左到右找到一个 >= v的元素 while (v < a[--j]) if (j == lo) break; // 从右到左找到一个 <= v的元素 if (i >= j) break; swap(a, i, j); // 交换元素 } swap(a, lo, j); // 将切分元素放到对应位置 return j; // 返回切分元素的索引 }
2 | 算法改进
乱序
在每次排序之前将数组打乱并随机选取切分元素保证随机性
在小数组时候切换到插入排序
对于小数组而言, 插入排序比快速排序快
将
1
if (hi <= lo) return;
改为
1 2 3 4
if (hi <= lo + M) { insertion.sort(a, lo, hi); //切换到插入排序 return; }
intpartition(vector<int>& a, int lo, int hi){ int i = lo, j = hi + 1; int v = a[lo]; // 切分元素 while (1) { while (a[++i] < v) if (i == hi) break; // 从左到右找到一个 >= v的元素 while (v < a[--j]) if (j == lo) break; // 从右到左找到一个 <= v的元素 if (i >= j) break; swap(a[i], a[j]); // 交换元素 } swap(a[lo], a[j]); // 将切分元素放到对应位置 return j; // 返回切分元素的索引 }
voidqsort(vector<int>& a, int lo, int hi){ if (lo >= hi) return; int j = partition(a, lo, hi); cout << "lo: " << lo << " hi: " << hi << " j: " << j << endl; qsort(a, lo, j - 1); qsort(a, j + 1, hi); }
intmain(){ vector<int> a{'E','A','S','Y','Q','U','E','S','T','I','O','N'}; qsort(a, 0, a.size() - 1); for (char i : a) { cout << i << " "; } }
/* lo: 0 hi: 11 j: 2 lo: 0 hi: 1 j: 1 lo: 3 hi: 11 j: 11 lo: 3 hi: 10 j: 4 lo: 5 hi: 10 j: 10 lo: 5 hi: 9 j: 5 lo: 6 hi: 9 j: 7 lo: 8 hi: 9 j: 9 A E E I N O Q S S T U Y */
2.3.3
2.3.4
顺序就是最坏情况
2.3.5
进行一次三向切分即可
4 | 各个排序的比较
4 优先队列
作业: 2.4.5 2.4.7 2.4.9 2.4.18
下面代码以最大堆为例, 给出c++的实现
1 | 下沉和上升
1 2 3 4 5 6 7 8
// 元素的上升swim // 实现: 当子节点大于父节点时将二者交换 voidswim(vector<int>& a, int k){ while (k > 1 && a[k / 2] < a[k]) { swap(a[k / 2], a[k]); k = k / 2; } }
1 2 3 4 5 6 7 8 9 10 11 12
// 元素的下沉sink // 实现: 当父节点值小于子节点时与子节点的较大者交换 voidsink(vector<int>& a, int k){ int N = a.size() - 1; while (k * 2 <= N) { int j = k * 2; if (j < N && a[j] < a[j + 1]) ++j; if (a[k] >= a[j]) break; swap(a[k], a[j]); k = j; } }
2 | 插入和删除最大元素的实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
// 插入 // 实现: 数组末尾加入一个元素后进行上浮操作 voidinsert(vector<int>& a, int k){ a.push_back(k); swim(a, a.size() - 1); }
voidswim(vector<int>& a, int k){ while (k > 1 && a[k / 2] < a[k]) { swap(a[k / 2], a[k]); k = k / 2; } }
voidsink(vector<int>& a, int k){ int N = a.size() - 1; while (k * 2 <= N) { int j = k * 2; if (j < N && a[j] < a[j + 1]) ++j; if (a[k] >= a[j]) break; swap(a[k], a[j]); k = j; } }
voidinsert(vector<int>& a, int k){ a.push_back(k); swim(a, a.size() - 1); }