一、冒泡排序的优化

1.内层循环次数递减

  1. function sort(arr){
  2.   const {length} = arr;
  3.   for (let i=0 ; i<length ; i++){
  4.     for (let j=0 ; j<length-i-1;j++){
  5.       swap(arr,j,j+1)
  6.       }
  7.     }
  8.   return(arr) //一定要有！！
  9. };
  10. function swap(arr,a,b){
  11.   if (arr[a]>arr[b]){
  12.     var temp = arr[a];
  13.     arr[a] = arr[b];
  14.     arr[b] = temp;
  15.   }
  16. }

原理：体现在第二轮的for循环的j<length-i-1条件语句，起效是因为第i轮代表排好了第i大的数（在序列的末尾），故之后的循环可以省略这些已经排好序的数值

2.监控内层交换

2.1 哨兵的作用

（1）暂时存放待插入的元素

（2）防止数组下标越界。（避免对已经排好序的序列再做排序）

2.2 代码实现

原理：监控内层是否发生过交换，如过某次内层没有发生过交换直接返回。

  1. function sort(arr){
  2.     const {length} = arr;
  3.     for (var i = length-1 ; i>=1 ; i--){
  4.         var swaped = false;  // 设置哨兵，用来监控内层是否发生交换
  5.         for (var j = 0 ; j<i ; j++){
  6.             if (arr[j]>arr[j+1]){
  7.                 swap(arr,j,j+1);
  8.                 swaped = true; //true表示发生了交换
  9.             }
  10.         }
  11.         if (!swaped){
  12.             break; //若整轮下来都不需要发生交换即swaped始终为false，则可直接结束循环
  13.         }   
  14.     }
  15.     return arr 
  16. };

【注释】因为有if循环在，所以只要是没有全部排好序，都会将第n个大的数轮到倒数第n个的地方。而只有当全部排好序了，故而只要开始外循环之后在该轮中，有一次swaped为false则代表该次循环并没有再进行交换排序，则可以说明全部数值已经排序完成了！可以结束。。

二、链表

1. 接口的实现

  1. // Node类表示我们想要添加到链表中的项。它的element 属性表示要加入链表元素的值；next 属性是指向链表中下一个元素的指针。
  2. class Node {
  3.   constructor(element) {
  4.     this.element = element;
  5.     this.next = undefined;
  6.   }
  7. }
  8. function defaultEquals(a,b) { 
  9.   return a === b; 
  10. } 
  11. //创建LinkedList 类的“骨架”
  12. class LinkedList {
  13.   constructor(equalsFn = defaultEquals) { 
  14.     this.count = 0; 
  15.     this.head = undefined; // 保存第一个函数的引用
  16.     this.equalsFn = equalsFn; 
  17.  } 
  18. }
  20. class DoublyNode extends Node {
  21.     constructor(element, next, prev) {
  22.     super(element, next); 
  23.     this.prev = prev; // 新增的
  24.     } 
  25. } 
  26. class DoublyLinkedList extends LinkedList {  // 表明是在扩展 LinkedList 类（
  27.     constructor(equalsFn = defaultEquals) { 
  28.     super(equalsFn);  
  29.     this.tail = undefined; // 新增的  用来保存对最后一个元素的引用
  30.     }
  31. }

1.1 生成链表

  • 单链表
    1. //尾插法
    2. push(element) { 
    3. const node = new Node(element); // 把 element 作为值传入
    4. let current;  //current 变量总是为对所循环列表的当前元素
    5. if (this.head == null) { // 判断原列表是否为空
    6. this.head = node; 
    7. } else { 
    8. current = this.head; // 我们只有第一个元素的引用（所以是head），并在此基础上进行循环
    9. while (current.next != null) { // 直到找到最后一项，跳出while
    10. current = current.next; 
    11. } 
    12. current.next = node; // 将其 next 赋为新元素，建立链接
    13. } 
    14. this.count++; // 
    15. }
    尾插法.webp
  1. //头插法（成为第二个）
  2. push2(element) { 
  3.   const node = new Node(element); // 把 element 作为值传入
  4.   let current;  //current 变量总是为对所循环列表的当前元素
  5.   if (this.head == null) { // 判断原列表是否为空
  6.     this.head = node; 
  7.     } else { 
  8.       let previous = this.head; 
  9.       let current = previous.next;
  10.       previous.next = node;
  11.       node.next = current;
  12.       } 
  13.   this.count++;
  14. }

