基本算法
算法基本概念
算法复杂度
参考
递归
- 递归主体，就是要循环解决问题的代码
- 递归的跳出条件，递归不能一直递归下去，需要完成一定条件后跳出
递归容易造成爆栈，尾部调用可以解决递归的这个问题
分治
部分算法如快排、二分查找等都是基于分治思想。
排序
参考:
快速排序
选择一个目标值，比目标值小的放左边，比目标值大的放右边，目标值的位置已排好，将左右两侧再进行快排，利用分治思想实现排序
快排流程：
- 随机选择数组中的一个标志数 A，以这个数为基准
- 其他数字跟这个数进行比较，比这个数小的放在其左边，大的放到其右边
- 经过一次循环之后，A 左边为小于 A 的，右边为大于 A 的
- 分别对左右数组进行递归，重复上面过程，直至数组已排序为止（剩余1个元素）
function quickSort(arr) {
// 递归结束条件
if (arr.length <= 1) {
return arr;
}
let pivotIndex = Math.floor(arr.length / 2);
let pivot = arr.splice(pivotIndex, 1)[0];
let left = [];
let right = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
// 递归
return quickSort(left).concat([pivot], quickSort(right));
}
选择排序
每次排序取一个最大或最小的数字放到前面的有序序列中。
for (var i = 0; i < num; ++i){
var min = i;
for (var j = i + 1; j < num; ++j){
if (arr[min] > arr[j]){
min = j;
}
}
var temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
冒泡排序
循环数组，比较当前元素和下一个元素，如果当前元素比下一个元素大，向上冒泡。下一次循环继续上面的操作，不循环已经排序好的数。
for (var i = 0; i < num; ++i){
for (var j = 0; j < num-i; ++j){
if (arr[j+1] < arr[j]){
var temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
插入排序
把未排序子列的第一个数插入到已排序子列的正确位置
将左侧序列看成一个有序序列，每次将一个数字插入该有序序列。插入时，从有序序列最右侧开始比较，若比较的数较大，后移一位。
for (let i = 1, len = arr.length; i < len; ++i){
let j = i,
key = arr[i];
while (--j > -1) {
if (arr[j] > key) {
arr[j + 1] = arr[j];
} else {
break;
}
}
arr[j + 1] = key;
}
归并排序
将大序列二分成小序列，将小序列排序后再将排序后的小序列归并成大序列。利用归并思想实现排序
堆排序
创建一个大顶堆，大顶堆的堆顶一定是最大的元素。交换第一个元素和最后一个元素，让剩余的元素继续调整为大顶堆。从后往前以此和第一个元素交换并重新构建，排序完成。
查找
参考
顺序查找
数组的顺序查找、链表的顺序查找，注意双指针的使用。
二分查找
二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。如果查以空的一半结束，则无法满足条件，并且无法找到目标。
二分查找主要用于在有序数组中找到目标值，其流程为
- 数组中排在中间的数字 A，与要找的数字比较大小
- 因为数组是有序的，所以：
- A 较大则说明要查找的数字应该从前半部分查找
- A 较小则说明应该从查找数字的后半部分查找
- 这样不断查找缩小数量级（扔掉一半数据），直到找完数组为止
function binarySearch(array, target) {
var low = 0,
high = array.length - 1
while (low <= high) {
var mid = Math.floor(low + ( high - low) / 2);
if (array[mid] > target)
high = mid - 1;
else if (array[mid] < target)
low = mid + 1;
else
return mid;
}
return false
}
广度优先搜索
优先遍历当前位置附近的元素
深度优先搜索
优先遍历子节点
回溯算法
从解决问题每一步的所有可能选项里系统选择出一个可行的解决方案。
在某一步选择一个选项后，进入下一步，然后面临新的选项。重复选择，直至达到最终状态。
动态规划
动态规划往往是最能有效考察算法和设计能力的题目类型，面对这类题目最重要的是抓住问题的阶段，了解每个阶段的状态，从而分析阶段之间的关系转化。
适用于动态规划的问题，需要满足最优子结构和无后效性，动态规划的求解过程，在于找到状态转移方程，进行自底向上的求解。
将问题抽象成动态方程。
贪心算法
对问题求解的时候，总是做出在当前看来是最好的做法。