一、概念
1.什么是算法与数据结构？？
数据结构：指的是“一组数据的存储结构”
算法：指的是“操作数据的一组方法” (计算机解决问题的一种方法)
数据结构是为算法服务的，算法是要作用在特定的数据结构上的。
2.常用的数据结构与算法？？
数据结构： 数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Tire树
算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
3.数据结构与算法思维导图：
二、JavaScript中常用的算法
1. 实现递归
一个递归算法就是函数调用自身去解决它的子问题。
递归的特点：
1.在函数过程中调用自身。
2.在递归过程中，必须有一个明确的条件判断递归的结束，既递归出口。
3.递归算法简洁但效率低，通常不作为推荐算法。
JS实现递归的3种方法：
- 通过函数自身名字递归调用
function sum(num){
if(num<=1){
return 1;
}
else{
return num+sum(num-1); //调用函数自身
}
}
//通过函数名字调用自身的方式存在一个问题：函数的名字是一个指向函数对象的指针，
//如果我们把函数的名字与函数对象本身的指向关系断开，这种方式运行时将出现错误。
- 通过arguments.callee调用函数自身
function sum(num){
if(num<=1){
return 1;
}
else{
return num+arguments.callee(num-1); //通过arguments.callee调用函数自身
}
}
console.log(sum(5)); //15
var sumAnother=sum;
console.log(sumAnother(5)); //15
sum=null;
console.log(sumAnother(5)); //15
//这种方式很好的解决了函数名指向变更时导致递归调用时找不到自身的问题。
//但是这种方式也不是很完美，因为在严格模式下是禁止使用arguments.callee的。
- 通过函数命名表达式来实现arguments.callee的效果。
var sum=(function(){
'use strict'
return function fun(num){
if(num<=1){
return 1;
}
else{
return num+fun(num-1);
}
}
})()
console.log(sum(5));//15
var sumAnother=sum;
console.log(sumAnother(5));//15
sum=null;
console.log(sumAnother(5));//15
排序算法
排序算法 是按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作，
排序算法 方法种类较多，其中比较简单常用的排序算法：快速排序和冒泡排序。
(1). 快速排序 (最常用)
快速排序的3个基本步骤：
1.从数组中选择一个元素作为基准点
2.排序数组，所有比基准值小的元素摆放在左边，而大于基准值的摆放在右边。每次分割结束以后基准值会插入到中间去。
3.最后利用递归，将摆放在左边的数组和右边的数组在进行一次上述的1和2操作。
var quickSort = function(arr) {
if (arr.length <= 1) {
return arr;
}
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var 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));
};
以上代码的实现方式：选择一个中间的数字为基准点，用两个数组分别去保存比基准数小的值，和比基准数大的值，最后递归左边的数组和右边的数组，用concat去做一个数组的合并。
(2). 冒泡排序
冒泡排序 是一种非常基础的排序方法，其原理就是从把一个数组中的每一个数从前往后依次进行比较，然后根据大小交换位置，每一轮的比较都确定出一个当轮比较的最大值，最终实现数组的大小排序。
var arr = [3, 4, 1, 2];
function bubbleSort (arr) {
var max = arr.length - 1;
for (var j = 0; j < max; j++) {
// 声明一个变量，作为标志位
var done = true;
for (var i = 0; i < max - j; i++) {
if (arr[i] > arr[i + 1]) {
var temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
done = false;
}
}
if (done) { //排序完，没有替换的，则指定跳出，优化性能
break;
}
}
return arr;
}
bubbleSort(arr);
查找算法
根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素
1.顺序查找
顺序查找也称线形查找。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。
//查找指定值
function seqSearch(arr, data) {
for (var i = 0; i < arr.length; ++i) {
if (arr[i] == data) {
return true;
}
}
return false;
}
//查找最小值和最大值
function findMin(arr) {
var min = arr[0];
for (var i = 1; i < arr.length; ++i) {
if (arr[i] < min) {
min = arr[i];
}
}
return min;
}
function findMax(arr) {
var max = arr[0];
for (var i = 1; i < arr.length; ++i) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
2. 二分查找
条件：有序的数组。
思路：
1.将数组折半，分成左右两个数组。
2.判断要查找的数和中间位置数值的大小，来判断要查找的数实在哪一半。
3.之后继续折半查找，直至找到这个数。
//arr 已排好的数组 data想要查找的值
function search(arr,data){
var max = arr.length-1, //最大值
min = 0; //最小值
while(min<=max){
var mid = Math.floor((max+min)/2); //中间值
if(arr[mid]<data){ //取后半段
min = mid+1; //缩小范围
}
else if(arr[mid]>data){ //取前半段
max = mid-1; //缩小范围
}
else{
return mid;
}
}
return -1; //没找到返回-1
}