基础算法

算法是程序的灵魂，是程序的核心。算法的好坏直接影响程序的性能。因此，学习算法是每一个程序员必须要做的事情。本文将对常用的算法进行整理，方便自己查阅，也方便他人参考。

搜索

搜索：以某种特定的方法，枚举状态空间中的状态，直到找到问题的解为止。
从一个起始状态出发，通过给定的规则寻找后继状态，到达终止状态时不继续拓展

搜索树

搜索树：搜索过程中的状态可以用树来表示，这棵树就是搜索树。搜索树的每个节点表示一个状态，根节点表示初始状态，叶子节点表示终止状态，中间节点表示中间状态。搜索树的每条路径表示一种状态转移的序列，从根节点到叶子节点的路径表示一种解的方案。

深度优先搜索与广度优先搜索

深度优先搜索：从起始状态出发，每次选择一个未被访问过的后继状态，直到无法继续为止，然后回退到上一个状态，继续选择另一个未被访问过的后继状态，直到找到问题的解为止。
广度优先搜索：从起始状态出发，每次选择所有未被访问过的后继状态，直到无法继续为止，然后回退到上一个状态，继续选择所有未被访问过的后继状态，直到找到问题的解为止。

搜索剪枝

搜索剪枝：为了减少搜索的状态数，可以在搜索过程中删除一些状态，这个过程就是搜索剪枝。

可行性剪枝与最优性剪枝

可行性剪枝：在搜索过程中，如果发现某个状态的后继状态一定不是问题的解，那么就可以将这个状态从搜索树中删除，这个过程就是可行性剪枝。
最优性剪枝：在搜索过程中，如果发现某个状态的后继状态一定不是问题的最优解，那么就可以将这个状态从搜索树中删除，这个过程就是最优性剪枝。

启发式搜索

启发式搜索：在搜索过程中，根据问题的特点，选择一个启发函数，根据启发函数的值来选择后继状态，这个过程就是启发式搜索。

记忆化搜索

记忆化搜索：在搜索过程中，将已经搜索过的状态保存下来，下次搜索到这个状态时，直接从保存的结果中取出，这个过程就是记忆化搜索。

贪心

贪心：在每一步都选择当前状态下最好或最优的选择，最终得到的就是全局最好或最优的结果（局部最优解得到全局最优解）。局部最优解不一定是全局最优解，因此贪心算法不一定能得到问题的解。

二分与三分

二分法

二分法，即一分为二的方法，将一个区间分为两个子区间，然后在一个子区间中继续使用一分为二的方法，直到找到问题的解为止。
二分查找（Binary Search）：在有序数组中查找某个元素的位置。
C++中的二分查找函数：
lower_bound()：返回第一个大于等于给定值的元素的位置。
upper_bound()：返回第一个大于给定值的元素的位置。
binary_search()：返回是否存在给定值的元素。
equal_range()：返回一个pair，pair的first成员是lower_bound()的返回值，pair的second成员是upper_bound()的返回值。
二分答案（Binary Answer）：在一个区间中查找满足某个条件的最大值或最小值。

三分法

三分法，即一分为三的方法，将一个区间分为三个子区间，然后在一个子区间中继续使用一分为三的方法，直到找到问题的解为止。

递归与分治

递归

递归：如果一个问题可以被分为若干个与原问题相同性质的问题，则可以使用递归来解决这个问题。

分治

分治：如果一个问题可以被分为若干个相互独立的子问题，且这些子问题的解可以合并为原问题的解，则可以使用分治来解决这个问题。

基本的排序算法

基本概念

排序：将一组数据按照某种顺序重新排列的过程。
稳定性：如果两个相等的元素在排序前后的相对位置不发生改变，则这个排序算法是稳定的。
时间复杂度：排序算法的时间复杂度是指该算法的运行时间，一般使用大O表示法来表示时间复杂度。
空间复杂度：排序算法的空间复杂度是指该算法的运行过程中所需要的额外的存储空间，一般使用大O表示法来表示空间复杂度。
C++：std::sort()

交换排序

交换排序：通过交换数组中的元素来实现排序。

冒泡排序

冒泡排序：每次从数组的第一个元素开始，依次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换这两个元素，直到数组的最后一个元素，这样一次冒泡排序就完成了，然后再从数组的第一个元素开始，依次比较相邻的两个元素，直到数组的倒数第二个元素，这样第二次冒泡排序就完成了，依次类推，直到数组中的所有元素都排好序为止。

快速排序

快速排序：从数组中选择一个元素作为基准，将数组中的元素分为两部分，左边的元素都小于基准，右边的元素都大于基准，然后对左右两部分分别进行快速排序，直到数组中的所有元素都排好序为止。

插入排序

插入排序：将数组中的元素分为两部分，左边的元素都是已经排好序的，右边的元素都是未排序的，每次从未排序的部分中取出一个元素，将它插入到已经排好序的部分中，直到数组中的所有元素都排好序为止。

直接插入排序

直接插入排序：每次从未排序的部分中取出一个元素，将它插入到已经排好序的部分中，直到数组中的所有元素都排好序为止。

折半插入排序

折半插入排序：每次从未排序的部分中取出一个元素，使用二分查找的方法将它插入到已经排好序的部分中，直到数组中的所有元素都排好序为止。

希尔排序

希尔排序：将数组中的元素分为若干个子序列，分别对每个子序列进行直接插入排序，直到数组中的所有元素都排好序为止。

选择排序

选择排序：每次从数组中选择一个最小的元素，将它与数组中的第一个元素交换，然后从剩下的元素中选择一个最小的元素，将它与数组中的第二个元素交换，依次类推，直到数组中的所有元素都排好序为止。

直接选择排序

直接选择排序：每次从数组中选择一个最小的元素，将它与数组中的第一个元素交换，然后从剩下的元素中选择一个最小的元素，将它与数组中的第二个元素交换，依次类推，直到数组中的所有元素都排好序为止。

堆排序

堆排序：将数组中的元素构建成一个大顶堆，然后将堆顶元素与数组中的最后一个元素交换，然后将剩下的元素重新构建成一个大顶堆，然后将堆顶元素与数组中的倒数第二个元素交换，依次类推，直到数组中的所有元素都排好序为止。

归并排序

归并排序：将数组中的元素分为两部分，分别对每个部分进行归并排序，然后将两个排好序的部分合并成一个排好序的部分，直到数组中的所有元素都排好序为止。

二路归并排序

二路归并排序：将数组中的元素分为两部分，分别对每个部分进行归并排序，然后将两个排好序的部分合并成一个排好序的部分，直到数组中的所有元素都排好序为止。

多路归并排序

多路归并排序：将数组中的元素分为若干个子序列，分别对每个子序列进行归并排序，然后将若干个排好序的子序列合并成一个排好序的序列，直到数组中的所有元素都排好序为止。

基数排序

基数排序：将数组中的元素按照某个位数进行排序，然后按照下一个位数进行排序，直到所有的位数都排序完毕，这样整个数组就排好序了。