头插法.webp


  • 1.2 判断链表是否为空

  • 单链表

    1. isEmpty () {
    2. return this.size() === 0;
    3. }

  • 双向链表

    1. push(element) { 
    2. const node = new DoublyNode(element); 
    3. if (this.head == null) {
    4.   this.head = node;
    5.   this.tail = node;
    6. } else { 
    7.   this.tail.next = node;
    8.   node.prev = this.tail;
    9.   this.tail = node;
    10. }
    11. this.count++;
    12. }

  • 循环链表

    1.   push(element) {
    2.     const node = new Node(element);
    3.     let current;
    4.     if (this.head == null) {
    5.       this.head = node;
    6.     } else {
    7.       current = this.getElementAt(this.size() - 1); //找到最后一个元素
    8.       current.next = node;
    9.     }
    10.     node.next = this.head;
    11.     this.count++;
    12.   }


  • 1.3 链表的清空

  • 单链表

    1. clear (){
    2. this.count = 0;
    3. this.head = undefined;
    4. }

  • 双向链表

    1.   clear() {
    2.     super.clear(); //
    3.     this.tail = undefined;
    4.   }

  • 循环链表

    1. clear (){
    2. this.count = 0;
    3. this.head = undefined;
    4. }

    1.4 结点的插入

  • 单链表

    1. insert(element,index){
    2.   if (index>=0 && index<=this.count){
    3.     const node = new Node(element);
    4.     if (index === 0){
    5.       const current = this.head;
    6.       node.next = current;
    7.       this.head = node;
    8.     } else {
    9.       const previous = this.getElementAt(index-1);
    10.       const current = previous.next;
    11.       node.next = current; 
    12.       previous.next = node;
    13.     }
    14.     this.count++;
    15.   }
    16.   return false;
    17. }

  • 双向链表

    1.   insert(element,index){
    2.     if (index>=0 && index<=this.count){
    3.       const node = new DoublyNode(element); //
    4.       let current = this.head;
    5.       if (index === 0){  //加在第一项
    6.         if (this.head == null) { // 新增的
    7.           this.head = node; 
    8.           this.tail = node; 
    9.         } else { 
    10.           node.next = this.head; // 
    11.           current.prev = node; //  新增的
    12.           this.head = node; // 
    13.         } 
    14.       } else if (index === this.count) { // 新增的 //加在最后一项
    15.         current = this.tail; 
    16.         current.next = node; 
    17.         node.prev = current; 
    18.         this.tail = node; 
    19.       } else { 
    20.         //找到index前后的两个元素
    21.         const previous = this.getElementAt(index - 1); // 找到添加位置的前一位元素
    22.         current = previous.next; // 找到原来在index上的元素（即将往后挪一位）
    23.         //为新加入的元素添加4条相关链接
    24.         previous.next = node; // 定义新的previous.next是新插入的元素
    25.         node.next = current; //  
    26.         current.prev = node; // 新增的
    27.         node.prev = previous; //  新增的
    28.       } 
    29.       this.count++; 
    30.       return true; 
    31.     } 
    32.     return false; 
    33.   }

  • 循环链表

    1. insert(element, index) { 
    2.   if (index >= 0 && index <= this.count) { 
    3.     const node = new Node(element); 
    4.     let current = this.head; 
    5.     if (index === 0) { 
    6.       if (this.head == null) { 
    7.         this.head = node; 
    8.         node.next = this.head; // 新增的
    9.       } else { 
    10.         node.next = current; // 此时current的值是原本的第一个元素
    11.         current = this.getElementAt(this.size()); // 将current重新定义为最后一个元素
    12.         // 更新最后一个元素
    13.         this.head = node; // 将新元素插在头部
    14.         current.next = this.head; // 实现头尾循环的链接
    15.       } 
    16.     } else {  //不变
    17.       const previous = this.getElementAt(index - 1); 
    18.       node.next = previous.next; 
    19.       previous.next = node; 
    20.     } 
    21.     this.count++; 
    22.     return true; 
    23.   } 
    24.   return false; 
    25. }

    1.5 结点的删除

  • 单链表

    1. remove(element) { 
    2.   const index = this.indexOf(element); 
    3.   return this.removeAt(index); 
    4. }

  • 双向链表

    1.   removeAt(index) { 
    2.     if (index >= 0 && index < this.count) { 
    3.       let current = this.head; 
    4.       if (index === 0) { //移走头部
    5.         this.head = current.next; // 定义了新的头部
    6.         // 如果只有一项，更新 tail,直接undefined // 新增的
    7.         if (this.count === 1) { //  
    8.           this.tail = undefined; 
    9.         } else {  
    10.          this.head.prev = undefined; 
    11.         } 
    12.      }  else if (index === this.count - 1) {  //新增的
    13.         current = this.tail;  
    14.         this.tail = current.prev;  
    15.         this.tail.next = undefined; 
    16.       } else { 
    17.         current = this.getElementAt(index); // {7} 
    18.         const previous = current.prev; // {8} 
    19.         // 将 previous 与 current 的下一项链接起来，跳过 current ，达到移除current
    20.         previous.next = current.next; 
    21.         current.next.prev = previous; // 新增的
    22.       } 
    23.       this.count--; 
    24.       return current.element; 
    25.     } 
    26.     return undefined; 
    27.   }

  • 循环链表

    1. removeAt(index) {
    2.   if (index >= 0 && index < this.count) {
    3.     let current = this.head;
    4.     if (index === 0) {
    5.       if (this.size() === 1) {
    6.         this.head = undefined;
    7.       } else {
    8.         const removed = this.head;
    9.         current = this.getElementAt(this.size() - 1);
    10.         this.head = this.head.next;
    11.         current.next = this.head;
    12.         current = removed;
    13.       }
    14.     } else {
    15.       const previous = this.getElementAt(index - 1);
    16.       current = previous.next;
    17.       previous.next = current.next;
    18.     }
    19.     this.count--;
    20.     return current.element;
    21.   }
    22.   return undefined;
    23. }

    1.6 返回第i个结点

    1. getElementAt (index){
    2.   if (index>=0 && index<=this.count){ //循环迭代链表直到目标位置
    3.     let node = this.head; 
    4.     for (let i = 0; i<index; i++){
    5.       node = node.next; //相当于随上面remove中的current移动而移动
    6.     }
    7.     return node;
    8.   }
    9.   return undefined;
    10. }

