摘要：適用于數據比較少或基本有序的情況。插入排序時間復雜度為，空間復雜度為，屬于穩定排序。算法適用于少量數據的排序。就像下圖這樣，可以理解桶的意思下圖是整個排序過程示意圖基數排序時間復雜度為，空間復雜度為，屬于穩定排序。

寫在前面

個人感覺：javascript對類似排序查找這樣的功能已經有了很好的封裝，以致于當我們想對數組排序的時候只需要調用arr.sort()方法，而查找數組元素也只需要調用indexOf()方法或lastIndexOf()方法，我們忽略了其內部的實現。而今，js能開發的項目越來越龐大，對性能和效率要求也越來越高，雖然眾多的庫和框架也可以幫我們應付這些問題，但小編覺得框架過眼云煙，把握程序開發的基礎，才能在飛速的更新換代中應對自如。因此我們不妨也研究一下這些算法，其中的思路有助于我們自身的提高。

聲明：本文章中的部分圖片來自百度搜索，如侵刪。

這個是最簡單的排序，就像氣泡從水里冒出來。
它每執行一次外層循環，就會將最小數（或最大的）放到數組最后，然后再尋找剩余部分的最小數（或最大的）放在這一部分的最后，以此類推。
每一個外層循環的過程可以用一下圖來描述：

冒泡排序的時間復雜度為$O(n^2)$，空間復雜度為$O(1)$，屬于 穩定 排序。適用于數據比較少或基本有序的情況。

//冒泡排序
bubbleSort = function(arr){
  var len = arr.length;
  for (var i = 0; i < len; i++){
    for (var j = 0; j < len - i - 1; j++){
      if (arr[j] > arr[j + 1])
        [arr[j + 1], arr[j]] = [arr[j],arr[j + 1]];
    }
  }
}

選擇排序也很簡單。它每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。下面是完整的選擇排序過程：

選擇排序的時間復雜度為$O(n^2)$，空間復雜度為$O(1)$，屬于 穩定 排序。適用于數據比較少的情況，綜合各種情況來講還是這個最慢。

//選擇排序
 selectionSort = function(arr){
  var len = arr.length;
  var min, min_index;//min每次找到的最小值，min_index最小值在無序序列的位置
  for (var i = 0; i < len - 1; i++){
    min = arr[i];
    for (var j = i + 1; j < len; j++){//找到最小值
      if (arr[j] < min){
        min = arr[j];//找到的最小值
        min_index = j;//找到的最小值索引
      }
    }
    if (min != arr[i])
      [arr[min_index], arr[i]] = [arr[i], arr[min_index]];
  }
}

這個要略微復雜一點了。它的思路就是將一個數據插入到已經排好序的有序數據中，依然保持有序。實現過程把數組看作2部分，一部分是有序的，一部分是無序的，每次大循環將無序數組的第一個元素插入到有序的數組中。

插入排序時間復雜度為$O(n^2)$，空間復雜度為$O(1)$，屬于 穩定 排序。算法適用于少量數據的排序。

注：二分插入和直接插入各種情況復雜度一樣

//直接插入排序
insertionSort = function (arr){
  var len = arr.length;
  var temp;//temp每次要執行插入的值
  var index;//index插入值在有序序列的位置
  for (var i = 1; i < len; i++){
    temp = arr[i];
    for (var j = 0; j < i; j++){//找到插入位置
      index = i;
      if (arr[j] > temp){
        index = j;//找到的插入點索引
        break;
      }
    }
    if (i != index){
      for (var j = i; j > index; j--)//插入該值
        [arr[j - 1], arr[j]] = [arr[j],arr[j - 1]];
    }
    arr[index] = temp;
  }
}

這個想必大家都耳熟能詳，20世紀十大經典算法之一。主要原因還是它極大的推動了信息技術的發展，可惜它不是穩定算法。
這個算法比較就比較難理解了，它通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的任一數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。這里面包含的分治的思想。
下面一個圖表現了函數的一次執行過程：

而這個圖表現了整個排序過程：

插入排序時間復雜度為$O(nlogn)$，空間復雜度為$O(logn)$，屬于 不穩定 排序。

////快速排序(前軸）
function quickSort(arr){
  qSort(0, arr.length - 1);
  return arr;

  function qSort(left, right){
    if (left >= right)//兩個數相遇則結束該輪排序
      return;
    var key = arr[left];//取最左邊的元素作為標識數
    var i = left;
    var j = right;
    while (i != j){//兩個數相遇則結束該輪排序
      while (i != j && arr[j] >= key) j--;//j前移
      [arr[j], arr[i]] = [arr[i], arr[j]];
      while (i != j && arr[i] <= key) i++;//i后移
      [arr[j], arr[i]] = [arr[i], arr[j]];
    }
    qSort(left, j - 1);//對標識數前面的數繼續該方法排序
    qSort(j + 1, right);//對標識數后面的數繼續該方法排序
  }
}

