js实现基础算法以及堆栈实现

算法复杂度.png

冒泡排序

• 算法步骤：
  • 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  • 针对所有的元素重复以上的步骤，除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
• 代码实现

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

快速排序

• 算法步骤：
  • 先从数列中取出一个数作为“基准”。
  • 分区过程：将比这个“基准”大的数全放到“基准”的右边，小于或等于“基准”的数全放到“基准”的左边。
  • 再对左右区间重复第二步，直到各区间只有一个数。
• 代码实现

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));  //链接左数组、基准数构成的数组、右数组
};

选择排序：

• 算法步骤
  • 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  • 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  • 重复第二步，直到所有元素均排序完毕。
• 代码实现

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

希尔排序：

• 插入排序的更高效的改进版本
• 基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行依次直接插入排序。
• 算法步骤
  • 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
  • 按增量序列个数 k，对序列进行 k 趟排序；
  • 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
• 代码实现：

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {          //动态定义间隔序列
        gap = gap*3+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j -= gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}

归并排序

• 算法思想：归并排序采用的是分治的思想，首先是“分”，将一个数组反复二分为两个小数组，直到每个数组只有一个元素；其次是“治”，从最小数组开始，两两按大小顺序合并，直到并为原始数组大小，
• 代码实现

function mergeSort(arr) {
  let len = arr.length;
  if(len > 1) {
    let index = Math.floor(len / 2);
    left = arr.slice(0,index); //得到下标从0~index-1的数组
    right = arr.slice(index);  //得到下标从index开始到末尾的数组
    return merge(mergeSort(left) , mergeSort(right));  里面采用递归
  }else {
    return arr;
  }
}
//该函数与快排类似，但是仔细发现，每次left或者right都是要shift掉第一个元素，表示left或者right是会变化的，最后arr.concat，因为不知道left或者right其中一个哪个剩下元素，所以要将剩下的元素给加上
function merge(left , right) {   
  let arr = [];
  while(left.length && right.length) {
    if(left[0] < right[0]) {
      arr.push(left.shift());
    }else {
      arr.push(right.shift())
    }
  }
  return arr.concat(left , right);
}

数组常用方式

• 方法详解：
  • concat: 链接两个或者更多数据，并返回结果。
  • every: 对数组中的每一项运行给定的函数，如果该函数对每一项都返回true，则返回true。
  • filter: 对数组中的每一项运行给定函数，返回改函数会返回true的项组成的数组。
  • forEach: 对数组中的每一项运行给定函数，这个方法没有返回值。
  • join: 将所有的数组元素链接成一个字符串。
  • indexOf: 返回第一个与给定参数相等的数组元素的索引，没有找到则返回-1。
  • lastIndexOf: 返回在数组中搜索到的与给定参数相等的元素的索引里最大的值。
  • map: 对数组中的每一项运行给定函数，返回每次函数调用的结果组成的数组。
  • reverse: 颠倒数组中元素的顺序，原先第一个元素现在变成最后一个，同样原先的最后一个元素变成现在的第一个。
  • slice: 传入索引值，将数组中对应索引范围内的元素作为新元素返回。
  • some: 对数组中的每一项运行给定函数，如果任一项返回true，则返回true。
  • sort: 按照字母顺序对数组排序，支持传入指定排序方法的函数作为参数。
  • toString: 将数组作为字符串返回。
  • valueOf: 和toString相似，将数组作为字符串返回。

栈：

• 栈的创建：
  • 对于一个栈，我们需要实现添加、删除元素、获取栈顶元素、已经是否为空，栈的长度、清除元素等几个基本操作。下面是基本定义。

  function Stack(){
    this.items = [];
  }
  Stack.prototype = {
    constructor:Stack,
    push:function(element){
      this.items.push(element);
    },
    pop:function(){
      return this.items.pop();
    },
    peek:function(){
      return this.items[this.items.length - 1];
    },
    isEmpty:function(){
      return this.items.length == 0;
    },
    clear:function(){
      this.items = [];
    },
    size:function(){
      return this.items.length;
    },
    print:function(){
      console.log(this.items.toString());
    }
  }
  

• 用栈实现对正整数的二进制转换：

    function divideBy2(decNumber){
      var decStack = new Stack();
      var rem;
      var decString = '';
      while(decNumber > 0){
        rem = decNumber%2;
        decStack.push(rem);
        decNumber = Math.floor(decNumber/2);
      }
      while(!decStack.isEmpty()){
        decString += decStack.pop().toString();
      }
      return decString;
    }
    console.log(divideBy2(10));//1010

队列

• 队列的创建：
  • 队列是遵循FIFO(First In First Out,先进先出,也称为先来先服务)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的末尾。队列要实现的操作基本和栈一样，只不过栈是FILO(先进后出)。

      function Queue(){
          this.items = [];
      }
      Queue.prototype = {
          constructor:Queue,
          enqueue:function(elements){
              this.items.push(elements);
          },
          dequeue:function(){
              return this.items.shift();
          },
          front:function(){
              return this.items[0];
          },
          isEmpty:function(){
              return this.items.length == 0;
          },
          size:function(){
              return this.items.length;
          },
          clear:function(){
              this.items = [];
          },
          print:function(){
              console.log(this.items.toString());
          }
      }
  

链表

