主要讲了三个基础算法的思想和模板,以及一些例题
基础算法思想和模板
快速排序
思想:对于所要排序的区间,设置两个指针为 i(初始值为 l-1 ) 和 j(初始值为 r+1 ),以及一个枢纽值(一般取中间位置的值),将 i 和 j 移动到可以进行交换的地方(i 位置的值大于枢纽值时可交换,j 位置的值小于枢纽值时可交换),进行交换,直至 i 与 j 相遇( 满足i>=j )。
然后对由i(或者 j )分割开的左右两个区间分别进行快速排序。
#include <iostream>
#include <algorithm>
const int N = 1000010;
int n;
int q[n];
using namespace std;
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, i);
quick_sort(q, i+1, r);
}
int main(void)
{
scanf("%d", &n);
for(int i=0; i<n; i++) scanf("%d", &q[i]);
quick_sort(q, 0, n-1);
for(int i=-; i<n; i++) printf("%d ", q[i]);
return 0;
}
模板中需要注意的几个边界问题
1. 循环的大条件是while(i<j)
,而不是while(i<=j)
2. 判断左移和右移是<
和>
而不是<=
和>=
以上两个地方从思路上来考虑没有问题,但是在实际数据中运行可能会导致无限循环,所以要记得这两个地方。
归并排序
思想:对于所要排序的区间,设置两个指针 i(初始值为区间左边界 l)和 j(初始值为区间中间位置 l+r>>1),两者后移时将所指向的较小值放入 tmp[] 数组,直至 i==mid 或者 j==r,然后把左半边或者右半边剩余的全部移进 tmp[] 数组,实现排序,最后把 tmp[] 数组中的元素拷贝到原数组的[l, r]区间。
注意,递归的位置在排序之前。
#include <iostream>
const int N=1e6+10;
int n;
int q[N],tmp[N];
using namespace std;
void merge_sort(int q[], int l, int r)
{
if(l>=r) return;
int mid=l+r>>1;
int i=l, j=mid+1, k=0;
merge_sprt(q, l, mid);
merge_sort(q, mid+1, r);
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];
}
int main(void)
{
scanf("%d", &n);
for(int i=0; i<n; i++) scanf("%d", &q[i]);
merge_sort(q, 0, n-1);
for(int i=-; i<n; i++) printf("%d ", q[i]);
return 0;
}
模板中需要注意的几个问题
1. 递归在排序之前
2. i=l, j=mid+1
3. tmp[] 数组从0开始存放和拷贝
二分查找
思想:对于一个区间,如果某种性质能够将区间分为前后两个部分(check()为True和False),那么可以用递归的方式找到满足与不满足的分界点,递归的方式是逐步地缩小查找的区间,并且每次只check此区间中间位置的值是否满足,注意这里“递归”的实现是循环。
bool check(int x) // 检查是否满足某种性质
{
/* ... */
}
int bsearch_1(int l, int r)
{
while(l<r)
{
int mid= l+r >> 1;
if(check(mid)) r=mid;
else l=mid+1;
}
return l;
}
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)// 检查是否满足某种性质
{
/* ... */
}
double bsearch_3(double l, double r)
{
const double eps = 1e-6;
while(r-l>eps)
{
double mid = (l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
return l;
}
需要注意的问题
1. 如果所写的check()函数为 True 时,需要将 l 更新为 mid,那么 mid 应该用 l+r+1 >> 1(原因可能是正整数移位取整是向下取整,不+1 可能会导致 l=l,从而导致无无限循环)