摘要：本文简单介绍几个常见的排序算法，包括：冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序。列出的代码为 JavaScript 实现，标题后表示的是该排序算法的时间复杂度。

冒泡排序 —— O(n^2)

function bubbleSort (array) {
  for(let i = 0; i < array.length; i++){
    for(let j = 1; j < array.length; j++){
      if(array[i] > array[j]){
        [array[i], array[j]] = [array[j], array[i]]
      }
    }
  }
  return array
}

选择排序 —— O(n^2)

function selectionSort (array) {
  let min = null
  for(let i = 0; i < array.length; i++){
    min = i
    for(let j = i + 1; j < array.length; j++){
      if(array[min] > array[j]){
        min = j
      }
    }
    [array[i],array[min]] = [array[min],array[i]]
  }
  return array
}

插入排序 —— O(n^2)

• 普通版

function insertionSort (array) {
  let temp = null
  for(let i = 1; i < array.length; i++){
    temp = array[i]
    for(var j = i; j >=0 && temp < array[j-1]; j--){
      array[j] = array[j-1]
    }
    array[j] = temp
  }
  return array
}

• JS版( 使用splice )

function insertionSort (array) {
  for(let i = 1; i < array.length; i++){
    for(var j = 0; j < i; j++){
      if(array[i] < array[j]){
        array.splice(j,0,array[i])
        array.splice(i+1,1)
        break
      }
    }
  }
  return array
}

快速排序 —— O(nlogn)

• 递归版（存在空间浪费）

function quickSort (array) {
  if(array.length <= 1) {
    return array
  }
  let leftArray = [] 
  let rightArray = []
  for(let i = 1; i < array.length; i++){
    if(array[i] >= array[0]) {
      rightArray.push(array[i])
    } else {
      leftArray.push(array[i])
    }
  }
  return quickSort(leftArray).concat(array[0]).concat(quickSort(rightArray))
}

• 递归的进阶版（在原数组上操作，最典型的快排写法）
  该方法大致流程如下：
  1. 对于一个数组，挑选最后一个值作为参考值(key)
  2. 从数组的头部开始扫描，如果值比参考值小，继续往后扫描，直到扫描到的值(左值)比参考值大
  3. 从数组的尾部(参考值的前一个)开始扫描，如果值比参考值大，继续往前扫描，直到扫描到的值(右值)比参考值小
  4. 此时交换扫描停止时的这两个值
  5. 继续上面的逻辑，直到左值和右值相遇
  6. 如果相遇时的值大于等于参考值，让参考值和相遇值调换位置(一般情况)
  7. 如果相遇时的值小于参考值，不调换，但 left 后移以为 (特殊情况，如 [2, 1, 3, 4, 5])
  8. 经过上面的处理后，就会把数组变成以原数组末尾数字为分割（左边都比它小，右边都比它大）的数组。然后分别对参考值左侧和右侧通过类似的逻辑继续处理。

function quickSort(arr) {
  function _quickSort(arr, start, end) {
    if(start >= end) return
    let key = arr[end]
    let left = start, right = end - 1
    while(left < right) {
      while(arr[left] < key && left < right) left++
      while(arr[right] >= key && left < right) right--
      [arr[left], arr[right]] = [arr[right], arr[left]]
    }
    if(arr[left] >= arr[end]) { 
      [arr[left], arr[end]] = [arr[end], arr[left]]
    } else {  // 如 [2, 1, 3, 4]
      left++
    }
    _quickSort(arr, start, left - 1)
    _quickSort(arr, left + 1, end)
  }
  _quickSort(arr, 0, arr.length - 1)
  return arr
}

归并排序 —— O(nlogn)

• 大致流程：
  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  4. 重复步骤3直到某一指针到达序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

/*
left : [1, 3, 4, 7]
right: [2, 5, 6, 9]
result: [1, 2, 3, 4, 5, 6, 7, 9]
 */

function mergeSort(arr) {
  var merge = function(left, right) {
    var result = []
    while(left.length && right.length) {
      result.push(left[0] <= right[0] ? left.shift() : right.shift())
    }
    return result.concat(left.concat(right))
  }
  if(arr.length < 2) return arr
  var mid = arr.length >> 1
  return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)))
}

希尔排序 —— O(nlog2n)

原理：先将整个待排数组分割成若干个子数组（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个数组中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下效率是很高的，因此希尔排序在时间效率上较大提高。

function shellSort(arr) {
  var temp
  var len = arr.length
  for (var gap = len >> 1; gap > 0; gap = gap >>=1) {
    for (var i = gap; i < len; i++) {
      temp = arr[i]
      for( j = i - gap; j >=0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j]
      }
      arr[j + gap] = temp
    }
    console.log(arr)
  }
}

var arr = [3, 1, 7, 2, 5, 0, 4, 6]
shellSort(arr)
console.log(arr)