1.7 返回链表的结点个数

  • 单链表
    1. size(){
    2.   return this.count
    3. }

    1.8 根据给定值，返回该值在链表出现的第一个位置

    1. indexOf (element) {
    2.   let current = this.head;
    3.   for (let i = 0; i < this.count && current != null; i++){
    4.     if (this.equalsFn(element, current.element)){
    5.       return i
    6.     }
    7.     current = current.next;
    8.   }
    9.   return -1
    10. }

    2. 链表和传统的顺序表的优缺点对比

项目 优点 缺点
链表 插入删除比较方便（因为有指针的存在）；
分配空间不固定（动态），元素个数无限制，适用于元素数目变化较大或者数目不确定的情况		 随机储存没有顺序表方便；
存在空间浪费（结构性开销），查找不方便
顺序表 随机访问较快，查找方便；
创建比较简单，便于随机储存；
没有空间浪费，适用于元素数目一定或者较少的情况		 插入删除比较麻烦；
分配的空间是固定的，元素个数不能超过预定的长度

三、栈和队列

栈是一种遵从后进先出（LIFO）原则的有序集合。
队列是遵循先进先出（FIFO，也称为先来先服务）原则的一组有序的项。

1. 接口的实现

  1. class Stack { 
  2.     constructor() { 
  3.         this.count = 0; // 作items对象的键名
  4.         this.items = {}; // 选择数组保存栈内元素
  6.     }
  7. }
  1. class Queue {
  2.     constructor() {
  3.       this.count = 0; // 是用来控制队列的大小而非直接就是队列的长度
  4.       this.lowestCount = 0; // 用来追踪第一个元素（即使移除了元素，其前对应的“位置序号”还是原来的数值）
  5.       this.items = {};
  6.     }    
  7. }

1.1 元素入栈

  1. push(element) { 
  2.     this.items[this.count] = element
  3.     this.count++
  4. }

1.2 元素出栈

  1. pop(){ 
  2.  if (this.isEmpty()) {
  3.      return undefined; 
  4.  } 
  5.  this.count--; 
  6.  const removed  = this.items[this.count]; 
  7.  delete this.items[this.count];  
  8.  return removed; 
  9. }

1.3 返回栈的长度

  1. size(){
  2.   return this.count
  3. }

1.4 判断是否为空栈

  1. isEmpty() {
  2.     return this.count === 0;
  3. }

