二分查找、归并排序、快速排序
二维数组搜索路径：回溯法、递归
最优解，多个子问题：动态规划（自上而下、自下而上）
子问题特殊选择：贪婪算法
查找：顺序查找、二分查找、哈希表查找和二叉排序树查找（二叉搜索树）
二分查找：在排序的数组查找一个数字或者统计某个数字出现次数；
排序
插入排序、冒泡排序、归并排序、快速排序等
2小时让你精通前端3种排序算法_哔哩哔哩_bilibili
https://www.bilibili.com/video/BV1C64y1M7sR?p=4&spm_id_from=pageDriver
冒泡排序Bubble：
//冒泡
//让数组中的当前项和后一项比较，偌大，交换位置，大数在后面
//第一轮结束后，最大的值换到了最后，其他值未完成排序，内层比较了length-1次
// 所以外层进行ary.lenght-1轮，且不用和自己及末尾已排序(length-1-目前轮次数)的比较
function bubble(ary){
// 外层循环
for(let i=0;i<ary.length-1;i++){
// 里层循环
for(let j = 0;j<ary.length-1-i;j++){
if(ary[j]>ary[j+1]){
const temp = ary[j];
ary[j] = ary[j+1];
ary[j+1] = temp;
}
}
}
return ary;
}插入排序Insert：
//插入排序
//打牌，准备新数组，外层顺着摸,内层和手里的牌依次比大小（从后向前）
// 如果新牌A比手里某张牌B大，则把A放到B的后面，如果小继续向前比
// 如果比到第一张牌，插到最前面
function insert(ary){
let res =[];
res.push(ary[0]);
for(let i = 1;i<ary.length;i++){
const A = ary[i];
for(let j = res.length-1;j>=0;j--){
const B = res[j];
if(A>B){res.splice(j+1,0,A);break;}
if(j===0){res.unshift(A);}
}
}
return res;
}快速排序Quick：平均效率最好，不是任何时候最优
//快速排序（递归）
// 找到数组中间项，把它从原来数组中移除，获取这一项结果
// 创建左边数组和右边数组，原数组中每一项和中间项比
// 递归，直到只有一项或者没有
// 结果等于左边+中间+右边；
function quickSort(ary) {
if(ary.length<=1) return ary;
let mid=ary.length>>1,midValue = ary.splice(mid,1)[0];//splice()返回的是数组，所以提取[0]
let aryLeft=[],aryRight=[];
for(let i=0;i<ary.length;i++){
let cur = ary[i];
cur<midValue?aryLeft.push(cur):aryRight.push(cur);
}
return [...quickSort(aryLeft),midValue,...quickSort(aryRight)];
}
let array = [12,8,15,16,1,24];
console.log(quickSort(array));*递归函数中调用自己会导致死递归，栈溢出；
递归时使用setTimeout(fn,0)不会导致栈溢出错误；
回溯法（纯暴力搜索）
带你学透回溯算法（理论篇）| 回溯法精讲！_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1cy4y167mM?spm_id_from=333.999.0.0leetcode
组合77 17 39 40 216
分割131 93
子集78 90
排列46 47
棋盘问题51 37（难）
其他491 332（难）
抽象为树形结构（递归，无返回值）
for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历
var funcation backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
//单层搜索逻辑
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
for (int i = startIndex; i <= n; i++) {
path.push_back(i);
backtracking(n, k, i + 1);//i重复，i+1不重复
path.pop_back();
}
//剪枝
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置组合剪枝77(通过条件不进行一些遍历)
只要把本层集合元素length改为n-(k-res.lenght)+1就可以完成剪枝操作。
-
已经选择的元素个数：res.length();
-
还需要的元素个数为: k - res.length();
-
在集合n中至多要从该起始位置 : n - (k - res.length()) + 1，开始遍历
可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
N皇后
/**
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function(n) {
//建立二维数组,方便引索
let res = new Array(n).fill([]).map(() => new Array(n).fill('.')),ans=[];
const backTracking=function(n,row){
if(row===n){
let cur=[];
for(const i of res){
cur.push(i.join(''));
}
ans.push([...cur]);
return;
}
for(let col = 0;col<n;col++){
if(isValid(row,col,res,n)){
res[row][col]='Q';
backTracking(n,row+1);
res[row][col]='.';
}
}
}
//皇后判别
const isValid=function(row,col,res,n){
for(let j=0;j<row;j++){
if(res[j][col]=='Q'){return false;}
}
for(let i =0;i<col;i++){
if(res[row][i]=='Q'){return false;}
}
for(let i=row-1,j=col+1;i>=0&&j<n;i--,j++){
if(res[i][j]=='Q'){return false;}
}
for(let i=row-1,j=col-1;i>=0&&j<n;i--,j--){
if(res[i][j]=='Q'){return false;}
}
return true;
}
backTracking(n,0);
return ans;
};