js 常见数据结构和算法（待更新）

一、排序

冒泡排序

比较相邻的元素，如果前一个比后一个大，交换之。

第一趟排序第1个和第2个一对，比较与交换，随后第2个和第3个一对比较交换，这样直到倒数第2个和最后1个，将最大的数移动到最后一位。

第二趟将第二大的数移动至倒数第二位
......
因此需要n-1趟；

function sort(element){
        for(var i = 0;i<element.length-1;i++) {
         
            for(var j = 0;j<element.length-i-1;j++){
         
                if(element[j]>element[j+1]){
                    //把大的数字放到后面
                    var swap = element[j];
                    element[j] = element[j+1];
                    element[j+1] = swap;
                }
            }
        }
    }
    var element = [3,5,1,2,7,8,4,5,3,4];
    //console.log("before:"+element);[3,5,1,2,7,8,4,5,3,4];
    sort(element);

选择排序

选择排序，从头至尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列

    Array.prototype.selectSort=function () {
        let arr=this,
            len = arr.length;
        for (let i = 0, len = arr.length; i < len; i++) {
    for (let j = i, len = arr.length; j < len; j++) {
      if (arr[i] > arr[j]) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
  }
    return arr;
  }
  [1,2,3,4].selectSort()

二、栈和堆的区别？

• 栈（stack）：由编译器自动分配释放，存放函数的参数值，局部变量等；
  • 基本数据类型存储在栈中
  • 指针放在栈中，该指针指向堆中该实体的起始地址。当解释器寻找引用值时，会首先检索其在栈中的地址，取得地址后从堆中获得实体
    栈的特点：先进后出
• 堆（heap）：一般由程序员分配释放，若程序员不释放，程序结束时可能由操作系统释放
  • 引用数据类型（对象）存储在堆中
• 两种类型的区别
  • 存储位置不同：
    • 原始数据类型直接存储在栈中的简单数据段，占据空间小、大小固定
    • 引用数据类型存储在堆中的对象,占据空间大、大小不固定

三、数组随机排序

• 法一、

  • 遍历数组，每次循环都随机一个在数组长度范围内的数，并交换本次循环的位置和随机数位置上的元素

• 法二、

  • 申明一个新的空数组,利用while循环，如果数组长度大于0，就继续循环；
  • 每次循环都随机一个在数组长度范围内的数，将随机数位置上的元素push到新数组里，
  • 并利用splice（对splice不太理解的同学可以看这里）截取出随机数位置上的元素，同时也修改了原始数组的长度；

• 法三、利用传入sort排序中的比较函数

  • 如果 compareFunction(a, b)的返回值 小于 0 ，那么 a 会被排列到 b 之前；
  • 如果 compareFunction(a, b)的返回值 等于 0 ，那么a 和 b 的相对位置不变；
  • 如果 compareFunction(a, b)的返回值 大于 0 ，那么b 会被排列到 a 之前；

   function randomSort3(arr){
      arr.sort(function(a,b){
          return Math.random() - 0.5;
      });
      return arr;
  }
  

  数组打乱排序（除了sort）

四、 js数组去重

• ES6 Set去重: 无法去掉“{}”空对象
• 利用for嵌套for，然后splice去重
• 利用indexOf去重: 新建一个空的结果数组，for 循环原数组，判断结果数组是否存在当前元素，如果有相同的值则跳过，不相同则push进数组
• 利用sort(): 根据排序后的结果进行遍历及相邻元素比对
• 利用filter
• 利用hasOwnProperty
• 利用includes

链表

链表:存贮有序元素的集合,
但是不同于数组,每个元素是一个存贮元素本身的节点和指向下一个元素引用组成
要想访问链表中间的元素,需要从起点开始遍历找到所需元素

字典

类似对象，以key，value存贮值

二叉树

特点：每个节点最多有两个子树的树结构