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

算法的定义

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

算法（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），很稳定，因为在递归的过程，每次都将数组分为两个子块（不论什么情况），但是归并排序需要额外开一个和数据大小相同的数组用来作为中间变量存放我们排好序的值。

归并排序的基本思路：首先就是二分，不断的进行二分，直到分到只剩一个元素的时候，那么一个元素说明已经排好序了，就直接返回（也就是l==r），更前面的快速排序返回条件一样，只不过快速排序是先排序后递归，归并排序是先递归后排序，下面是代码

void sort(int q[],int tmp[], int l, int r)
{if (l >= r) return;int mid = (l + r) / 2;sort(q, tmp, l, mid),sort(q, tmp, 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];
}

因为用到了递归，所以一开始我们就要设置返回条件，之后算出我们的中间位置，也就是mid的值，之后进行分治，将数组划分为更小的子数组，我还是重点讲一下这个循环

这个循环就是将我们划分的左边数组的值与右边数组的值进行比较，结果小的就放入我们的中间数组tmp里面，当我们左边的数组或者右边的数组的值都放完的时候就结束了循环，这时由于我们有一边的值肯定没有放完，但是我们不确定是哪一边的值，所以使用了两次while循环，将剩下的元素放进我们的tmp数组里，将值放进tmp数组里的过程也就是合并操作，最后将tmp数组的里的值赋值到原来数组的位置，我举个例子大家应该能更加容易理解

假设一开始原始数组的值为1 5 6 2 4，那么当我们进行归并的时候，这时我们中间值mid为2（假设数组的下标从0开始），i为0，j为3对应的值为3，那么我们就开始进行比较，第一次循环后tmp数组里的值为1，第二次循环后的值为 1 2，第三次为 1 2 4，这时我们看到mid右边值都已经放进我们的tmp数组里了，j为5，这时i为1，左边数组的值并没有放完，那么我们就进行while循环，直接将值放进tmp数组里（这里有些人可能会问了，那会不会出现左边的值并没有排好序的情况呢，不会，因为我们是一开始就进行递归，递归到只剩一个元素时才返回，那么每次返回后将排好序的进行合并，那么就保证了返回后我们的子数组一定是排好序的），我们最后得到的tmp数组就是1 2 4 5 6，最后将值重新返回我们原来的数组里，得到的就是我们排好序的数组了

二分

高精度

前缀和与差分

双指针算法

位运算

离散化

区间合并