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

寫在前面

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

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

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

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

//冒泡排序
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]];
    }
  }
}

選擇排序也很簡單。它每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。下面是完整的選擇排序過程：

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

//選擇排序
 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]];
  }
}

這個(gè)要略微復(fù)雜一點(diǎn)了。它的思路就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，依然保持有序。實(shí)現(xiàn)過程把數(shù)組看作2部分，一部分是有序的，一部分是無序的，每次大循環(huán)將無序數(shù)組的第一個(gè)元素插入到有序的數(shù)組中。

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

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

//直接插入排序
insertionSort = function (arr){
  var len = arr.length;
  var temp;//temp每次要執(zhí)行插入的值
  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;//找到的插入點(diǎn)索引
        break;
      }
    }
    if (i != index){
      for (var j = i; j > index; j--)//插入該值
        [arr[j - 1], arr[j]] = [arr[j],arr[j - 1]];
    }
    arr[index] = temp;
  }
}

這個(gè)想必大家都耳熟能詳，20世紀(jì)十大經(jīng)典算法之一。主要原因還是它極大的推動了信息技術(shù)的發(fā)展，可惜它不是穩(wěn)定算法。
這個(gè)算法比較就比較難理解了，它通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的任一數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。這里面包含的分治的思想。
下面一個(gè)圖表現(xiàn)了函數(shù)的一次執(zhí)行過程：

而這個(gè)圖表現(xiàn)了整個(gè)排序過程：

插入排序時(shí)間復(fù)雜度為$O(nlogn)$，空間復(fù)雜度為$O(logn)$，屬于 不穩(wěn)定 排序。

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

  function qSort(left, right){
    if (left >= right)//兩個(gè)數(shù)相遇則結(jié)束該輪排序
      return;
    var key = arr[left];//取最左邊的元素作為標(biāo)識數(shù)
    var i = left;
    var j = right;
    while (i != j){//兩個(gè)數(shù)相遇則結(jié)束該輪排序
      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);//對標(biāo)識數(shù)前面的數(shù)繼續(xù)該方法排序
    qSort(j + 1, right);//對標(biāo)識數(shù)后面的數(shù)繼續(xù)該方法排序
  }
}

這里補(bǔ)充一下：快速排序由于其實(shí)軸的選擇不同，分為前軸、中軸、后軸快速排序，上面的例子是前軸快速排序，下文比較算法的時(shí)候也才用上述代碼。不過，這里補(bǔ)充另外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); // 向右找大于軸的數(shù)
        while (arr[--j] > key); // 向左找小于軸的數(shù)
        if (i >= j)//兩索引相同結(jié)束排序
          break;
        [arr[i], arr[j]] = [arr[j],arr[i]];//交換找到的數(shù)
      }
      qSort(left, i - 1); // 繼續(xù)這樣對軸前面的排序
      qSort(j + 1, right); // 繼續(xù)這樣對軸后面的排序
    }
  }
}

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

  function qSort(left, right){
    if (left >= right)//兩索引相同結(jié)束排序
      return;
    var key = arr[right];
    var i = left - 1;//s是最右邊的軸
    for (var j = left; j < right; j++){ //將數(shù)據(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);//繼續(xù)這樣對軸前面的排序
    qSort(i, right);//繼續(xù)這樣對軸后面的排序
  }
}

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

插入排序時(shí)間復(fù)雜度為$O(nlogn)$，空間復(fù)雜度為$O(n)$，屬于 穩(wěn)定 排序。

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

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

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

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

//希爾排序
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++){//遍歷起點(diǎn)后移，保證每個(gè)數(shù)在該步長下參與且只參與1此排序
      temp = arr[i];
      for (j = i; j >= index && arr[j - index] > temp;){//等步長數(shù)列執(zhí)行插入排序
        arr[j] = arr[j - index];
        j -= index;
        arr[j] = temp;
      }
    }
    index = Math.floor(index / 2);//步長減半
  }
}

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

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

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

  function heapAdjust(arr, i, len){//二叉堆調(diào)整函數(shù)，負(fù)責(zé)將堆調(diào)整成大根堆（因?yàn)槭窃鲂蚺帕校?    var child;//根孩子的索引
    var temp;
    //以等倍數(shù)間隔，調(diào)整堆為大根堆
    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;
    }
  }
}

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

下圖是整個(gè)排序過程示意圖：

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

//基數(shù)排序(桶排序)
radixSort = function(arr){
  var len = arr.length;
  var bullet= [];
  var k=1, temp;//k是處理數(shù)字的權(quán)重，k=1表示處理個(gè)位數(shù)，k=10表示處理十位數(shù)，以此類推
  for (var i = 0; i < 10; i++)//為每個(gè)桶分配內(nèi)存空間
    bullet[i] = [];
  while (true){
    var num = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ];//num用來統(tǒng)計(jì)0~9每個(gè)桶里面現(xiàn)有數(shù)字個(gè)數(shù)
    for (var i = 0; i < len; i++){//統(tǒng)計(jì)分配每個(gè)數(shù)字到桶里面，并統(tǒng)計(jì)每個(gè)桶數(shù)字個(gè)數(shù)
      temp = Math.floor(arr[i] / k) % 10;
      bullet[temp][num[temp]++] = arr[i];
    }
    if (num[0] == len) break;//當(dāng)全部數(shù)字都在編號為0的桶中，排序結(jié)束
    //將桶里的數(shù)依次放回a數(shù)組中
    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倍，從右至左處理下一位數(shù)字
  }
  return arr;
}