前言
忽然想起自己考前还报了一个acwing的课,似乎内容比洛谷的还多,报名人数3.5w不是瞎说的。
(听完第一节课感觉讲的甚至比RXZ还好。)
排序
快排
之前已经在很多地方学习过了,RXZ与yxc所说的暴力方法有点不一样,但是很相似,是不得已才使用的。
暴力方式
暴力的方式是指重新开一个数组,将小于哨兵的放入排序数组,大于哨兵的放入tmp数组,放完大于后从tmp数组中取出大于哨兵的放入排序数组。这样做常数有点大。
优美的方法
yxc讲一个非常优美的做法,起初有2个指针,l和r分别在区间头部和区间尾部。
当l指向的数小于哨兵时,继续移动,直到遇到大于哨兵的数为止。
此时开始移动r指针,当r指向的数小于哨兵时停止。
此时将l和r指向的数交换。
是不是非常优美,常数也不大,要付出的代价只是指针的移动罢了。
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + 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]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
归并排序
RXZ也讲过可以看我另外一篇blog:RXZ讲的归并排序](https://blog.loveoi.net/OI/OI-Course/course-day-3/#O-nlogn-的实用算法))
真贴心,还指出了归并与快排的区别。
- 归并:先递归后排序
- 快排,先排序后归并
当然归并的稳定排序,快排的不稳定排序(毒瘤数据可以退化成$O(n^{2})$)。
在递归后我们有2个有序序列A,B。
A,B各有一个指针i,j起初分别指向两个序列的头部。
此时两个指针指向的数就是两个序列中的最小值,此时将他们比大小,最小值即为两个序列的最小值。
将其填入tmp数组,最后回填即可,和RXZ讲的类似。
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];
}
二分
整数二分
和RXZ的统一二分不同,这个是"学院派"二分,时间复杂度比通用稍小,容易写炸,但是我们还是要学习一下.
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
往左边二分和往右边二分的两种方式.
浮点二分
多两个精度上模板即可
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度,取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
This post was written on August 11, 2022 at 23:03.