在計(jì)算機(jī)科學(xué)所使用的排序算法通常被分類為：

• 計(jì)算的 時(shí)間復(fù)雜度（最差、平均、和最好性能），依據(jù)列表（list）的大小(n)。一般而言，好的性能是O(n log n)，且壞的性能是O(n^2)。對于一個(gè)排序理想的性能是O(n)。僅使用一個(gè)抽象關(guān)鍵比較運(yùn)算的排序算法總平均上總是至少需要O(n log n)。
• 存儲(chǔ)器使用量（以及其他電腦資源的使用）
  穩(wěn)定性：穩(wěn)定排序算法會(huì)讓原本有相等鍵值的紀(jì)錄維持相對次序。也就是如果一個(gè)排序算法是穩(wěn)定的，當(dāng)有兩個(gè)相等鍵值的紀(jì)錄R和S，且在原本的列表中R出現(xiàn)在S之前，在排序過的列表中R也將會(huì)是在S之前。
• 依據(jù)排序的方法：插入、交換、選擇、合并等等。

依據(jù)排序的方法分類的三種排序算法:

冒泡排序

冒泡排序?qū)σ粋€(gè)需要進(jìn)行排序的數(shù)組進(jìn)行以下操作:

1. 比較第一項(xiàng)和第二項(xiàng);
2. 如果第一項(xiàng)應(yīng)該排在第二項(xiàng)之后, 那么兩者交換順序;
3. 比較第二項(xiàng)和第三項(xiàng);
4. 如果第二項(xiàng)應(yīng)該排在第三項(xiàng)之后, 那么兩者交換順序;
5. 以此類推直到完成排序;

冒泡排序.gif

將數(shù)組[3, 2, 4, 5, 1]以從小到大的順序進(jìn)行排序:

1. 3應(yīng)該在2之后, 因此交換, 得到[2, 3, 4, 5, 1];
2. 3, 4順序不變, 4, 5也不變, 交換5, 1得到[2, 3, 4, 1, 5];
3. 第一次遍歷結(jié)束, 數(shù)組中最后一項(xiàng)處于正確位置不會(huì)再有變化, 因此下一次遍歷可以排除最后一項(xiàng);
4. 開始第二次遍歷, 最后結(jié)果為[2, 3, 1, 4, 5], 排除后兩項(xiàng)進(jìn)行下一次遍歷;
5. 第三次遍歷結(jié)果為[2, 1, 3, 4, 5];
6. 最后得到[1, 2, 3, 4, 5], 排序結(jié)束;

代碼實(shí)現(xiàn):

function swap(items, firstIndex, secondIndex){
      var temp = items[firstIndex];
      items[firstIndex] = items[secondIndex];
      items[secondIndex] = temp;
};
function bubbleSort(items){
      var len = items.length, i, j, stop;
      for (i = 0; i < len; i++){
        for (j = 0, stop = len-i; j < stop; j++){
          if (items[j] > items[j+1]){
            swap(items, j, j+1);
          }
        }
      }
      return items;
}

外層的循環(huán)決定需要進(jìn)行多少次遍歷, 內(nèi)層的循環(huán)負(fù)責(zé)數(shù)組內(nèi)各項(xiàng)的比較, 還通過外層循環(huán)的次數(shù)和數(shù)組長度決定何時(shí)停止比較.

冒泡排序極其低效, 因?yàn)樘幚頂?shù)據(jù)的步驟太多, 對于數(shù)組中的每n項(xiàng), 都需要n^2次操作來實(shí)現(xiàn)該算法(實(shí)際比n^2略小, 但可以忽略, 具體原因見??), 即時(shí)間復(fù)雜度為O(n^2).

對于含有n個(gè)元素的數(shù)組, 需要進(jìn)行(n-1)+(n-2)+...+1次操作, 而(n-1)+(n-2)+...+1 = n(n-1)/2 = n^2/2 - n/2, 如果n趨于無限大, 那么n/2的大小對于整個(gè)算式的結(jié)果影響可以忽略, 因此最終的時(shí)間復(fù)雜度用O(n^2)表示

選擇排序

選擇排序?qū)σ粋€(gè)需要進(jìn)行排序的數(shù)組進(jìn)行以下操作:

1.假定數(shù)組中的第一項(xiàng)為最小值(min);

2. 比較第一項(xiàng)和第二項(xiàng)的值;
3. 若第二項(xiàng)比第一項(xiàng)小, 則假定第二項(xiàng)為最小值;
4. 以此類推直到排序完成.

選擇排序.gif

將數(shù)組["b", "a", "d", "c", "e"]以字母a-z的順序進(jìn)行排序:

1. 假定數(shù)組中第一項(xiàng)"b"(index0)為min;
2. 比較第二項(xiàng)"a"與第一項(xiàng)"b", 因"a"應(yīng)在"b"之前的順序, 故"a"(index1)為min;
3. 然后將min與后面幾項(xiàng)比較, 由于"a"就是最小值, 因此min確定在index1的位置;
4. 第一次遍歷結(jié)束后, 將假定的min(index0), 與真實(shí)的min(index1)進(jìn)行比較, 真實(shí)的min應(yīng)該在index0的位置, 因此將兩者交換, 第一次遍歷交換之后的結(jié)果為["a", "b", "d", "c", "e"];
5. 然后開始第二次遍歷, 遍歷從第二項(xiàng)(index1的位置)開始, 這次假定第二項(xiàng)為最小值, 將第二項(xiàng)與之后幾項(xiàng)逐個(gè)比較, 因?yàn)?b"就在應(yīng)該存在的位置, 所以不需要進(jìn)行交換, 這次遍歷之后的結(jié)果為["a", "b", "d", "c", "e"];
   6.之后開始第三次遍歷, "c"應(yīng)為這次遍歷的最小值, 交換index2("d"),index3("c")位置, 最后結(jié)果為["a", "b", "c", "d", "e"];
