本节内容为部分排序和查找算法，数据结构课讲过，不过当时期末时间紧，没去听课，虽然PPT看懂了，但是从没有自己完整敲过，现在原理也都忘了，学一遍发现确实有些地方容易写错。

快速排序

核心思路

主要思想：分治

1. 确定分界点：q[l]或者q[(l+r)/2]或者q[r]；
2. 调整范围：目标是左边的数都小于等于x，右边的数都大于等于x（分界点不一定是x）；
3. 递归处理左右两端

第2步实现

暴力算法

1. 开两个数组a[ ]和b[ ]；

2. 把q[ ]中从l到r遍历：

   • q[i]<=x 放入a;
   • q[i]>x 放入b;
3. 把a[ ]和b[ ]放入q[ ]中

常用思路

1. 设定两个指针，从左右两端开始：

   • 左指针从左向右寻找第一个大于等于基准的元素
   • 右指针从右向左寻找第一个小于等于基准的元素
2. 找到之后交换两个元素

3. 持续移动左右指针并交换元素，直到两个指针相遇，此时结束

阅读全文

基本工具

编译器选项

-std=c++11

文件读入

#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif

快速读入

inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

阅读全文