這里補充一下：快速排序由于其實軸的選擇不同，分為前軸、中軸、后軸快速排序，上面的例子是前軸快速排序，下文比較算法的時候也才用上述代碼。不過，這里補充另外2種代碼：

//中軸快速排序
function quickSortM(arr){
  qSort(0, arr.length - 1);
  return arr;

  function qSort(left, right){
    if (left < right){
      var index = Math.floor((left + right) / 2);
      var key = arr[index];
      var i = left - 1;
      var j = right + 1;
      while (true){
        while (arr[++i] < key); // 向右找大于軸的數
        while (arr[--j] > key); // 向左找小于軸的數
        if (i >= j)//兩索引相同結束排序
          break;
        [arr[i], arr[j]] = [arr[j],arr[i]];//交換找到的數
      }
      qSort(left, i - 1); // 繼續這樣對軸前面的排序
      qSort(j + 1, right); // 繼續這樣對軸后面的排序
    }
  }
}

//后軸快速排序
function quickSortB(arr){
  qSort(0, arr.length - 1);
  return arr;

  function qSort(left, right){
    if (left >= right)//兩索引相同結束排序
      return;
    var key = arr[right];
    var i = left - 1;//s是最右邊的軸
    for (var j = left; j < right; j++){ //將數據分成大于軸和小于軸兩部分
      if (arr[j] <= key){
        i++;
        [arr[i], arr[j]] = [arr[j],arr[i]];
      }
    }
    i++;
    [arr[right], arr[i]] = [arr[i],arr[right]];//將軸插入到大于軸和小于軸兩部分的中間
    qSort(left, i - 1);//繼續這樣對軸前面的排序
    qSort(i, right);//繼續這樣對軸后面的排序
  }
}

這個排序在小編眼里用的是最廣泛的，很多函數封裝內部都才用這個排序，包括數據庫在內的排序也采用了歸并排序或紅黑樹的形式。這個排序也用到了分治的思想：它將一個序列逐級拆分成小序列，將小序列排序后合并，得到完全有序的序列。若每次將序列分成2個子序列，再依此合并，稱為二路歸并。
沒理解？看圖：

插入排序時間復雜度為$O(nlogn)$，空間復雜度為$O(n)$，屬于 穩定 排序。

//歸并排序
function mergeSort(arr){
  var temp = [];
  merge(0, arr.length - 1);
  return arr;

  function merge(left, right){//temp是臨時空間，存放排序過程中間結果
    var mid;//該部分中間位置
    if (left >= right)//分組小于等于1時歸并結束
      return;
    mid = Math.floor((left + right) / 2);
    merge(left, mid);//對中間位置之前部分繼續該方法排序
    merge(mid + 1, right);//對中間位置之后部分繼續該方法排序
    var i = left, j = mid + 1, k = left;
    while (i != mid + 1 && j != right + 1)//比較兩部分每個值，把較小的放入temp中，并后移該指針，直到某部分全部遍歷
      temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    //將未全部遍歷部分數據順次放入temp中
    while (i != mid + 1)
      temp[k++] = arr[i++];
    while (j != right + 1)
      temp[k++] = arr[j++];
    //將temp復制會a中
    for (i = left; i <= right; i++)
      arr[i] = temp[i];
  }
}

這是惟一一個用人名命名的排序算法。它把數據按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。
這個估計最不好理解了，看看圖吧：

希爾排序時間復雜度為$O(n^frac1{3})$，空間復雜度為$O(1)$，屬于 不穩定 排序。

//希爾排序
shellSort = function(arr){
  var len = arr.length;
  var index = Math.floor(len / 2);//得到比較步長
  var j, temp;
  while (index > 0){
    for (var i = index; i < len; i++){//遍歷起點后移，保證每個數在該步長下參與且只參與1此排序
      temp = arr[i];
      for (j = i; j >= index && arr[j - index] > temp;){//等步長數列執行插入排序
        arr[j] = arr[j - index];
        j -= index;
        arr[j] = temp;
      }
    }
    index = Math.floor(index / 2);//步長減半
  }
}

