JS实现常见算法

1. 冒泡排序
   要点：相邻元素两两对比，若前面大于后面，则交换位置。

function bubbleSort(arr) {
  var len = arr.length;

  for(var i=0; i<len; i++){
    for(var j=0; j<len-1-i; j++){
      if(arr[j] > arr[j+1]){
        var temp = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = temp;
      }
    }
  }

  return arr;
}

2. 选择排序
   要点：从第一个元素开始，与其后面的元素对比，找到最小的互换位置。

function selectionSort(arr) {
  var len = arr.length;

  for(var i=0; i<len-1; i++){
    var minIndex = i;
    for(var j=i+1; j<len; j++){
      if(arr[j] < arr[minIndex]){
        minIndex = j;
      }
    }
    var temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }

  return arr;
}

3. 插入排序
   要点：从第二个元素开始，暂存当前元素。倒序遍历前面的元素，如果大于当前元素，则将其往后移动一位，直到跳出遍历，将之前暂存的元素插入到跳出遍历时的后一位。

function insertionSort(arr) {
  var len = arr.length;

  var preIndex, current;
  for(var i=1, i<len; i++){
    preIndex = i - 1;
    current = arr[i];
    while (preIndex >=0 && arr[preIndex] > current) {
      arr[preIndex+1] = arr[preIndex];
      preIndex --;
    }
    arr[preIndex+1] = current;
  }

  return arr;
}

4. 二分查找

function binarySearch(arr, num, start, end) {
  var start = start || 0,
      end = end || arr.length;

  var mid = Math.floor((start + end) / 2);
  var midVal = arr[mid]

  if (start >= end) {
    return false
  }

  if (midVal === num) {
    return mid
  } else {
    if (midVal > num) {
      return binarySearch(arr, num, 0, mid)
    } else {
      return binarySearch(arr, num, mid + 1, arr.length)
    }
  }
}

5. 遍历二叉树
   先序遍历

var preTraverse = function (node) {
  if (node) {
    console.log(node.value);
    preTraverse(node.left);
    preTraverse(node.right);
  }
}