主要思想掌握，深刻的理解
代码模板理解以及背过（掌握思想）
模板题目练习
理解 + 记忆
快速排序的主要思想是基于分治的，第一步就是是确定分界点，重点是调整范围。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
void quick_sort(int q[], int l, int r)
{
if (l >= r) return ; // 如果数组一个数都没有或者只有一个数，就不用排序、
//设置两个指针，以及分界点x
int x = q[l], i = l - 1, j = r + 1; //这里两个指针我们设置在数组外，这样我们可以不管，直接让二者都往里面走
//开始循环
while (i < j)
{
//只有两个指针没有碰到才可以继续走
do ++i; while (q[i] < x); //当 q[i] < x就继续往下走
do --j; while (q[j] > x); //当q[j] > x就继续往下走，直到j指针指到一个<=x的数，说明应该放在左边
//判断i, j两个指针未碰到就可以交换
if (i < j) swap(q[i], q[j]);
}
//一次循环结束后，分界点x归位，接着继续分别递归左右两边
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
int main ()
{
scanf ("%d",&n); // 输入有几个数
for (int i = 0; i < n; ++i)
{
scanf ("%d",&q[i]); // 输入数组
}
// 快速排序
quick_sort(q, 0, n - 1);//范围0 - n-1
for (int i = 0; i < n; ++i) printf ("%d ",q[i]);
printf ("\n");
return 0;
}
quick_sort中注意一下：写i，最好就不要用q[l]，否则会有边界问题，改成i，如下：
int x = q[r];
//或者
int x = q[(l + r + 1) / 2]; // 一定要上取整，一定不能取到l这个边界上
quick_sort(q, l, i - 1);
quick_sort(q, i, r);
//当我们这里用i时，一定不能取到l左边界，否则就会死循环
举个实例，思考一下：
/*
例如：
2
1 2
*/
- 这时若是x = q[l]，则是x = 1;
- 首先，i指向第一个点1前面，j指向第二个点2后面
- 用的是 do-while 两个指针都会先++移动一下
- 第一个点不满足小于x，i++，指向第一个点1;
- 第二个点满足大于x,且之前++ 过了，再往前走，指向第一个点1，两个指针相遇
- 此时i=0，等于左边界l;
- 此时 quick_sort(q, 0, -1); // 左边没有数，结束了
- 此时 quick_sort(q, 0, 1); // 下次还会是[0, 1]
- 就会一直死循环，无限递归下来
- 边界问题
- 同理用j的时候就不要用r(左不对左，右指针不对右边界)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
void quick_sort(int q[], int l, int r)
{
if (l >= r) return ;
int x = q[r];
int i = l - 1;
int 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]);
}
quick_sort(q, l, i - 1);
quick_sort(q, i, r);
}
int main ()
{
scanf ("%d", &n);
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]);
}
printf ("\n");
return 0;
}
基于思想： 分治
双指针，分别指向两个需要合并的数组；
然后，分别将两个指针指向的数字对比，较小的放在最终的结果数组里面，然后指向较小数的那个指针后移，接着比对，重复此过程；
不断比对，指针不断往后移；若是其中一个指针指到末尾（无），而另一个指针指向的数组还有剩下，则将这些全部放到结果数组中（说明这些就是大的数）
稳定是指：原序列中两个数的值是相同的话，在排完序后相对位置要是不发生变化的话，排序就是稳定的
归并排序稳定，快速排序一般不稳定；
快排平均时间复杂度：O(nlogn);
归并排序：O(nlogn)；n / log2n次2才等于1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N]; //数据
int temp[N]; //存放临时数据数组
void merge_sort(int q[], int l, int r)
{
if (l >= r) return; //如果数组里面只有一个数据或者没有，直接返回退出函数
//先确定分界点
int mid = l + r >> 1; // 位运算 /2
//递归排序左右两边
merge_sort(q, l, mid); //递归排序左边
merge_sort(q, mid + 1, r); //递归排序右边
//归并
int k = 0; //归并的个数
// 两个指针
int i = l;
int j = mid + 1;
// 分别指向排完序的左右半边，接着进行合并
//合并是对有序的数组合并
while (i <= mid && j <= r)
{
// 如果i指针指向的数小于j指针指向的数，则将i指向的数插入临时数组里面，i与k往下走
//同理 j k
if (q[i] <= q[j]) temp[k++] = q[i++];
else temp[k++] = q[j++];
}
// 当i还没有走完，j以及结束了，则把剩余的数组放在临时数组temp中
while (i <= mid) temp[k++] = q[i++];
// 同理 右半边
while (j <= r) temp[k++] = q[j++];
//把临时数组整理 ，重新赋值回q数组中
for (i = l, j = 0; i <= r; ++i, ++j)
{
q[i] = temp[j];
}
}
int main ()
{
scanf ("%d", &n);
for (int i = 0; i < n ; ++i)
{
scanf ("%d",&q[i]);
}
merge_sort(q, 0, n - 1);
for (int i = 0; i < n ; ++i)
{
printf ("%d ",q[i]);
}
printf ("\n");
return 0;
}
本质：与单调性无关，但是有单调性一定有二分。【可以二分的题目不一定有单调性】；
二分的本质是边界，假设给我们一个区间，然后在这个区间上定义了某种，使得这个性质在右半边是满足的，在左半边是不满足的；
整个区间可以被一分为二；
只要整个区间里可以找到这个性质，就可以用二分把这个边界点二分出来；
假设想二分出绿颜色这个点；
step one：先让中间点mid = （l + r) / 2;
假设性质是绿色这个性质，那么先检查mid是否满足绿色这个性质，if (check(mid));
若是true， 则mid 在绿色块区间，边界点所在区间为[l, mid]；【r = mid】;
若是false，则mid 在红色块区间，边界点所在区间为[mid + 1, r]；【l = mid + 1】;
若是这两个区间【mid在左半边】，则mid = (l + r) / 2；
（C++中整数除法下取整）
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int q[N];
int main ()
{
scanf ("%d%d",&n, &m);
for (int i = 0; i < n; ++i)
{
scanf ("%d", &q[i]);
}
// 要查找的数的起始位置和终止位置
while (m--)
{
int x;
scanf ("%d", &x);
// 初始区间的范围
int l = 0, r = n - 1;
// 寻找起始位置边界
// 思考check函数
while (l < r)
{
int mid = l + r >> 1;
//数组升序排列
// 若是q[mid]的值比x大 ，则x在左半边，r = mid
if (q[mid] >= x) r = mid;
else l = mid + 1;
}
// 新 l == r
//从循环出来，若 ！=x则无这个数
if (q[l] != x) cout << "-1 -1" << endl;
else
{
cout << l << ' ';
int l = 0;
int r = n - 1;
while (l < r)
{
int mid = l + r + 1>> 1;
// 找终止位置，则换一个check判断；【完了之后还要看看mid】
// 若为true ，则说明边界点在右半边
if (q[mid] <=x)
{
l = mid;
}else r = mid - 1; //则前面 int mid = l + r + 1>> 1;
}
// 其实出循环，l与r就会碰到
cout << l << endl;
}
}
return 0;
}
在一个区间内部，去二分我们的边界，【每一次会把长度缩写一半】每一次都要选择答案所在的区间去进行下一步的处理;（每一次都能 保证我们的区间里有答案，答案都会被区间覆盖掉）
当我们区间是1的时候，这个区间里的数就一定是答案；
二分时（模板）一定是有解的；无解是相对于题目来说的，比如ACwing 789这一个例子；（我们定义的这个性质是一定有边界的，一定能把这个边界二分出来）
//求平方根
#include <bits/stdc++.h>
using namespace std;
int main()
{
// 输入待求平方根的数
double x;
cin >> x;
// 确定边界
double l = 0;
double r = x;
// 因为是浮点数，不能简单的用 =
// 当 r - l <= 1e-8 认为“相等”跳出循环
while (r - l > 1e-8)
{
double mid = (l + r) / 2; //先找出mid
if (mid * mid >= x)
{
// 说明平方根在左半边 比 mid 小 但满足可以取到mid
r = mid;
}
else
{
// 否则，直接让l = mid 就行，因为是浮点数
l = mid;
}
}
// %lf 默认是6位，所以前面是1e-8(比要保留的个数多两位，比较保险)
printf ("%lf", l);
}