JavaScript 实现几种常见的排序及二分查找

首先，在切入正题之前，先提一下某同事前段时间的面试。前段时间某同事去某大厂面试，面的不好。面试问到的好多深入的问题，没答上来或者答得不全。大厂就是大厂，要求面试者不仅在广度上，而且在深度上也都要有一定的积累，个人理解就是你不仅要知道这是什么，而且还要知道这是为什么，甚至还要知道这样有什么好处和不好之处。一路面下来，各种被鄙视。比如，前端的优化方法有哪些，说说你在工作中做了哪些优化？Web 安全有哪些，又是如何去防御或者规避？HTTP 缓存的原理，缓存的过程是什么样子的？等等……当然，也问到了一些简单的算法问题，当时有点懵逼了，虽然大学的时候学过，但是时间久了，统统还给老师了，尴尬。对于算法，虽然相对后端语言来说，前端工作中还是比较少接触算法的，就算会接触，大都不会太复杂，但是一些简单的算法也是不得不知道的，大厂们都比较重视这个。

排序。排序是我们最常见的算法题目，当然工作中也会遇到（前端 js API 里面已经有封装一个叫 sort 的方法），但，后面将要介绍几种排序是用 js 实现的方法。在这里整理一下，需要的时候可以翻看一下;

查找。顺便总结一下常见的一些查找，如二分查找。

一、冒泡排序

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

// es6
function BubleSort(arr) {
  const len = arr.length;
  for (let i = len - 1; i > 0; i--) {
    if (let j = 0; j < i; j++) {
      if (arr[j] > arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
  }
  return arr;
}

复杂度：

平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
O(n^2)	O(n)	O(n^2)	O(1)	稳定

二、选择排序

function SelectionSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len; i++) {
    var min = arr[i];
    var index = i;
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < min) {
        min = arr[j];
        index = j;
      }
    }
    if (index != i) {
      var temp = arr[i];
      arr[i] = arr[index];
      arr[index] = temp;
    }
  }
  return arr;
}

// es6
function SelectionSort(arr) {
  const len = arr.length;
  for (let i = 0 ;i < len - 1; i++) {
    for (let j = i ; j<len; j++) {
	   if (arr[j] < arr[i]) {
	     [arr[i],arr[j]] = [arr[j],arr[i]];
	   }
	 }
  }
  return arr
}

复杂度：

平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定

三、插入排序

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

// es 6
function InserttionSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = i; j > 0; j--) {
      if (arr[j] < arr[j-1]) {
        [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
      } else {
        break;
      }
    }
  }
}

复杂度：

平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
O(n^2)	O(n)	O(n^2)	O(1)	稳定

四、希尔排序

function ShellSort(arr) {
  var len = arr.length;
  var gap = Math.round(len / 2);
  while (gap > 0) {
    for (var i = gap; i < len; i++) {
      var insert = arr[i];
      var index = i;
      for (var j = i; j >= 0; j -= gap) {
        if (insert < arr[j]) {
          arr[j + gap] = arr[j];
          index = j;
        }
      }
      arr[index] = insert;
    }
    gap = Math.round(gap/2 - 0.1);
  }
  return arr;
}

复杂度：

平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
O(n^1.3)	O(n)	O(n^2)	O(1)	不稳定

五、归并排序

function merge(leftArr, rightArr) {  
  var result = []
  while (leftArr.length > 0 && rightArr.length > 0) {  
    if (leftArr[0] < rightArr[0])  
      result.push(leftArr.shift()) // 把最小的最先取出，放到结果集中   
    else   
      result.push(rightArr.shift())
  }   
  return result.concat(leftArr).concat(rightArr)  // 剩下的就是合并，这样就排好序了  
}  

function mergeSort(array) {  
  if (array.length == 1) return array
  var middle = Math.floor(array.length / 2)       // 求出中点  
  var left = array.slice(0, middle)               // 分割数组  
  var right = array.slice(middle)  
  return merge(mergeSort(left), mergeSort(right)) // 递归合并与排序  
} 

复杂度：

平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
O(n*log(n)) (n乘以n的以2为底的对数)	O(n*log(n))	O(N*log(n))	O(n)	稳定

六、快速排序

function QuickSort(arr) {
  var len = arr.length;
  if (len <= 1) {
    return arr;
  } else {
    var smaller = [];
    var bigger = [];
    var base = [arr[0]];
    for (var i = 1; i < len; i++) {
      if (arr[i] <= base[0]) {
        smaller.push(arr[i]);
      } else {
        bigger.push(arr[i]);
      }
    }
    return QuickSort(smaller).concat(base.concat(QuickSort(bigger)));
  }
}

// es6
function QuickSort(arr) {
  const len = arr.length;
  if (len <= 1) {
    return arr;
  } else {
    const smallers = [];
    const biggers = [];
    const base = arr[0];
    for (let i = 1; i < len; i++) {
      if (arr[i] <= base) {
        smallers.push(arr[i]);
      } else {
        biggers.push(arr[i]);
      }
    }
    return [...QuickSort(smallers), base, ...QuickSort(biggers)];
  }
}

复杂度：

平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
O(n*log(n)) (n乘以n的以2为底的对数)	O(n*log(n))	O(n^2)	O(log(n))~O(n)	不稳定

七、二分查找

二分查找，也称为折半查找，是指在有序的数组里找出指定的值，返回该值在数组中的索引。

1. 递归实现

// 递归实现的js代码
// 查找值为 key 所在数组中的下标
function binary_search2(arr, low, high, key) {
    if (low > high) {
        return -1;
    }
    var mid = parseInt((high + low) / 2);
    if (arr[mid] === key) {
        return mid;
    } else if (arr[mid] > key) {
        high = mid -1;
        return binary_search2(arr, low, high, key);
    } else if (arr[mid] < key) {
        low = mid +1;
        return binary_search2(arr, low, high, key);
    }
}

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 23, 44, 86];
var result2 = binary_search2(arr, 0, 13, 10);
console.log(result2);   // 9

2. 非递归实现

// 非递归实现的js代码
// 查找值为 key 所在数组中的下标
function binary_search(arr, key) {
    var low = 0;
    var high = arr.length - 1;
	 // 遍历 
    while (low <= high) {
        var mid = parseInt((high + low) / 2);
        if (key === arr[mid]) {
            return mid;
        } else if (key > arr[mid]) {
            low = mid + 1;
        } else if (key < arr[mid]) {
            high = mid -1;
        } else {
            return -1;
        }
    }
}

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 23, 44, 86];
var result = binary_search(arr, 10);
console.log(result);   // 9

以上代码是笔者参考网上，经过整理而成，有遗漏之处，欢迎指正。