y总的算法基础课——第一讲
内容过大,食用量警告!!!
- 快速排序
快速排序是分而治之的思想,基本上在排序算法中快速排序的优先级很高,但是快速排序的边界问题要处理的东西很多也很复杂,所以能把模板背下来就是最好的了。- 找到分界点
- 调整区间
- 递归处理左右两边
ps:快速排序并不稳定
pps:稳不稳定其实对于排序算法没什么用
ppps:快排可以通过二元组的形式变得更稳定
#include <iostream> const int N = 100010; int n, q[N]; void quick_sort(int q[], int l, int r) { if (l == r) return; int x = q[(l + r) / 2], i = l - 1, j = r + 1; // 关于分界点的选择,选择两端在某些case情况下会超时 while (i < j) { do i ++ ; while(q[i] < x); do j -- ; while(q[j] > x); if (i < j) swap(q[i], q[j); } quick_sort(q, l, j); quick_sort(q, j + 1, r); } int main() { scanf("%d", &n); // 因为数据量比较大,scanf大概能比cin要快十倍 for (int i = 0; i < n; i ++ ) scanf("%d", q[i]); quick_sort(q, 0, n - 1); for (int i = 0; i < n; i ++) printf("%d ", q[i]); return 0; }
2.快速选择算法
快速选择算法是基于快速排序算法的基础上,为了提高速度找到TOP k的数而改进的算法
int quick_selection(int l, int r, int k) { if (l == r) return q[l]; int x = q[l + r>>1], i = l - 1, j = r + 1; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } int sl = j - l + 1; if (k <= sl) return quick_selection(l, j, k); return quick_selection(j + 1, r, k - sl); }
- 归并排序
归并排序也是一种很优雅的排序方式呀,并且排序结果很稳定,同快排一样用到的是分而治之的算法思想。
但是,归并的递归入口是在前,快排的递归入口是在后,而且合并的部分也需要额外注意。
int q[N], tmp[N]; // 注意到归并排序需要额外的内存空间 void merge_sort(int q[], int l, int r) { if (l >= r) return; // 这个判断语句很关键,维持最小的组大于一个元素 int mid = l + r >> 1; merge_sort(q, l, mid); merge_sort(q, mid + 1, r); int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) { if (q[i] <= q[j]) tmp[k++] = q[i++]; else tmp[k++] = q[j++]; } while (i <= mid) tmp[k++] = q[i++]; while (j <= r) tmp[k++] = q[j++]; for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j]; }
- 二分查找算法
整数二分:
二分的本质并不是单调性
二分的本质是找到确定条件的边界 y总这句话说的真的好,二分本质只需要两个模板,一个是下确界的,而另一个,就是上确界的。
有两个模板,我们可以通过一道题来理解他。
给定一个按照升序排列的长度为 n 的整数数组,以及 q 个查询。
对于每个查询,返回一个元素 k 的起始位置和终止位置(位置从 00 开始计数)。
如果数组中不存在该元素,则返回
-1 -1
。
#include <iostream> using namespace std; const int N = 100010; int n, m; int q[N]; int main() { scanf("%d%d", &n, &m); // 在大数据的情况下,scanf要比cin快十倍 for (int i = 0; i < n; i ++) scanf("%d", &q[i]); while (m--) { int x; scanf("%d", &x); int l = 0, r = n - 1; while (l < r) { int mid = l + r >> 1; // 如何进行更新,以及这个地方是否需要取上界即+1 要考虑一下 if (q[mid] >= x) r = mid; // 这个check条件,也影响二分的更新方式,这个是在找下确界 else l = mid + 1; } if (q[l] != x) cout << "-1 -1" << endl; else { cout << l << ' '; int l = 0, r = n - 1; // 找另一个上确界 while (l < r) { int mid = l + r + 1 >> 1; // 这里为什么要+1,是因为mid取值为左侧 if (q[mid] <= x) l = mid; else r = mid - 1; } cout << l << endl; } } return 0; }