摘要：本文簡(jiǎn)單介紹幾個(gè)常見(jiàn)的排序算法，包括：冒泡排序、選擇排序、插入排序、快速排序、歸并排序、希爾排序。列出的代碼為 JavaScript 實(shí)現(xiàn)，標(biāo)題后表示的是該排序算法的時(shí)間復(fù)雜度。

冒泡排序 —— 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)

• 遞歸版（存在空間浪費(fèi)）

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

• 遞歸的進(jìn)階版（在原數(shù)組上操作，最典型的快排寫法）
  該方法大致流程如下：
  1. 對(duì)于一個(gè)數(shù)組，挑選最后一個(gè)值作為參考值(key)
  2. 從數(shù)組的頭部開(kāi)始掃描，如果值比參考值小，繼續(xù)往后掃描，直到掃描到的值(左值)比參考值大
  3. 從數(shù)組的尾部(參考值的前一個(gè))開(kāi)始掃描，如果值比參考值大，繼續(xù)往前掃描，直到掃描到的值(右值)比參考值小
  4. 此時(shí)交換掃描停止時(shí)的這兩個(gè)值
  5. 繼續(xù)上面的邏輯，直到左值和右值相遇
  6. 如果相遇時(shí)的值大于等于參考值，讓參考值和相遇值調(diào)換位置(一般情況)
  7. 如果相遇時(shí)的值小于參考值，不調(diào)換，但 left 后移以為 (特殊情況，如 [2, 1, 3, 4, 5])
  8. 經(jīng)過(guò)上面的處理后，就會(huì)把數(shù)組變成以原數(shù)組末尾數(shù)字為分割（左邊都比它小，右邊都比它大）的數(shù)組。然后分別對(duì)參考值左側(cè)和右側(cè)通過(guò)類似的邏輯繼續(xù)處理。

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. 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列
  2. 設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
  3. 比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
  4. 重復(fù)步驟3直到某一指針到達(dá)序列尾
  5. 將另一序列剩下的所有元素直接復(fù)制到合并序列尾

/*
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)

原理：先將整個(gè)待排數(shù)組分割成若干個(gè)子數(shù)組（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序，待整個(gè)數(shù)組中的元素基本有序（增量足夠?。r(shí)，再對(duì)全體元素進(jìn)行一次直接插入排序。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下效率是很高的，因此希爾排序在時(shí)間效率上較大提高。

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)