1.5 栈的清空

  1. clear() {
  2.   this.items = {};
  3.   this.count = 0; // 很有必要不要遗漏！
  4. }

2. 关于栈的上溢和下溢

2.1 栈上溢

（1）情况一： 栈已满的前提下，继续执行入栈操作
（2）情况二： 设置了死循环

2.2 栈下溢

栈已空，无法进行退栈操作

3.栈的真溢出和假溢出

(函数递归的时候容易发生“栈溢出”)

3.1 栈的真溢出

3.2 栈的假溢出

存储区未满，发生了溢出

3.3 解决方案

  • 解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。（递归很容易发生“栈溢出”，而ES6 中只要使用尾递归，就不会发生栈溢出

（原理：使递归本身无论调用多少次，都只占用一个栈帧）

四、队列

1. 接口的实现

1.1 元素入队

  1. enqueue(element) { 
  2.     this.items[this.count] = element; 
  3.     this.count++; 
  4. }

1.2 元素出队

  1. dequeue(){
  2.     if (this.isEmpty()) {
  3.         return undefined
  4.     }
  5.     const removed = this.items[this.lowestCount];
  6.     delete this.items[this.lowestCount];
  7.     this.lowestCount++; 
  8.     return removed;
  9. }

1.3 返回队列的长度

  1. size() {
  2.   return this.count - this.lowestCount; 
  3. }

1.4 判断队列是否为空

  1. isEmpty() { 
  2.   return this.size() === 0; 
  3. }

1.5 队列的清空

  1. clear(){
  2.     this.items = {};
  3.     this.count = 0;
  4.     this.lowestCount = 0;
  5. }

2. 队列的真溢出和假溢出

2.1 真溢出：

Q.rear==Q.front（循环）

2.2 假溢出

当队列中的存储空间没满时，但是由于来的元素堵在队尾，此时如果还有元素要入队的话，就会报错，发生溢出

2.3 解决方案

  1. 按最大可能的进队操作次数设置顺序队列的最多元素个数，比如说如果要操作16次，则可以存储8个元素；但是这个方法很浪费空间，一般不用这个方法；
  2. 修改出队操作算法，使每次出队后都把队列中剩余的操作元素向队头移动一个位置；
  3. 修改入队算法,增加判断条件，当发生“假性溢出”时，把数据元素向队头移动；
  4. 采用循环队列；

（参考链接：如何解决队列的“假性溢出”问题？）

五、双端队列

1.接口的实现

1.1 元素入队

  1. // 在后端添加元素
  2. addBack(element) { 
  3.     this.items[this.count] = element; 
  4.     this.count++; 
  5. }
  1. // 在前端添加元素
  2. addFront(element){
  3.         if (this.isEmpty()) {
  4.           this.addBack(element);
  5.         }else if(this.lowestCount>0){  //之前有元素被移出去了
  6.           // 直接将新元素插在最前面
  7.           this.lowestCount--; // 先设置现在新的第一个位置
  8.           this.items[this.lowestCount]=element; // 将新元素插在最前面
  9.         }else{ // 没有移动过元素的情况（此时的lowestCount=0）
  10.           for (let i = this.count;i>0;i--){ //从后往前会更加便利（因为最后一个位置初始状态是空的，如果从前往后则需要中间量）
  11.             this.items[i] = this.items[i-1]
  12.           }
  13.           this.count++;
  14.           this.items[0] = element;
  15.         }
  16. }

1.2 元素出队

  1. // 在后面出队
  2. removeFront(){
  3.     if (this.isEmpty()) {
  4.         return undefined
  5.     }
  6.     const removed = this.items[this.lowestCount];
  7.     delete this.items[this.lowestCount];
  8.     this.lowestCount++; 
  9.     return removed;
  10. }
  1. // 在前面出队
  2. removeBack(){
  3.     if (this.isEmpty()){
  4.         return undefined;
  5.     }else{
  6.         const removed = this.items[this.count-1]
  7.         delete this.items[this.count-1];
  8.         this.count--;
  9.         return removed
  10.     }
  11. }

1.3 返回队列的长度

  1. size() {
  2.   return this.count - this.lowestCount; 
  3. }

1.4 判断队列是否为空

  1. isEmpty() { 
  2.   return this.size() === 0; 
  3. }

1.5 队列的清空

  1. clear(){
  2.     this.items = {};
  3.     this.count = 0;
  4.     this.lowestCount = 0;
  5. }