首先說一下一個名詞：大根堆。大根堆的要求是每個節點的值都不大于其父節點的值，即$A[PARENT[i]] geq A[i]$， 屬于完全二叉樹。
根據大根堆的要求可知，最大的值一定在堆頂，根據其特點，如果要求每個節點的左孩子小于右孩子，得到的就是數據從小到大的排列。反之從大到小排列應該使用小根堆。
如果你對二叉樹熟悉的話，可以簡單用圖理解一下

堆排序時間復雜度為$O(nlogn)$，空間復雜度為$O(1)$，屬于 不穩定 排序。
下面利用數組快速定位指定索引的元素模擬堆操作，并沒有實際建立二叉樹。

//堆排序
heapSort = function(arr){
  var len = arr.length;
  for (var i = len / 2 - 1; i >= 0; i--)//反向遍歷數組，將數組調整為大根堆
    heapAdjust(arr, i, len);
  for (var i = len - 1; i > 0; i--){
    [arr[0], arr[i]] = [arr[i], arr[0]];//將無需部分最大數放在最后，即構成有序部分
    heapAdjust(arr, 0, i);//將剩余無需部分調整為大根堆，直到該部分只有一個元素為止
  }
  return arr;

  function heapAdjust(arr, i, len){//二叉堆調整函數，負責將堆調整成大根堆（因為是增序排列）
    var child;//根孩子的索引
    var temp;
    //以等倍數間隔，調整堆為大根堆
    for (; 2 * i + 1 < len; i = child){
      child = 2 * i + 1;  //定位其左孩子
      if (child < len - 1 && arr[child + 1] > arr[child])//從其左右孩子中選擇最大的孩子
        child++;
      if (arr[i] < arr[child])//如果自己比最大的孩子小，和該孩子交換
        [arr[child], arr[i]] = [arr[i], arr[child]];
      else
        break;
    }
  }
}

這個排序是對費空間的，不過這個思想有點像哈希表的意思。顧名思義，它是透過鍵值的部份資訊，比如每個數的最高位(如果位數不同在前方補零)，將要排序的元素分配至某些“桶”中，依次從低位到高位執行，然后再把每個桶的數據順序綜合起來，以達到排序的作用。就像下圖這樣，可以理解桶的意思：

下圖是整個排序過程示意圖：

基數排序時間復雜度為$O(d(r+n))$，空間復雜度為$O(rd+n)$，屬于 穩定 排序。（其中r為基數，n為數據總數，d為桶數；也有書得到其平均時間復雜度為$O(nlog_{r}d)$）

//基數排序(桶排序)
radixSort = function(arr){
  var len = arr.length;
  var bullet= [];
  var k=1, temp;//k是處理數字的權重，k=1表示處理個位數，k=10表示處理十位數，以此類推
  for (var i = 0; i < 10; i++)//為每個桶分配內存空間
    bullet[i] = [];
  while (true){
    var num = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ];//num用來統計0~9每個桶里面現有數字個數
    for (var i = 0; i < len; i++){//統計分配每個數字到桶里面，并統計每個桶數字個數
      temp = Math.floor(arr[i] / k) % 10;
      bullet[temp][num[temp]++] = arr[i];
    }
    if (num[0] == len) break;//當全部數字都在編號為0的桶中，排序結束
    //將桶里的數依次放回a數組中
    for (var i = 0; i < len; i++){
      for (var j = 0; j < 10; j++){
        for (var r = 0; r < num[j]; r++)
          arr[i++] = bullet[j][r];
      }
    }
    k *= 10;//k增加10倍，從右至左處理下一位數字
  }
  return arr;
}

以上是常見的8種排序算法，小編也把結果寫出來把。下面是10個隨機數的排序效果：

當然還有算法速度，小編用了2萬個均勻分布在0到10000的隨機數，得到如下結果：

不過實際使用中，并不是越快越好，而且即便是追求快也和數據本身的質量有關系。就像下面這個表中的：

注:

基數排序的復雜度中，$r$ 代表關鍵字基數，$d$ 代表長度，$n$ 代表關鍵字個數

排序算法的穩定性指在原序列中，$r_i=r_j$，且 $r_i$ 在 $r_j$ 之前，而在排序后的序列中，$r_i$ 仍在 $r_j$ 之前，則稱這種排序算法是穩定的；否則稱為不穩定的。

開發的時候應該綜合排序原始數據狀態，需求，穩定性，系統資源等諸多因素來確定使用哪種排序方式，也可一將幾種排序組合使用以提高性能，比如小編就發現在快速排序中，當每個部分數據數量小于8時，對每個部分用插入排序就比一直使用快速排序更快。小編在找到一個動圖，十分生動形象的表現了不同算法的速度上的差異。

本章js源碼可以 點此去下載

排序算法就寫這么多，有什么不足還請指點。