看看自己博客这竟然是第一篇算法相关的文章……我学东西一向是有用的才学，有时候算法这东西用的时候理解上网搜一搜，但是为了准备工作，还是得系统学学，刷刷题目，背背模板之类的。感谢欧翔曦给我指了条明路，先看y总的算法基础课，总的来说第一讲效果挺好，几个模板吃透了感觉要比准备考研时候学习数据结构还清晰。反正之前无脑乱刷是真的痛苦😔。
快速排序
快排属于分治思想的一种，简单来说，就是每一趟，找一个基准点（当时考研的时候复习叫枢轴），把大于枢轴的放在一边，小于等于枢轴的放在另一边，如此再对两边进行找枢轴划分的操作……如此递归，最终得到一个有序的数列，当时复习的时候，记得快排算是不稳定的算法，时间复杂度是O(nlogn)。
快排的思想很简单，但是难点就在划分这一步怎么实现上。
这一步要是暴力来做，可以开两个额外数组，小于枢轴的扔到一个里，大于枢轴的扔到另外一个里，然后再按顺序扔回原来的数组里，完成一次划分。但是额外空间太浪费了。
课上所讲的划分方法，是指定指向数组有左右两个指针，左侧指针在保证指向数字小于枢轴的情况下向右移动，右侧指针在保证指向数字大于枢轴的情况下向左移动；两个都移不动的时候，说明左指针指向的数大于枢轴而右指针指的小于枢轴，这样一来，对两个数字进行一次交换即可，如此循环直到两个指针相遇完成一次划分。
模板如下：
#include <iostream>
using namespace std;
int n;
const int N = 1e6;
int 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;
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);
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;
}
本来在之前的模板里，枢轴选取是选的q[l]的，但是我试了一下会报段错误，有边界问题，保险起见选中间的，不会有问题。
归并排序
归并排序也是分治思想的一种体现，先找中间位置的点，分成两片，然后递归左右两边，再归并，把小的合并成大的。归并排序时间复杂度是O(nlogn)，稳定。
归并排序的难点在归并这一步，其实这一步完成了排序的操作，因为归并是一个由小合大的过程，当区间小到长度为1时，这时的小区间就是有序的，那么归并的过程就要保证小区间合成后的大区间有序性。
提出的想法是，申请一个额外数组，对归并的两个数组头部加上指针，比较两个指针指向的数字大小，数字小的加入额外数组且指针右移。如此循环直到一个数组为空，将另一个数组的余下值放入额外数组中。再将额外数组的值放回原来的数组，完成一次归并。
模板如下：
#include <iostream>
using namespace std;
int n;
const int N = 1e6;
int q[N],tmp[N];
void merge_sort(int q[],int l,int r)
{
if(l >= r) return;
int mid = (l + r) / 2;
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];
}
}
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
}
单纯的归并排序还能扩展出新的题目，像是这么一道题，求一个数列逆序数对的个数，就可以用归并的方法做，只需要在上面的模板修改以下的部分：
int count = 0;
while(i <= mid && j <=r)
{
if(q[i] <= q[j]) tmp[k++] = q[i++];
else
{
count += mid - i + 1;
tmp[k++] = q[j++];
}
}
//最后返回count即可
关于count的理解：因为归并的两部分都是有序的，用模板来说是由小到大的，那么只要左边数组里的下标为i的值大于右边的一个值的话，那么对于右边的这个值，左边从i到mid的所有值都比它大，即可组成mid - i + 1个逆序对。
二分查找（整数/浮点数）
二分查找在我印象中应该是在初中还是高中数学书中介绍的一种解方程的方法，思想很简单，确定问题的解在一个确定的区间中，找到这个区间的中间值mid，带入到问题中做判断，如此来判断解是在mid的左边还是mid的右边，这样区间就缩小了，如此重复这个过程，区间的长度越来越小，小到满足精度要求时候，就可以认为区间左右任一个断点可作为问题的解。
其实二分的应用场景不是有单调性的排列，可以说是具有某种阶段变化的序列都可以用二分来判断。所以单调序列都可以二分，但是可以二分的问题不一定是单调的。
这么理解下来，其实问题很简单，二分查找的模板可以很轻松地写一个出来：
double bsearch(double l,double r)
{
while(l < r)
{
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
return l;
}
//check(double)是一个判断函数，具体怎么实现要看实际情况
对于浮点数的情况来说，二分查找比较简单，因为不会产生边界问题，数字都是连续的，不会存在边界问题。
但是对于整数的二分，根据问题的不同，由于C/C++的整数除法是下取整的，在某些情况下会发生边界问题。所以有两个模板：
//区间被划分成[l,mid]和[mid + 1,r]时使用
int bsearch_1(int l,int r)
{
while(l < r)
{
int mid = (l + r) / 2;
if(check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
//区间被划分成[l,mid - 1]和[mid,r]时使用
int bsearch_2(int l,int r)
{
while(l < r)
{
int mid = (l + r + 1) / 2;
if(check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
这里一个难以理解的点就是在划分为[l,mid - 1]和[mid,r]的情况下为什么mid等于(l + r + 1) / 2,可以这么想，不加1的情况下，若[l,r]的长度为1，此时的(l + r) / 2即(l + l + 1) / 2，由于c/c++整数除法向下取整的特性，此时mid等于l，那么在check(mid)为true的情况下，l会等于自身，整个while循环会进入死循环的状态，所以为了避免这种情况，要加1，防止l等于自身。
其实写到这里还是有点摸不到头脑，似乎说不太清楚这两种情况究竟是什么样的，下面看这么一道题。
题目名字叫做数的范围，这道题是一个整数二分查找问题，目标数列是一个单调有序数列，要求对于输入的查询元素在数列中找到数的起始下标和终止下标。本题实现的代码如下：
#include <iostream>
using namespace std;
int n,q;
const int N = 1e6+10;
int group[N];
int main()
{
scanf("%d %d",&n,&q);
for(int i = 0;i < n;i++)
scanf("%d",&group[i]);
for(int i = 0;i < q;i++)
{
int find;
scanf("%d",&find);
int start = -1,end = -1;
int l = 0, r = n - 1;
//先找起始下标
while(l < r)
{ int mid_1 = (l + r) / 2;
if(group[mid_1] >= find) r = mid_1;
else l = mid_1 + 1;
}
if(group[l] != find)
{
printf("-1 -1\n");
continue;
}
start = l;
l = 0,r = n - 1;
//再找终止下标
while(l < r)
{ int mid_2 = (l + r + 1) / 2;
if(group[mid_2] <= find) l = mid_2;
else r = mid_2 - 1;
}
end = l;
printf("%d %d\n",start,end);
}
return 0;
}
这道题处理一个数的起始和终止位置，其实就是用了两次二分，正好用了两次上面介绍的模板。记住模板后，设计判断函数的部分决定了要用哪一个模板，一开始写可能会有点蒙，但是只要记住不同的划分情况用的模板就行了。
后记：就上面那道题我写的挺快的，结果报了半天的超时错误跑不过，结果查了半天发现是把mid写在了每个while的上面……而且设计判断函数的过程也比较痛苦，那个大于等于号和小于等于号分别归属于哪个情况，转了半天弯。还是功力太浅。
总结
这节课学了两种排序和一种查找方法，借助固定的模板，自己感觉能比较快的写出来，理解上也相比考研时候更清楚了，当时看王道的数据结构课，说实话就是过课本，写代码的能力倒是真的没有什么提高，y总的课总体来说还是不错的，让我在做算法题上有了个思路。
这是第一节课的总结，加油。