6. 最后一次遍歷, 所有元素在應(yīng)有位置, 不需要進(jìn)行交換.

代碼實(shí)現(xiàn):

function swap(items, firstIndex, secondIndex){
  var temp = items[firstIndex];
  items[firstIndex] = items[secondIndex];
  items[secondIndex] = temp;
};

function selectionSort(){
  let items = [...document.querySelectorAll('.num-queue span')].map(num => +num.textContent);
  let len = items.length, min;

  for (i = 0; i < len; i++){
    min = i;
    for(j = i + 1; j < len; j++){
      if(items[j] < items[min]){
        min = j;
      }
    }
    if(i != min){
      swap(items, i, min);
    }
  }
  return items;
};

外層循環(huán)決定每次遍歷的初始位置, 從數(shù)組的第一項(xiàng)開始直到最后一項(xiàng). 內(nèi)層循環(huán)決定哪一項(xiàng)元素被比較.

選擇排序的時(shí)間復(fù)雜度為O(n^2).

插入排序

與上述兩種排序算法不同, 插入排序是穩(wěn)定排序算法(stable sort algorithm), 穩(wěn)定排序算法指不改變列表中相同元素的位置, 冒泡排序和選擇排序不是穩(wěn)定排序算法, 因?yàn)榕判蜻^程中有可能會(huì)改變相同元素位置. 對簡單的值(數(shù)字或字符串)排序時(shí), 相同元素位置改變與否影響不是很大. 而當(dāng)列表中的元素是對象, 根據(jù)對象的某個(gè)屬性對列表進(jìn)行排序時(shí), 使用穩(wěn)定排序算法就很有必要了.

一旦算法包含交換(swap)這個(gè)步驟, 就不可能是穩(wěn)定的排序算法. 列表內(nèi)元素不斷交換, 無法保證先前的元素排列為止一直保持原樣. 而插入排序的實(shí)現(xiàn)過程不包含交換, 而是提取某個(gè)元素將其插入數(shù)組中正確位置.

插入排序的實(shí)現(xiàn)是將一個(gè)數(shù)組分為兩個(gè)部分, 一部分排序完成, 一部分未進(jìn)行排序. 初始狀態(tài)下整個(gè)數(shù)組屬于未排序部分, 排序完成部分為空. 然后進(jìn)行排序, 數(shù)組內(nèi)的第一項(xiàng)被加入排序完成部分, 由于只有一項(xiàng), 自然屬于排序完成狀態(tài). 然后對未完成排序的余下部分的元素進(jìn)行如下操作:

1. 如果這一項(xiàng)的值應(yīng)該在排序完成部分最后一項(xiàng)元素之后, 保留這一項(xiàng)在原有位置開始下一步;
2. 如果這一項(xiàng)的值應(yīng)該排在排序完成部分最后一項(xiàng)元素之前, 將這一項(xiàng)從未完成部分暫時(shí)移開, 將已完成部分的最后一項(xiàng)元素移后一個(gè)位置;
3. 被暫時(shí)移開的元素與已完成部分倒數(shù)第二項(xiàng)元素進(jìn)行比較;
4. 如果被移除元素的值在最后一項(xiàng)與倒數(shù)第二項(xiàng)的值之間, 那么將其插入兩者之間的位置, 否則繼續(xù)與前面的元素比較, 將暫移出的元素放置已完成部分合適位置. 以此類推直到所有元素都被移至排序完成部分.

插入排序.gif

現(xiàn)在需要將數(shù)組var items = [5, 2, 6, 1, 3, 9];進(jìn)行插入排序:

1. 5屬于已完成部分, 余下元素為未完成部分. 接下來提取出2, 因?yàn)?比2大, 于是5被移至靠右一個(gè)位置, 覆蓋2, 占用2原本存在的位置. 這樣本來存放5的位置(已完成部分的首個(gè)位置)就被空出, 而2在比5小, 因此將2置于這個(gè)位置, 此時(shí)結(jié)果為[2, 5, 6, 1, 3, 9];
2. 接下來提取出6, 因?yàn)?比5大, 所以不操作提取出1, 1與已完成部分各個(gè)元素(2, 5, 6)進(jìn)行比較, 應(yīng)該在2之前, 因此2, 5, 6各向右移一位, 1置于已完成部分首位, 此時(shí)結(jié)果為[1, 2, 5, 6, 3, 9];
3. 對余下未完成元素進(jìn)行類似操作, 最后得出結(jié)果[1, 2, 3, 5, 6, 9];

代碼實(shí)現(xiàn):

function insertionSort(items) {
  let len = items.length, value, i, j;
  for (i = 0; i < len; i++) {
    value = items[i];
    for (j = i-1; j > -1 && items[j] > value; j--) {
      items[j+1] = items[j];
    }
    items[j+1] = value;
  }
  return items;
};

外層循環(huán)的遍歷順序是從數(shù)組的第一位到最后一位, 內(nèi)層循環(huán)的遍歷則是從后往前, 內(nèi)層循環(huán)同時(shí)負(fù)責(zé)元素的移位.

插入排序的時(shí)間復(fù)雜度為O(n^2)

以上三種排序算法都十分低效, 因此實(shí)際應(yīng)用中不要使用這三種算法, 遇到需要排序的問題, 應(yīng)該首先使用JavaScript內(nèi)置的方法Array.prototype.sort();

參考:

2015-CS50-week-算法
排序算法-JavaScript描述
三種基礎(chǔ)的排序算法