"所谓"的前端算法

[zhaoqize]

算法，这个题目有点大。
其实算法是一个很宽的概念，我们写的所有程序都可称之为算法，因为算法就是一个处理问题的逻辑，将问题进行归类，抽象出一个统一范式，然后为这个范式取个名字，比如：快速排序。
所以这里我们就来看下前端有哪些常用的算法。

递归

递归算法 : 英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。

递归的两个要素：

• 调用自身
• 能跳出循环

阶乘
n! = n*(n-1)...21

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
• 否则中点元素即为要查找的数据，可以进行返回。

注意这里的数组必须是有序的

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）。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的特性

• 每个结点最多有两颗子树，结点的度最大为2
• 左子树和右子树是有顺序的，次序不能颠倒
• 即使某结点只有一个子树，也要区分左右子树。

二叉树遍历

这里采用递归-先序遍历一个树形结构

var preOrder = function (node) {
  if (node) {
    preOrder(node.left);
    preOrder(node.right);
  }
}

👆返回主页查看更多文章👆