Open zhaoqize opened 6 years ago
算法,这个题目有点大。 其实算法是一个很宽的概念,我们写的所有程序都可称之为算法,因为算法就是一个处理问题的逻辑,将问题进行归类,抽象出一个统一范式,然后为这个范式取个名字,比如:快速排序。 所以这里我们就来看下前端有哪些常用的算法。
递归算法 : 英语:recursion algorithm)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。绝大多数编程语言支持函数的自调用,在这些语言中函数可以通过调用自身来进行递归。
递归的两个要素:
阶乘 n! = n(n-1)...2*1
6! = 6 5 4 3 2 *1
规律:n的阶乘就是从n开始依次递减值的积
function factorial(number){ if(number==1) { return number; } else{ return number*factorial(number-1); } }
斐波那契数列 斐波那契数列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 求第n个数是多少
第一个数: 1 = 1 第二个数: 1 = 1 第三个数: 2 = 1 + 1 第四个数: 3 = 2 + 1 第五个数: 5 = 3 + 2 第六个数: 8 = 5 + 3 ...
规律:后一项是前两项的和
function fibonacci(number) { if (number <= 2) { return 1; } return fibonacci(number-1) + fibonacci(number - 2) }
冒泡排序算法:它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
比较流程
升顺排列 6 2 7 9 5
第一次冒泡: 2 6 7 9 5 第二次冒泡: 2 5 7 9 6 ...
// 升序比较 function bubbleSort(arr) { var nArr = arr.slice(); var temp; if (nArr.length > 0) { for (var i = 0; i < nArr.length; i++){ for (var l = i; l < (nArr.length - 1); l++){ if (nArr[i] > nArr[l+1]) { temp = nArr[i]; nArr[i] = nArr[l+1]; nArr[l+1] = temp; } } } } return nArr; }
快速排序算法:快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法,通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直到所有数据都是有序的。
排序说明
function qSort(arr){ if(arr.length <= 1){ return arr; } let midIndex = Math.floor(arr.length/2); //取基准点 let midVal = arr.splice(midIndex,1); //取基准点的值 let left = [];//存放比基准点小的数组 let right = [];//存放比基准点大的数组 for(let i = 0; i < arr.length; i++){ if(arr[i] < midVal){ left.push(arr[i]);//比基准点小的放在左边数组 }else{ right.push(arr[i]);//比基准点大的放在右边数组 } } // 递归 return quickSort(left).concat(midVal,quickSort(right)); }
二分查找算法:也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
查找说明
1.将数组的第一个位置设置为下边界(0) 2.将数组最后一个元素所在的位置设置为上边界(数组的长度减1)。 3.若下边界等于或小于上边界,则做如下操作。 将中点设置为(上边界加上下边界)除以2 如果中点的元素小于查询的值,则将下边界设置为中点元素所在下标加1 如果中点的元素大于查询的值,则将上边界设置为中点元素所在下标减1 否则中点元素即为要查找的数据,可以进行返回。
1.将数组的第一个位置设置为下边界(0) 2.将数组最后一个元素所在的位置设置为上边界(数组的长度减1)。 3.若下边界等于或小于上边界,则做如下操作。
注意这里的数组必须是有序的
function binSearch(arr, data) { var upperBound = arr.length - 1; var lowerBound = 0; while (lowerBound <= upperBound) { var mid = Math.floor((upperBound + lowerBound) / 2); if (arr[mid] < data) { lowerBound = mid + 1; } else if(arr[mid] > data) { upperBound = mid - 1; } else { return mid; } } return -1; }
二叉树 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的特性
二叉树遍历
这里采用递归-先序遍历一个树形结构
var preOrder = function (node) { if (node) { preOrder(node.left); preOrder(node.right); } }
算法,这个题目有点大。 其实算法是一个很宽的概念,我们写的所有程序都可称之为算法,因为算法就是一个处理问题的逻辑,将问题进行归类,抽象出一个统一范式,然后为这个范式取个名字,比如:快速排序。 所以这里我们就来看下前端有哪些常用的算法。
递归
递归算法 : 英语:recursion algorithm)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。绝大多数编程语言支持函数的自调用,在这些语言中函数可以通过调用自身来进行递归。
递归的两个要素:
阶乘 n! = n(n-1)...2*1
规律:n的阶乘就是从n开始依次递减值的积
斐波那契数列 斐波那契数列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 求第n个数是多少
规律:后一项是前两项的和
排序算法
冒泡排序算法:它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
比较流程
升顺排列 6 2 7 9 5
快速排序算法:快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法,通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直到所有数据都是有序的。
排序说明
检索算法
二分查找算法:也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
查找说明
注意这里的数组必须是有序的
二叉树算法
二叉树 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的特性
二叉树遍历
这里采用递归-先序遍历一个树形结构