前端算法（更新中）

二分法查找

采用二分法查找时，数据需是排好序的。
主要思想是：（设查找的数组区间为array[s, e]）
（1）确定该区间的中间位置m
（2）将查找的值T与array[m]比较,若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。

function binarySeach(arr,val,leftIndex,rightIndex){ var middleIndex=Math.floor((leftIndex+rightIndex)/2); var middleVal=arr[middleIndex]; if(leftIndex>rightIndex){ console.log('前一位数据是：'+middleVal,'下标是：'+middleIndex); return; } if(middleVal>val){ binarySeach(arr,val,leftIndex,middleIndex-1) }else if(middleVal<val){ binarySeach(arr,val,middleIndex+1,rightIndex) }else{ console.log('找到了，下标为：'+middleIndex); return middleIndex; } } var arr=[1,3,12,21,24,44,54,67]; binarySeach(arr,24,0,arr.length-1); 

插入排序

function insertSort(arr) { for (var i = 1; i < arr.length; i++) { var temp = arr[i]; var j = i - 1; while (j >= 0 && arr[j] > temp) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = temp; } return arr; } var arr = [1, 45, 37, 5, 48, 15, 37, 26, 29, 2, 46, 4, 17, 50, 52]; console.log(insertSort(arr)); 

冒泡排序

function sort(arr){ for(var i=0;i<arr.length;i++){ for(var j=0;j<arr.length-i-1;j++){ if(arr[j]>arr[j+1]){ var temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } return arr; } 

双向链表

 function Node(element) { this.element=element; this.next=null; this.previous=null; } function find(element) { var currentNode=this.head; while(currentNode.element!=element){ if(currentNode.next==null){ console.log('无法找到'); return 'error'; } currentNode=currentNode.next; } return currentNode; } function insert(newElement,currentElement) { var newNode=new Node(newElement); var currentNode=this.find(currentElement); if(currentNode=='error'){ console.log('无法插入'); return; } if(currentNode.next!=null){ newNode.next=currentNode.next; currentNode.next=newNode; newNode.previous=currentNode; newNode.next.previous=newNode; } else{ currentNode.next=newNode; newNode.previous=currentNode; } } function remove(element) { var currentNode=this.find(element); if(currentNode=='error'){ console.log('要移除的节点不存在'); return; } //不是尾节点也不是头节点 if(currentNode.next!=null&&currentNode.previous!=null){ currentNode.previous.next=currentNode.next; currentNode.next.previous=currentNode.previous; currentNode.next=null; currentNode.previous=null; } //头节点 else if(currentNode.next!=null&&currentNode.previous==null){ this.head=currentNode.next; currentNode.next=null; currentNode.previous=null; } //尾节点 else{ currentNode.next=null; currentNode.previous=null; } } function showList(){ var head=this.head; while(head!=null){ console.log(head.element); head=head.next; } } function lastNode() { var head=this.head; while(head.next!=null){ head=head.next; } return head; } function append(element) { var lastNode=this.lastNode(element); var newNode=new Node(element); lastNode.next=newNode; newNode.previous=lastNode; } function initList() { this.head = new Node('one'); this.find = find; this.insert = insert; this.remove = remove; this.showlist = showList; this.lastNode = lastNode; this.append = append; } var list=new initList(); list.insert('two','one'); list.insert('three','two'); list.insert('four','three'); list.insert('five','four'); //console.log(list.showlist());//one two three four five list.append('A'); list.append('B'); list.append('C'); list.insert('B2','B'); //console.log(list.showlist()); //one two three four five A B B2 C list.remove('A'); //console.log(list.showlist());//one two three four five B B2 C console.log(list.head);//