雖然前端對于算法的要求并不高，但是工作和面試偶爾還是會遇到排序算法和二分查找法。筆者通過這篇文章對排序和查找簡單總結(jié)，既是總結(jié)筆記以便以后參考，也是供大家一起學習交流。
注：以下所有排序都是由小到大升序排列。

冒泡排序

冒泡算法原理是數(shù)組里每相鄰的兩個數(shù)相比較，如果兩數(shù)中后者小于前者，則交換位置，否則不變，這樣一次遍歷下來，數(shù)組中最后一個數(shù)是最大的數(shù)，這樣的遍歷進行arr.length（數(shù)組長度）次，數(shù)組元素將順次排序。數(shù)組元素交換像冒泡一樣，所以叫冒泡排序。
平均時間復雜度：O(n^2)。

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;
}

選擇排序

選擇排序原理每次選擇數(shù)組中未排序中最小的，放到數(shù)組前面，這樣前面部分元素已順序排列。對未排序部分遍歷arr.length次，數(shù)組元素將順次排序。
時間復雜度O(n^2)。

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]) {     //尋找最小的數(shù)
                minIndex = j;                 //將最小數(shù)的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

插入排序

插入排序過程：數(shù)組被分為兩部分已排序部分，待排序部分，待排序部分第一個元素，與已排序部分每個元素比較，如果發(fā)現(xiàn)已排序元素大于未排序元素，則已排序元素向后移一位，否則未排序元素插入后一位。
時間復雜度：O(n^2)。

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;
}

希爾排序

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {          //動態(tài)定義間隔序列
        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;
}

歸并算法

運用了分而治之的思想，將數(shù)組分為兩半，分別排序在將兩部分合并，而分開的兩部分在進行同樣的操作，也就是遞歸的思想，最終實現(xiàn)升序排列。

function mergeSort(arr) {  //采用自上而下的遞歸方法
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result = [];

    while (left.length>0 && right.length>0) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

快速排序

首先在這個序列中隨便找一個數(shù)作為基準數(shù)。接下來，需要將這個序列中所有比基準數(shù)大的數(shù)放在基準數(shù)的右邊，比基準數(shù)小的數(shù)放在基準數(shù)的左邊。

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));
};

堆排序

大頂堆：根節(jié)點為最大值， 每個節(jié)點的值大于等于孩子節(jié)點。
小頂堆：根節(jié)點為最小值，每個節(jié)點的值小于等于孩子節(jié)點。
建立大頂堆，將根節(jié)點移到數(shù)組最后，調(diào)整未排序部分，循環(huán)往復最終得到升序數(shù)組。

function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function shiftDown(arr, i, length) {
  let temp = arr[i];
  for (let j = 2 * i + 1; j < length; j = 2 * j + 1) {
    temp = arr[i];
    if (j + 1 < length && arr[j] < arr[j + 1]) {
      j++;
    }
    if (temp < arr[j]) {
      swap(arr, i, j);
      i = j;
    } else {
      break;
    }
  }
}

function heapSort(arr) {
  for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) {
    shiftDown(arr, i, arr.length);
  }

  for (let i = Math.floor(arr.length - 1); i > 0; i--) {
    swap(arr, 0, i);
    shiftDown(arr, 0, i);
  }
  return arr;
}

二分查找法

二分查找法用于在有序數(shù)組里查找目標值，先檢驗中間項和目標值的大小，如果相同則返回下標，如果中間項小于目標值，則在中間項的右側(cè)尋找目標值，如果中間項大于目標值，則在中間項的左側(cè)尋找目標值，循環(huán)往復直到數(shù)組遍歷完或找到目標。

function binarySearch(target, arr) {
  var start = 0;
  var end = arr.length - 1;

  while (start <= end) {
    var mid = parseInt(start + (end - start) / 2);
    if (target == arr[mid]) {
      return mid;
    } else if (target > arr[mid]) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return -1;
}