基础算法（排序、二分、精度运算）

编程入门行业动态更新时间:2024-10-26 06:32:52

基础算法（排序、二分、<a href=https://www.elefans.com/category/jswz/34/1769184.html style= 精度运算）"/>

基础算法（排序、二分、精度运算）

这里写目录标题

排序
- 快速排序
- - 主要思想
  - 解法
  - 其它细节
- 归并
- - 主要思想
  - 解法
- STL - sort
- 总结时间效率
二分
- 整数二分
- - 主要思想
  - 解法
  - 举例：
  - - 起始位置
    - 结束位置
- 浮点数二分
- - 解法
- 二级目录
一级目录
- 二级目录
- 二级目录
- 二级目录
一级目录
- 二级目录
- 二级目录
- 二级目录
一级目录
- 二级目录
- 二级目录
- 二级目录

排序

快速排序

主要思想

解法

1、暴力

开辟新数组遍历之后将小的放在一个数组里大的放在一个数组里最后将两个数组合并到总数组里

2、双指针

i在左边 j在右边二者同时向中间移动但i的值大于等于x时就停下 j的值小于等于x时就停下两个都停下之后交换两个的值之后两者再次同时向中间移动然后继续这个过程直到i到了j的右边（或者说j 到了i 的左边）

模板：

main函数中第一次调用模板时传入 0 n-1（也就是两个边界的下标）因为是向函数传入左右边界值以供使用参数就是 l r

模版就是那个quick_sort函数
第一行是判断边界如果里面没有数或者只有一个数那么直接return

之后选定left为分界点之后初始化i 和 j的位置

然后在while循环里进行do … while 循环
第一个do i++；while （q[i]<x）意思是只要q[i]<x 那么就会一直在这一行执行也就是i会一直++
第二个就是只要满足 q[j]>x 那么就会让j–

之后再判断（i<j）交换 i j 所指向的数据因为只有上面两个do … while跳出才能到if 所以这里是指 i j 都停下了进行if判断并交换符合解题逻辑

最后递归依次递归左边区间以及右边区间以 j 为分界点
quick_sort(q,l,j);
quick_sort(q,j+1,r);

(注意当递归时传入j时（例如第一个递归的第三个参数）上面的int x后面必须是q【l】一定不可以是r)

其它细节

这个表示一百万 100 0000 + 10
所以一百万就是 1e6
+10 是因为预留一些空间防止越界

根据题目的数据范围来定义数组的大小

归并

主要思想

首先是两个有序的序列数组从小到大排列之后两个指针依次指向两个数组的最小值也就是最左端然后比较两个指针的值将较小值放入res数组然后谁放入了res 谁的指针后移一位之后再次比较直到某个指针到了最后那么进行完这次比较之后将另一个没有比完的数组依次接在res的最后

当两个数相同时一般是让第一个序列的指针所指的数放入res

快排以及归并的时间复杂度都是n*log n

解法

模板：

首先传入q 0 n-1 也就是数组左边界右边界

之后在merge_sort函数里面

第一行判断边界

之后确定分界点使用 l + r / 2 可以写成 l + r >> 1 这样更快一些

紧接着就分成两个数组递归调用以mid为分界点 l mid 以及 mid+1 r

之后开始合并首先要定义一个k 用来记录tmp数组的下标之后i指向l j指向mid+1 也就是都指向两个数组的第一个位置
while循环：当i j 都没出去最后时循环继续 if 选出较小值放入临时数组tmp
当第一个循环结束进入第二个循环这时已经有其中一个数组比较完了所以就判断是谁还有值将剩下的值拼接到tmp数组后面即可

最终for循环将tmp数组的数赋值回q数组因为最后输出的是q数组如果不想赋值直接该输出函数是tmp即可

STL - sort

#include

传入两个指针指向第一个元素以及最后一个元素用数组名代替首元素指着之后q+n指向了最后一个元素

总结时间效率

快速排序归并排序 STL-sort 三者时间差不多

二分

整数二分

主要思想

图中两个指针所指的点可以认为是两个目标点左边是红色区间边界点右边是黄色区间的边界点
假如要找红色的那个点那么就是第一种情况首先让mid = r + l >> 1
之后看mid是否满足在红色区间如果在那么目标值红点在mid右边所以mid左边可以丢掉但是mid不能丢掉因为mid在有效区间内所以 L = mid

如果mid不满足在红色区间那么目标值在mid左边并且mid在绿色区间不可能取到目标值所以直接丢掉mid右边以及mid r=mid-1

然后这个就是下面“解法一栏”的第二个模板看到 L=mid的更新就回过头把mid改成 r+l +1 >> 1

假如要找绿色区间边界点简称绿点也就是把绿点当做目标值首先让mid= r + l >> 1
之后看mid是否满足绿色区间如果满足那么目标值在mid左边那么更新r=mid
else mid在红色区间目标值在mid右边更新 l = mid +1

解法

模板：

思考过程
首先先写mid = l + r >> 1
之后写check（）函数或者直接判断也可以总之要有一个判断mid在目标值左还是右
之后看满足第一种情况还是第二种
如果是更新了 l=mid 那么回过头来修改mid 在mid的分子上 + 1
如果是更新了 r=mid 那么就无需修改mid

举例：

这里让找每个查询元素的起始位置以及终止位置那么我们这里只看某一个查询元素即可

起始位置

首先来找起始位置：
对于一个x 假设我们定性质为 >=x
这样就符合找绿点的情况

最外层while是指m个查询所以循环体里就是一个查询的代码
目标值用一个变量表示因为一般都是程序来输入目标值我们来查找

首先初始化 l 和 r 的位置分别是 0 n-1
之后while（l<r）循环条件是l<r 因为当l = r时就是要找的值
在小循环里首先定义mid
之后因为要查询绿点所以 q[mid] >= x
如果为真那么 r = mid
else l = mid + 1

结束位置

之后找右边坐标可以理解为右边界

这里插播一下无解的情况如果最后的结果不是x （如果不是那么q【l】的值就是>x的第一个值）那么就是无解直接返回无解的值

这里就是找红点的情况
首先check就是q【mid】<=x 更新 l = mid
else r = mid - 1
这里看到更新的是 l = mid
所以回去修改mid = r + l + 1 >> 1

最后输出 l 其实输出 l 还是 r 都一样因为循环最后跳出的条件就是 l = r