当前位置：首页 > news >正文

算法基础（以acwing讲述顺序为主，结合自己理解，持续更新中...）

news 来源：原创 2025/8/25 9:14:11

文章目录

算法的定义
一、基础算法
- 排序
- 二分
- 高精度
- 前缀和与差分
- 双指针算法
- 位运算
- 离散化
- 区间合并

算法的定义

这是我从百度上面搜的定义

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间，空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

空间复杂度： 其实也就相当于我们用了多少的内存空间

时间复杂度： 也就是执行我们这个算法所要花费的时间

在算法题中，会有对时间和空间（但是空间对我们的限制不大，往往容易卡在时间上面）的要求，所以我们学习算法，必须要了解这个算法对应的时间和空间复杂度，我们写题目的时候往往都是被时间卡了，导致超时

一、基础算法

排序

排序我们知道有很多种排序，但是最常见的其实就十大排序，分别为插入，排序，选择排序，冒泡排序，希尔排序，归并排序，快速排序，堆排序，计数排序，基数排序，桶排序.

由于本人现在学习算法只学习了快速排序和归并排序，所以先讲这两个，平常用的多的也是这两个（后续有时间再补上去）

快速排序： 快速排序的基本思路是在我们给定的数组中，随机选择数组中的某个元素，将大于这个元素的其它元素排到它的右边，小于的排到它的左边，然后递归的进行这个过程，这个递归的过程其实也用到了分治的思想，最后得到的就是我们排好序的数组

下面是代码

void sort(int q[], int l, int r)
{if (l >= r) return;int i = l - 1, j = r + 1, x = q[(l + r) / 2];while (i < j){while (q[++i] < x);while (q[--j] > x);if (i < j) swap(q[i], q[j]);}sort(q, l, j), sort(q, j + 1, r);
}

下面我来讲解一下这段代码，因为我们要用到递归所以我们要设置返回条件，也就是当l>=r的时候就返回，因为这个时候两者都指向的是一个相同的值，说明我们已经将这个数组分到最小的情况，也就是只有一个元素的情况，那么这一个元素也就是已经排好序的情况，我们直接返回就行了

我先来讲一下这个while循环的思路，再讲一下为什么用的是l-1而不是l，我们的思路其实很简单，就是我们不断让i向中间靠拢，直到遇到一个大于x的数，就停下来，因为大于x的数应该是在x的右边而不是左边，同理也让j不断向中间靠拢，最后我们交换两个数的位置就可以了，那么这个循环结束后，x的左边都是小于等于它的，右边都是大于等于它的

那为什么这里用的是l-1呢，因为当我们交换完后，我们需要让 i 指向下一个元素，让j指向它前面的一个元素，所以交换完后要先让 i 进行加一操作，j 进行减一操作，因为我们需要从第一个元素开始比较，所以要让 i 变成 l-1，这样加1后就指向的是我们数组的第一个元素位置

最后进行递归的操作就可以得到我们排好序的数组了

快速排序它因为用到了递归的过程，而我们知道递归是非常占用内存的，所以当数据输入量很大的时候，可能会出现内存不足的情况，并且快速排序在某些情况下时间复杂度是O（n的平方），最优的时间复杂度是（nlogn），这取决于我们函数里的中间值怎么取（也就是x变量），如果取的不好，时间复杂度也很高

那么接下来我就来介绍一个时间复杂度稳定的排序，那就是归并排序

归并排序： 归并排序的时间复杂度是O（nlogn），很稳定，因为在递归的过程，每次都将数组分为两个子块（不论什么情况），但是归并排序需要额外开一个和数据大小相同的数组用来作为中间变量存放我们排好序的值。

文章目录

算法的定义

一、基础算法

排序

二分

高精度

前缀和与差分

双指针算法

位运算

离散化

区间合并

相关文章：