• 链表的创建：
  • 我们使用动态原型模式来创建一个链表。列表最后一个节点的下一个元素始终是null。

  function LinkedList(){
    function Node(element){
      this.element = element;
      this.next = null;
    }
    this.head = null;
    this.length = 0;
    //通过对一个方法append判断就可以知道是否设置了prototype
    if((typeof this.append !== 'function')&&(typeof this.append !== 'string')){
      //添加元素
      LinkedList.prototype.append = function(element){
        var node = new Node(element);
        var current;
        if(this.head === null){
          this.head = node;
        }else{
          current = this.head;
          while(current.next !== null){
            current = current.next;
          }
          current.next = node;
        }
        this.length++;
      };
      //插入元素，成功true，失败false
      LinkedList.prototype.insert = function(position,element){
        if(position > -1 && position < this.length){
          var current = this.head;
          var previous;
          var index = 0;
          var node = new Node(element);
          if(position == 0){
            node.next = current;
            this.head = node;
          }else{
            while(index++ < position){
              previous = current;
              current = current.next;
            }
            node.next = current;
            previous.next = node;
          }
          this.length++;
          return true;
        }else{
          return false;
        }
      };
      //根据位置删除指定元素，成功 返回元素， 失败 返回null
      LinkedList.prototype.removeAt = function(position){
        if(position > -1 && position < this.length){
          var current = this.head;
          var previous = null;
          var index = 0;
          if(position == 0){
            this.head = current.next;
          }else{
            while(index++ < position){
              previous = current;
              current = current.next;
            }
            previous.next = current.next;
          }
          this.length--;
          return current.element;
        }else{
          return null;
        }
      };
      //根据元素删除指定元素，成功 返回元素， 失败 返回null
      LinkedList.prototype.remove = function(element){
        var index = this.indexOf(element);
        return this.removeAt(index);
      };
      //返回给定元素的索引，如果没有则返回-1
      LinkedList.prototype.indexOf = function(element){
        var current = this.head;
        var index = 0;
        while(current){
          if(current.element === element){
            return index;
          }
          index++;
          current = current.next;
        }
        return -1;
      };
      LinkedList.prototype.isEmpty = function(){
        return this.length === 0;
      };
      LinkedList.prototype.size = function(){
        return this.length;
      };
      LinkedList.prototype.toString = function(){
          var string = '';
          var current = this.head;
          while(current){
            string += current.element;
            current = current.next;
          }
          return string;
      };
      LinkedList.prototype.getHead = function(){
        return this.head;
      };
    }
  }
  // test
  var linkedList = new LinkedList();
  console.log(linkedList.isEmpty());//true;
  linkedList.append('a');
  linkedList.append('c')
  linkedList.insert(1,'b');
  console.log(linkedList.toString());// 'abc'
  console.log(linkedList.indexOf('c'));//2
  console.log(linkedList.size());//3
  console.log(linkedList.removeAt(2));//c
  console.log(linkedList.toString());//'ab'
  

• 双向链表
• 双向链表和普通链表的区别在于,在链表中, 一个节点只有链向下一个节点的链接,而在双向链表中,链接是双向的:一个链向下一个元素, 另一个链向前一个元素。
• 代码实现

//寄生组合式继承实现，详见javascript高级程序设计第七章
   function inheritPrototype(subType, superType) {
       function object(o) {
           function F() {}
           F.prototype = o;
           return new F();
       }
       var prototype = object(superType.prototype);
       prototype.constructor = subType;
       subType.prototype = prototype;
   }
   function DoublyLinkedList() {
       function Node(element) {
           this.element = element;
           this.next = null;
           this.prev = null;
       }
       this.tail = null;
       LinkedList.call(this);
       //与LinkedList不同的方法自己实现。
       this.insert = function(position, element) {
           if (position > -1 && position <= this.length) {
               var node = new Node(element);
               var current = this.head;
               var previous;
               var index = 0;
               if (position === 0) {
                   if (!this.head) {
                       this.head = node;
                       this.tail = node;
                   } else {
                       node.next = current;
                       current.prev = node;
                       this.head = node;
                   }
               } else if (position == this.length) {
                   current = this.tail;
                   current.next = node;
                   node.prev = current;
                   this.tail = node;
               } else {
                   while (index++ < position) {
                       previous = current;
                       current = current.next;
                   }
                   previous.next = node;
                   node.next = current;
                   current.prev = node;
                   node.prev = previous;
               }
               this.length++;
               return true;
           } else {
               return false;
           }
       };
       this.append = function(element) {
           var node = new Node(element);
           var current;
           if (this.head === null) {
               this.head = node;
               this.tail = node;
           } else {
               current = this.head;
               while (current.next !== null) {
                   current = current.next;
               }
               current.next = node;
               node.prev = current;
               this.tail = node;
           }
           this.length++;
       };
       this.removeAt = function(position) {
           if (position > -1 && position < this.length) {
               var current = this.head;
               var previous;
               var index = 0;
               if (position === 0) {
                   this.head = current.next;
                   if (this.length === 1) {
                       this.tail = null;
                   } else {
                       this.head.prev = null;
                   }
               } else if (position === (this.length - 1)) {
                   current = this.tail;
                   this.tail = current.prev;
                   this.tail.next = null;
               } else {
                   while (index++ < position) {
                       previous = current;
                       current = current.next;
                   }
                   previous.next = current.next;
                   current.next.prev = previous;
               }
               this.length--;
               return current.element;
           } else {
               return false;
           }
       };
   }
   inheritPrototype(DoublyLinkedList, LinkedList);

//    test
 var doublyList = new DoublyLinkedList();
    console.log(doublyList.isEmpty()); //true;
    doublyList.append('a');
    doublyList.append('c')
    doublyList.insert(1, 'b');
    console.log(doublyList.toString()); //'abc'
    console.log(doublyList.indexOf('c')); //2
    console.log(doublyList.size()); //3
    console.log(doublyList.removeAt(2)); //c
    console.log(doublyList.toString()); //'ab'