摘要：也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因於年提出而得名。

因為比較隨心所欲,所以我不按難度分享算法,所以你們會看到有時候順序有變化,因為我發表的時候會按照難度修改下位置,盡量讓你們看的時候能從簡單開始,
以后每次更新都加個更新時間好了,讓你們知道我進度.新增計時函數直觀對比效率
并且因為資料比較雜,很多都是我個人理解說法,如果有發現問題歡迎批評,造福更多人,誤人誤己就不好了
思路是一樣的,寫法不是唯一,所以不用死記代碼的
折騰了這麼久時間總算把十個算法都總結完了,但是還不熟練,一些思想還沒吃透,覺得有些寫法應該還能更好,以后肯定還會找時間優化一下的,但是可能不是最近,我有點迫不及待得想去總結下其他方面的知識點,例如請求方面的東西,好多短板需要學習

PS:
2018/12/18 全新排版,代碼優化

PS:經博友點明之后,為了提高嚴謹性,我把測試方法都新增類型判斷和過濾,生成函數新增能否重復取值的參數.
首先介紹一些生成測試例子的方法給大家，方便效率不用手動添加。

為了提高測試直觀性,我們采用固定亂序數組使用.

//是否數組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當前入參非數組類型!");
  return bol;
}

//計時小玩意
function useTime(name, fn) {
  console.time(name + "耗時");
  console.log("排序前: ", ary);
  console.log("排序后: ", fn(ary));
  console.timeEnd(name + "耗時");
}


/**
 * @param {*} num 生成長度
 * @param {*} isRepetition 能否重復取值 默認不能
 * @param {*} min 最小范圍 默認0
 * @param {*} max 最大范圍 默認1000
 * @returns
 */
function randomAry(num, isRepetition, min, max) {
  var ary = [],
    i = 0,
    min = min || 0,
    max = max || 1000;

  if (!isRepetition && num > max - min) {
    throw ("當前取值范圍超過最小值最大值之間的范圍并且不能重復取值!");
  }

  for (; i < num; i++) {
    const random = Math.ceil(Math.random() * (max - min) + min);

    if (!isRepetition && ary.indexOf(random) > -1) {
      --i;
      continue;
    }
    ary.push(random);
  }

  console.log("排序前: ", ary)
  return ary;
}

(友情鏈接,什麼叫log,應該不少人跟我一樣忘了什麼叫log吧!(～￣▽￣)～)

第一個循環,從零開始,假設它是最小值( i )

第二個循環,從最小值+1( j )位置開始,后續所有數據逐個跟最小值比較,發現有更小值就替換掉

第二層循環遍歷完后如果最小值已經改變了,就跟原最小值(也就是第一層循環的 i )互換位置

繼續重復步驟直到完成

要實現上述規則需要用雙層for循環

① 最最最簡單粗暴,不佔用額外的內存空間

① 最最最噁心,計算過程消耗性能巨大,數組越長遍歷次數越多,并且效率極度不穩定,不管數據亂序程度,它都必定會遍歷所有數據

//選擇排序
function selectIn(ary) {
  //類型檢查
  if (!isArray(ary)) return false;
  if (ary.length <= 1) return ary;

  var len = ary.length,
    i = 0,
    j,
    min; //最小值

  //互換位置
  var swap = function(a, b) {
    ary[a] = [ary[b], (ary[b] = ary[a])][0];
  };

  //拆分
  var select = (function() {
    for (; i < len; i++) {
      //假設當前是最小值
      min = i;

      for (j = i + 1; j < len; j++) {
        //找到最小值
        if (ary[min] > ary[j]) min = j;
      }

      //符合條件互換位置
      if (i != min) swap(i, min);
    }

    return ary;
  })();

  //返回新數組
  return select;
}

useTime("選擇排序算法", selectIn);

//是否數組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當前入參非數組類型!");
  return bol;
}

//計時小玩意
function useTime(name, fn) {
  var ary = [
    616,
    380,
    751,
    317,
    561,
    722,
    246,
    907,
    970,
    614,
    446,
    917,
    403,
    663,
    312
  ];
  console.time(name + "耗時");
  console.log("排序前: ", ary);
  console.log("排序后: ", fn(ary));
  console.timeEnd(name + "耗時");
}

運行結果:

排序前:  [ 616, 380, 751, 317, 561, 722, 246, 907, 970, 614, 446, 917, 403, 663, 312 ]
排序后:  [ 246, 312, 317, 380, 403, 446, 561, 614, 616, 663, 722, 751, 907, 917, 970 ]
選擇排序算法耗時: 12.634ms

插入算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但將最后一個元素除外(讓數組多一個空間才有插入的位置)，而第二部分就只包含這一個元素(即待插入元素)。在第一部分排序完成后，再將這個最后元素插入到已排好序的第一部分中。

第一個循環,從 1 開始,保存當前值作參考數

第二個循環,從 j=i-1 位置開始,滿足 j>=0 并且 j 位置值大於參考值時數值位置后移

不滿足條件中斷循環,參考值賦值當前 j+1 位置

要實現上述規則需要用到for和while循環

① 適用於少量數據的排序，最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需(n-1)次即可

① 計算過程消耗性能巨大,越往后遍歷次數越多,跟數據亂序程度有關，最壞情況就是，序列是降序排列，那麼此時需要進行的比較共有 n(n-1)/2 次。插入排序的賦值操作是比較操作的次數加上 (n-1)次

//插入排序
function insertIn(ary) {
  //類型檢查
  if (!isArray(ary)) return false;
  if (ary.length <= 1) return ary;

  //雙層遍歷,i要從1開始
  var len = ary.length,
    i = 1,
    j,
    tmp, //臨時變量
    copy = ary.slice(0); // 設置數組副本

  for (; i < len; i++) {
    tmp = copy[i];
    j = i - 1;

    //找到相應位置并插入
    while (j >= 0 && copy[j] > tmp) {
      //這裡i是固定的,j是遞減的,所以用j+1
      copy[j + 1] = copy[j];
      j--;
    }

    //賦值中斷位置，有種情況是順序沒發生變化相當於重新賦值自身，所以是穩定算法
    copy[j + 1] = tmp;
  }
  return copy;
}

useTime("插入排序", insertIn);

//是否數組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當前入參非數組類型!");
  return bol;
}

//計時小玩意
function useTime(name, fn) {
  var ary = [
    616,
    380,
    751,
    317,
    561,
    722,
    246,
    907,
    970,
    614,
    446,
    917,
    403,
    663,
    312
  ];
  console.time(name + "耗時");
  console.log("排序前: ", ary);
  console.log("排序后: ", fn(ary));
  console.timeEnd(name + "耗時");
}

運行結果:

排序前:  [ 616, 380, 751, 317, 561, 722, 246, 907, 970, 614, 446, 917, 403, 663, 312 ]
排序后:  [ 246, 312, 317, 380, 403, 446, 561, 614, 616, 663, 722, 751, 907, 917, 970 ]
插入排序耗時: 10.002ms

遍歷對比相鄰兩個數據，小的排在前面，如果前面的數據比后面的大就交換位置，這個算法的名字由來是因為越大的元素會經由交換慢慢“浮”到數列的頂端.

外循環,從數組長度開始遞減

內循環,從 i=0 開始不超過數組長度開始遞增，比較 i 和 i+1 位置數字排序

重復一二步驟

① 最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需(n-1)次即可。

① 是比較次數多，效率較低，每次只能移動相鄰兩個數據。最壞情況就是，序列是降序排列，那麼此時需要進行的比較共有 n(n-1)/2 次。

//冒泡排序
function bubbleSort(ary) {
  //類型檢查
  if (!isArray(ary)) return false;
  if (ary.length <= 1) return ary;

  var len = ary.length,
    i;

  //互換位置
  var swap = function(a, b) {
    ary[a] = [ary[b], (ary[b] = ary[a])][0];
  };

  while (len > 0) {
    for (i = 0; i < len - 1; i++) {
      if (ary[i] > ary[i + 1]) swap(i, i + 1);
    }
    len--;
  }
  return ary;
}

useTime("冒泡排序算法", bubbleSort);

//是否數組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當前入參非數組類型!");
  return bol;
}

//計時小玩意
function useTime(name, fn) {
  var ary = [
    616,
    380,
    751,
    317,
    561,
    722,
    246,
    907,
    970,
    614,
    446,
    917,
    403,
    663,
    312
  ];
  console.time(name + "耗時");
  console.log("排序前: ", ary);
  console.log("排序后: ", fn(ary));
  console.timeEnd(name + "耗時");
}

運行結果:

排序前:  [ 616, 380, 751, 317, 561, 722, 246, 907, 970, 614, 446, 917, 403, 663, 312 ]
排序后:  [ 246, 312, 317, 380, 403, 446, 561, 614, 616, 663, 722, 751, 907, 917, 970 ]
冒泡排序算法耗時: 12.200ms

通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

聲明兩個新數組，原數組里選擇一個中間元素作為參考數

其他元素里比參考數小的和比參考數大的分別放進兩個新數組裡并且重新組合成一個數組

然后不斷重復一二步驟直到完成為止

要實現上述規則需要用到 for 循環和遞歸.

① 是冒泡排序的改進版，使用得最廣泛，速度也較快。

① 在初始序列有序或者基本有序時，其時間復雜度降為 O(n*n) ,數據越多遞歸層級越深占用堆棧空間越大。

//快速排序
function quickSort(ary) {
  //類型檢查
  if (!isArray(ary)) return false;
  if (ary.length <= 1) return ary;

  var middleIndex = Math.ceil(ary.length / 2), //尋找中間位置
    middle = ary.splice(middleIndex, 1), //提取中間值
    left = [],
    right = [],
    i = 0,
    len = ary.length; //上面有個刪除步驟，不能放前面

  for (; i < len; i++) {
    (ary[i] < middle ? left : right).push(ary[i]);
  }

  //遞歸執行
  return quickSort(left).concat(middle, quickSort(right));
}

useTime("快速排序算法", quickSort);

//是否數組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當前入參非數組類型!");
  return bol;
}

//計時小玩意
function useTime(name, fn) {
  var ary = [
    616,
    380,
    751,
    317,
    561,
    722,
    246,
    907,
    970,
    614,
    446,
    917,
    403,
    663,
    312
  ];
  console.time(name + "耗時");
  console.log("排序前: ", ary);
  console.log("排序后: ", fn(ary));
  console.timeEnd(name + "耗時");
}

運行結果:

排序前:  [ 616, 380, 751, 317, 561, 722, 246, 907, 970, 614, 446, 917, 403, 663, 312 ]
排序后:  [ 246, 312, 317, 380, 403, 446, 561, 614, 616, 663, 722, 751, 907, 917, 970 ]
快速排序算法耗時: 13.195ms

有個需要注意的地方是過濾數組部分必須放在聲明變量，再具體點就是提取參考數之前,放在后面如果數組長度為 2,刪除參考數之后會因為符合條件被直接返回剩餘的數組,可以看看實例.(如果一次看不到效果,加加減減空格再查看效果就有變化了)

//快速排序
function quickSort(ary) {
  //類型檢查
  if (!isArray(ary)) return false;
  if (ary.length <= 1) return ary;

  var middleIndex = Math.ceil(ary.length / 2),
    middle = ary.splice(middleIndex, 1),
    left = [],
    right = [],
    i = 0,
    len = ary.length;

  //過濾部分數組
  if (len <= 1) return ary;

  for (; i < len; i++) {
    (ary[i] < middle ? left : right).push(ary[i]);
  }

  return quickSort(left).concat(middle, quickSort(right));
}

useTime("快速排序算法", quickSort);

//是否數組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當前入參非數組類型!");
  return bol;
}

//計時小玩意
function useTime(name, fn) {
  var ary = [
    616,
    380,
    751,
    317,
    561,
    722,
    246,
    907,
    970,
    614,
    446,
    917,
    403,
    663,
    312
  ];
  console.time(name + "耗時");
  console.log("排序前: ", ary);
  console.log("排序后: ", fn(ary));
  console.timeEnd(name + "耗時");
}

第一步拆分,數據不斷從中間拆分,直到無法繼續為止(從上至下)
[12,56,23,2] => [12,56] + [23,2] => [12] + [56] + [23] + [2]

第二步比較合并,每兩組數據排序合并,直到合并到只剩一組數據(從下至上)
[12] + [56] + [23] + [2] => [12,56] + [2,23] => [2,12,23,56]

要實現上述規則需要用到while循環和嵌套遞歸。

① 速度僅次於快速排序,例如如果排序項的數目是 1000,用歸併排序需要 3 秒的時間,那麼用插入排序則需要大概 16.7 分鐘(差距隨排序項增大而增加)。

① 比較佔用內存，復雜度稍微高一點點

//歸并排序
function excreteAndMerge(ary) {
  //類型檢查
  if (!isArray(ary)) return false;

  //拆分
  var excrete = function(_ary) {
    //不加中斷會一直運行直到堆棧溢出,關鍵!!
    if (_ary.length <= 1) return _ary;

    //拆分兩個數組
    var middleIndex = Math.ceil(_ary.length / 2),
      left = _ary.slice(0, middleIndex),
      right = _ary.slice(middleIndex);

    //合并數組
    return merge(excrete(left), excrete(right));
  };

  //排序併合并
  var merge = function(left, right) {
    var _ary = [];

    //這一步相當關鍵!!!
    while (left.length > 0 && right.length > 0) {
      //分別比較數組首位并把較小的數值推入新數組
      _ary.push((left[0] < right[0] ? left : right).shift());
    }
    //將比較完后剩下的數組項組合起來
    return _ary.concat(left, right);
  };

  return excrete(ary);
}

useTime("歸并排序算法", excreteAndMerge);

//是否數組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當前入參非數組類型!");
  return bol;
}

//計時小玩意
function useTime(name, fn) {
  var ary = [
    616,
    380,
    751,
    317,
    561,
    722,
    246,
    907,
    970,
    614,
    446,
    917,
    403,
    663,
    312
  ];
  console.time(name + "耗時");
  console.log("排序前: ", ary);
  console.log("排序后: ", fn(ary));
  console.timeEnd(name + "耗時");
}

運行結果:

排序前:  [ 616, 380, 751, 317, 561, 722, 246, 907, 970, 614, 446, 917, 403, 663, 312 ]
排序后:  [ 246, 312, 317, 380, 403, 446, 561, 614, 616, 663, 722, 751, 907, 917, 970 ]
歸并排序算法耗時: 13.403ms

基礎：希爾排序是基於插入排序的以下兩點性質而提出改進方法的：

插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率。

但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位。
希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因 DL．Shell 於 1959 年提出而得名。

第一步拆分,固定或動態定義一個間隔序列,最關鍵是不管序列多大,最終必須要逐個遍歷一遍收尾,(我在這步跪了一段時間才發現);

一般的初次取序列的一半為增量，以后每次減半，直到增量為 1。

例如長度 100, 跨度是 2, 初始間隔序列 = 長度/跨度, 遞減量=自身/跨度即 50,25,22.....1

第二步按間隔序列排序直到逐個排序為止

要實現上述規則需要用到多個循環和插入算法.

本質上講，希爾排序算法是直接插入排序算法的一種改進，減少了其復製的次數，速度要快很多,原因是
① 當文件初態基本有序時直接插入排序所需的比較和移動次數均較少。
② 當 n 值較小時，n 和 n2 的差別也較小，即直接插入排序的最好時間復雜度 O(n)和最壞時間復雜度 O(n2)差別不大。
③ 在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組內直接插入較快，后來增量逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由於已經按增量距離排過序，使文件較接近於有序狀態，所以新的一趟排序過程也較快。

對規模非常大的數據排序不是最優選擇
示例圖如下,假設原數組[663, 949, 916, 393, 470, 26, 649, 256, 901, 705, 519, 803, 334, 861, 83, 70, 230, 588, 9, 346],跨度為 3.
① 第一次循環增量:20/3≈7,即比較位置相差 7

第二次循環增量:7/3≈3,即比較位置相差 3

第三次循環增量:3/3=1,最終逐個遍歷一遍收尾

可以好好看看思維導圖,因為單純思考好容易迷糊的.
先來看看百度百科的寫法

var arr = [616, 380, 751, 317, 561, 722, 246, 907, 970, 614, 446, 917, 403, 663, 312],
  len = arr.length;
for (
  var fraction = Math.floor(len / 2); fraction > 0; fraction = Math.floor(fraction / 2)
) {
  console.log("fraction : " + fraction);
  for (var i = fraction; i < len; i++) {
    for (
      var j = i - fraction; j >= 0 && arr[j] > arr[fraction + j]; j -= fraction
    ) {
      var temp = arr[j];
      arr[j] = arr[fraction + j];
      arr[fraction + j] = temp;
    }
  }
}
console.log(arr);

fraction : 7
fraction : 3
fraction : 1
[ 246, 312, 317, 380, 403, 446, 561, 614, 616, 663, 722, 751, 907, 917, 970 ]

乍看之下好像挺好理解而且又簡單沒毛病,但有個小問題,實際上這是一個只能固定增量的代碼,如果你把間隔序列換成其他,也就是 Math.floor(len / 4)這樣子,有可能排序就完蛋了.如下:

var arr = [616, 380, 751, 317, 561, 722, 246, 907, 970, 614, 446, 917, 403, 663, 312],
  len = arr.length;
for (
  var fraction = Math.floor(len / 4); fraction > 0; fraction = Math.floor(fraction / 4)
) {
  console.log("fraction : " + fraction);
  for (var i = fraction; i < len; i++) {
    for (
      var j = i - fraction; j >= 0 && arr[j] > arr[fraction + j]; j -= fraction
    ) {
      var temp = arr[j];
      arr[j] = arr[fraction + j];
      arr[fraction + j] = temp;
    }
  }
}
console.log(arr);

fraction : 3
[ 246, 380, 312, 317, 446, 722, 403, 561, 751, 614, 663, 917, 616, 907, 970 ]

幸好我好奇心還行動手實踐一下,不然就栽在這裡以為懂了.關鍵就是上面說的不管序列多大,最終必須要逐個遍歷一遍收尾

我繼續挖掘下網上的代碼,另一種基本代碼都是這麼寫的

var arr = [616, 380, 751, 317, 561, 722, 246, 907, 970, 614, 446, 917, 403, 663, 312],
  len = arr.length,
  temp,
  fraction = 1;

while (fraction < len / 5) {
  //動態定義間隔序列
  fraction = fraction * 5 + 1;
}
for (fraction; fraction > 0; fraction = Math.floor(fraction / 5)) {
  console.log("fraction: " + fraction);
  for (var i = fraction; i < len; i++) {
    temp = arr[i];
    for (var j = i - fraction; j >= 0 && arr[j] > temp; j -= fraction) {
      arr[j + fraction] = arr[j];
    }
    arr[j + fraction] = temp;
  }
}

console.log(arr);

fraction: 6
fraction: 1
[ 246, 312, 317, 380, 403, 446, 561, 614, 616, 663, 722, 751, 907, 917, 970 ]

中間動態定義間隔序列的代碼就是解決上面說的問題
但我還不滿意,可擴展度還不夠高,下面是我按自己理解寫的一個希爾算法,只用三個循環加個中斷條件.自測沒發現什麼問題,如果有錯誤的地方麻煩指出來吧.

//希爾排序
function shellSort(ary, limit) {
  //類型檢查
  if (!isArray(ary)) return false;
  if (ary.length <= 1) return ary;

  var len = ary.length,
    limit = limit || 3, //跨度
    gap = Math.ceil(len / limit), //動態間隔序列
    i,
    j;

  //互換位置
  var swap = function (a, b) {
    ary[a] = [ary[b], (ary[b] = ary[a])][0];
  };

  //間隔序列循環遞減
  for (; gap > 0; gap = Math.ceil(gap / limit)) {
    for (i = gap; i < len; i++) {
      //間隔排序
      for (j = i - gap; j >= 0 && ary[j] > ary[j + gap]; j -= gap) {
        swap(j, j + gap);
      }
    }
    //另一個關鍵地方,不加中斷條件引起死循環導致內存溢出
    if (gap == 1) break;
  }

  return ary;
}

useTime("希爾排序算法", shellSort);

//是否數組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當前入參非數組類型!");
  return bol;
}

//計時小玩意
function useTime(name, fn) {
  var ary = [
    616,
    380,
    751,
    317,
    561,
    722,
    246,
    907,
    970,
    614,
    446,
    917,
    403,
    663,
    312
  ];
  console.time(name + "耗時");
  console.log("排序前: ", ary);
  console.log("排序后: ", fn(ary));
  console.timeEnd(name + "耗時");
}

排序前:  [ 616, 380, 751, 317, 561, 722, 246, 907, 970, 614, 446, 917, 403, 663, 312 ]
排序后:  [ 246, 312, 317, 380, 403, 446, 561, 614, 616, 663, 722, 751, 907, 917, 970 ]
希爾排序算法耗時: 8.988ms

基礎：計數排序是一個非基於比較的排序算法,核心在於將輸入的數據值轉化為鍵存儲在額外開闢的數組空間中。作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。計數排序對輸入的數據有附加的限制條件：

輸入的線性表的元素屬於有限偏序集 S；

設輸入的線性表的長度為 n，|S|=k(表示集合 S 中元素的總數目為 k)，則 k=O(n)。
在這兩個條件下，計數排序的復雜性為 O(n)。

統計數組統計每個值出現次數和找出其中最大最小值

統計數組從 min 位置開始對所有計數開始累加(當前項和前一項相加)直到最大值位置為止

根據統計數組的值大小可以知道排列順序，然后反向填充目標數組

① 在對一定范圍內的整數排序時，它的復雜度為 Ο(n+k)(其中 k 是整數的范圍)，快於任何比較排序算法。

① 犧牲空間換取時間,當 O(k)>O(nlog(n))的時候其效率反而不如基於比較的排序(基於比較的排序的時間復雜度在理論上的下限是 O(nlog(n)), 如歸併排序，堆排序)
詳細分析如下,假設原數組[27, 24, 23, 27, 21]
找到最小值21,最大值27
然后統計數組統計每個值出現次數后 Count [21: 1, 23: 1, 24: 1, 27: 2]
從最小值到最大值之間每個位置都填滿后 Count [21: 1, 22: 1, 23: 2, 24: 3, 25: 3, 26: 3, 27: 5]
反向填充目標數組: [21, 23, 24, 27, 27]

② 不適用數值相差范圍太大的排序,例如[1, 2, 1000],因為統計數組會從0開始累加直到1000, 即中間太多冗余填充數據了.
(這裡只會打印出值,不會打印相對應位置,但這是整個算法的關鍵,所以建議拷貝到本地去運行.)

因為算法的特殊性我們換一組相差范圍比較小的亂序數組做測試.

//計數排序
function countingSort(ary) {
  //類型檢查
  if (!isArray(ary)) return false;
  if (ary.length <= 1) return ary;

  var len = ary.length,
    Result = [], //排序數組
    Count = [], //統計數組
    min = (max = ary[0]),
    i = 0,
    j,
    k;

  //在Count里統計數據，并且找出最大值最小值
  for (; i < len; i++) {
    //切記不能用一個變量保存Count[ary[i]]！！,詳情http://www.qdfuns.com/notes/40831/dd2b82537d74065b8a53b75e2eb85715.html
    Count[ary[i]]++ || (Count[ary[i]] = 1); //可能有重復數值
    min > ary[i] && (min = ary[i]);
    max < ary[i] && (max = ary[i]);
  }
  console.log("第一個循環后的Count: ", Count);

  //從最小值到最大值之間每個位置都填滿(這步相當關鍵)
  for (j = min; j < max; j++) {
    //讓當前項數值比前一項數值大,后面將根據這個數值確定順序位置
    Count[j + 1] = (Count[j + 1] || 0) + (Count[j] || 0);
  }
  console.log("第二個循環后的Count: ", Count);

  //算法精華，反向填充數組!!
  for (k = len - 1; k >= 0; k--) {
    console.log("位置: ", Count[ary[k]] - 1, "值: ", ary[k])
    //Result[位置] = ary值，-1是因為新數組該從0位置開始排序
    Result[Count[ary[k]] - 1] = ary[k];
    //減少Count數組中保存的計數，注釋掉的話當數組存在重復數值時會跳過后續重復數值排序
    Count[ary[k]]--;
  }
  return Result;
}

useTime("計數排序算法", countingSort);

//是否數組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當前入參非數組類型!");
  return bol;
}

//計時小玩意
function useTime(name, fn) {
  var ary = [18, 19, 5, 15, 20, 2, 17, 13, 8, 6, 7, 16, 3, 10, 4];
  console.time(name + "耗時");
  console.log("排序前: ", ary);
  console.log("排序后: ", fn(ary));
  console.timeEnd(name + "耗時");
}

排序前:  (15) [18, 19, 5, 15, 20, 2, 17, 13, 8, 6, 7, 16, 3, 10, 4]

第一個循環后的Count:  (21) [undefined, undefined, 1, 1, 1, 1, 1, 1, 1, undefined, 1, undefined, undefined, 1, undefined, 1, 1, 1, 1, 1, 1]

第二個循環后的Count:  (21) [undefined, undefined, 1, 2, 3, 4, 5, 6, 7, 7, 8, 8, 8, 9, 9, 10, 11, 12, 13, 14, 15]

位置:  2 值:  4
位置:  7 值:  10
位置:  1 值:  3
位置:  10 值:  16
位置:  5 值:  7
位置:  4 值:  6
位置:  6 值:  8
位置:  8 值:  13
位置:  11 值:  17
位置:  0 值:  2
位置:  14 值:  20
位置:  9 值:  15
位置:  3 值:  5
位置:  13 值:  19
位置:  12 值:  18

排序后:  (15) [2, 3, 4, 5, 6, 7, 8, 10, 13, 15, 16, 17, 18, 19, 20]
計數排序算法耗時: 14.284999999999997ms

基礎：桶排序是計數排序的升級版。它利用了函數的映射關係，高效與否的關鍵就在於這個映射函數的確定。將數組分到有限數量的桶子里。每個桶子再個別排序(有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序)。

在額外空間充足的情況下，合理規劃桶的數量

使用的映射函數能夠將輸入的 N 個數據合理的分配到相應桶中

找出最大值最小值

求出每一個桶的數值范圍

將數值裝入相應桶中并排序

開始合并數組

① 時間復雜度是 O(M+N)，據說是最快最簡單的排序

① 如果輸入數據非常龐大，而桶的數量也非常多，則空間代價是昂貴的,或者數據長度相差過大如[1,255,366,120,156],效率反而變低
示例圖如下,假設初始數組[17, 42, 45, 44, 30, 21, 22, 1, 38, 33, 36, 39, 47, 5, 50, 31, 34, 27, 29, 11],桶為 bucketCount(5)個.
第一步: 找到最小值 1, 最大值 50
第二步: 每一個桶的數值范圍 Math.floor((max - min) / bucketCount) + 1 = 10
第三步: 將數值裝入相應桶中并排序

第四步: 合并數組["1", "5", "11", "17", "21", "22", "27", "29", "30", "31", "33", "34", "36", "38", "39", "42", "44", "45", "47", "50"]

//桶排序
function bucketSort(ary, bucketCount) {
  //類型檢查
  if (!isArray(ary)) return false;
  if (ary.length <= 1) return ary;

  //初始化變量參數
  bucketCount = bucketCount || 5;
  var len = ary.length,
    buckets = [], //桶數組
    max = min = ary[0], //默認取出首位
    space, //數值范圍
    i;

  //找出最大值最小值
  for (i = 1; i < len; i++) {
    min > ary[i] && (min = ary[i]);
    max < ary[i] && (max = ary[i]);
  }

  //求出每一個桶的數值范圍(向下取值并且加一),范圍取值(min -> >=max)
  space = Math.floor((max - min) / bucketCount) + 1;

  //將數值裝入桶中
  for (i = 0; i < len; i++) {
    var item = ary[i], //值
      index = Math.floor((item - min) / space), //難點一,找到相應的桶序列
      bucket = buckets[index]; //桶序列數組

    //判斷是否有對應桶
    if (bucket) {
      //因為數組從小到大排列
      var bucketLen = bucket.length - 1;

      //難點二,逆向比較大小,符合條件數值后移一位,k減一
      while (bucketLen >= 0 && bucket[bucketLen] > item) {
        bucket[bucketLen + 1] = bucket[bucketLen];
        bucketLen--;
      }

      //對應位置插入數組
      bucket[bucketLen + 1] = item;
    } else {
      //新增數值入桶(這裡不能引用變量bucket,詳情http://www.qdfuns.com/notes/40831/dd2b82537d74065b8a53b75e2eb85715.html)
      buckets[index] = [item];
    }
  }

  //開始合并數組
  // 方法一,返回數字格式數組,但是步驟性能都較差
  /* var n = 0, result = [];
  while(n < bucketCount) {
      //中間可能有沒有符合范圍的斷層數組
      if(buckets[n]) result = result.concat(buckets[n]);
      n++;
  }
  return result */

  //方法二,返回字符串格式數組,簡單方便(平均時間快幾毫秒級別)
  return buckets.join(",").split(",");
}

useTime("桶排序算法", bucketSort);

//是否數組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當前入參非數組類型!");
  return bol;
}

//計時小玩意
function useTime(name, fn) {
  var ary = [
    616,
    380,
    751,
    317,
    561,
    722,
    246,
    907,
    970,
    614,
    446,
    917,
    403,
    663,
    312
  ];
  console.time(name + "耗時");
  console.log("排序前: ", ary);
  console.log("排序后: ", fn(ary));
  console.timeEnd(name + "耗時");
}

排序前:  (15) [616, 380, 751, 317, 561, 722, 246, 907, 970, 614, 446, 917, 403, 663, 312]
排序后:  (15) [246, 312, 317, 380, 403, 446, 561, 614, 616, 663, 722, 751, 907, 917, 970]
桶排序算法耗時: 2.3799999999999955ms

基礎：將所有待比較數值(正整數)統一為同樣的數位長度，數位較短的數前面補零。然后，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數列就變成一個有序序列。

找出最大數值的單位長度(我網上看到的別人寫法都是沒有這一步,而是已知單位長度然后傳參進去,我改為自動判斷了)

根據排序方式 LSD/MSD,從低位數或者高位數為基層開始分配,

直到所有位數都分配完之后合并數組

LSD(Least significant digital)：由鍵值的最右邊開始,適用於位數小的數列,由低位數為基底開始進行分配，但在分配之后并不馬上合并回一個數組中，而是在每個“桶子”中建立“子桶”，將每個桶子中的數值按照上一數位的值分配到“子桶”中。在進行完最高位數的分配后再合并回單一的數組中。
MSD(Most significant digital)：由鍵值的最左邊開始,適用於位數大的數列,由高位數為基底開始進行分配，但在分配之后并不馬上合并回一個數組中，而是在每個“桶子”中建立“子桶”，將每個桶子中的數值按照下一數位的值分配到“子桶”中。在進行完最低位數的分配后再合并回單一的數組中。

① 穩定排序;時間復雜度可以突破 O(n)

① 只適用於有基數的情況，比如非數字字符串排序就沒法做了,適用范圍太窄，內存佔用太大。
示例圖如下,假設初始數組[537, 674, 474, 21, 60, 692, 728, 911, 322, 949]

按個位數排序

得出數組[60, 21, 911, 692, 322, 674, 474, 537, 728, 949]

按十位數排序

得出數組[911, 21, 322, 728, 537, 949, 60, 674, 474, 692]

按百位數排序

得出數組[21, 60, 322, 474, 537, 674, 692, 728, 911, 949]

//基數排序
function radixSort(ary) {
  //類型檢查
  if (!isArray(ary)) return false;
  if (ary.length <= 1) return ary;

  var maxLen = (Math.max.apply(null, ary) + "").length, //找出其中的最大值單位長度
    len = ary.length, // 數組長度
    counter = [], //基數數組
    mod = 10, //餘數單位
    dev = 1, //除數單位
    i = 0,
    j,
    index, //序列值
    val;

  //遍歷數值單位位數
  for (; i < maxLen; i++, dev *= 10, mod *= 10) {
    //遍歷數組長度
    for (j = 0; j < len; j++) {
      //難點一,得出數值指定單位的數字,從個位數開始比較,缺省數值補零,如(561 => 1, 6, 5, 0)
      index = parseInt((ary[j] % mod) / dev);
      //將數值放到對應的指定單位序列桶
      !counter[index] && (counter[index] = []);
      // //將數值放到對應的指定單位序列桶
      counter[index].push(ary[j]);
    }

    //統計數組長度,以最大長度為準,即使中間有空數組.
    var counterLen = counter.length, // 統計數組長度
      pos = 0; //定位

    //遍歷桶數組,修改原數組順序
    for (j = 0; j < counterLen; j++) {
      //過濾空數組
      if (counter[j]) {
        while (val = counter[j].shift()) {
          //用pos而不直接用j是因為counter中間可能有斷層
          //修改原數組而不使用新數組是因為該循環多次執行,并不是一次完成排序
          ary[pos++] = val;
        }
      }
    }
  }
  return ary;
}

useTime("基數排序算法", radixSort);

//是否數組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當前入參非數組類型!");
  return bol;
}

//計時小玩意
function useTime(name, fn) {
  var ary = [
    616,
    380,
    751,
    317,
    561,
    722,
    246,
    907,
    970,
    614,
    446,
    917,
    403,
    663,
    312
  ];
  console.time(name + "耗時");
  console.log("排序前: ", ary);
  console.log("排序后: ", fn(ary));
  console.timeEnd(name + "耗時");
}

排序前:  (15) [616, 380, 751, 317, 561, 722, 246, 907, 970, 614, 446, 917, 403, 663, 312]
排序后:  (15) [907, 380, 722, 403, 614, 616, 317, 907, 970, 614, 446, 917, 403, 663, 312]
基數排序算法耗時: 12.169999999999987ms

因為 js 模擬二叉樹比較麻煩，所以堆排序的優勢用 js 語言無法體現， 相對而言 C 語言的鏈表在實現上更能表現堆排序，堆排序或許更適合指針類的計算機語言。(二叉樹算法)

二叉樹的每個結點至多只有二棵子樹

二叉樹的第 i 層至多有 2^(i ? 1)個結點

深度為 k 的二叉樹至多有 2^k ? 1 個結點

堆排序的時間，主要由建立初始堆和反覆重建堆這兩部分的時間開銷構成

堆排序就是把最大堆堆頂的最大數取出，將剩餘的堆繼續調整為最大堆，再次將堆頂的最大數取出，這個過程持續到剩餘數只有一個時結束。在堆中定義以下幾種操作：

最大堆調整(Max-Heapify)：將堆的末端子節點作調整，使得子節點永遠小於父節點

創建最大堆(Build-Max-Heap)：將堆所有數據重新排序，使其成為最大堆

堆排序(Heap-Sort)：移除位在第一個數據的根節點，并做最大堆調整的遞歸運算

① 對於較大的序列，將表現出優越的性能

① 由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。堆排序是穩定時間的，堆排序的排序時間與數據無關意味著同樣大小的數據，可能已經排好序的，堆排序仍然需要花上同樣的時間去排序，內存佔用是快排的兩倍
示例圖如下,假設初始數組[31, 16, 73, 42, 51, 28, 71, 80, 61, 39, 60, 10, 85, 51, 21],二叉樹首次遍歷排序從最后的父結點開始

首次遍歷完成之后,交換首尾位置,然后尾數不參與下次排序,然后從堆頭開始遍歷排序,直到所有排序完成結束

可以好好看看思維導圖,因為單純思考好容易迷糊的.

//堆算法
function maxHeapSort(ary) {
  //類型檢查
  if (!isArray(ary)) return false;
  if (ary.length <= 1) return ary;

  //互換位置
  var swap = function (a, b) {
    ary[a] = [ary[b], (ary[b] = ary[a])][0];
  };

  //尋找父結點
  function buildMaxHeap(len) {
    var i = Math.floor(len / 2) - 1; //難點一，最后一個父尾結點

    //遍歷父結點,將堆所有數據逐層排序，找出最大結點
    for (; i >= 0; i--) {
      maxHeapify(i, len);
    }
  }

  //將堆的末端子節點作調整，使得子節點永遠小於父節點
  function maxHeapify(_index, _len) {
    var left, right, max = _index;

    //可以寫成遞歸,可讀性強一些,但是我覺得遍歷效率會比較好一些.
    while (true) {
      //分別為左子樹結點,右子樹結點,父結點的位置
      left = 2 * _index + 1;
      right = 2 * _index + 2;
      max = _index;

      //分別比較,父結點必須比子樹結點都大,不然換位置
      if (left < _len && ary[left] > ary[max]) max = left;
      if (right < _len && ary[right] > ary[max]) max = right;
      if (max != _index) {
        //順序不對,排序
        swap(_index, max);
        //替換節點位置繼續執行
        _index = max;
      } else {
        break;
      }
    }
  }

  //移除位在第一個數據的根節點，并做最大堆調整的遞歸運算
  function _sort() {

    //首次排序之后得出第一個最大的數值也就是首結點,
    var len = ary.length,
      i = len - 1; //尾部位置

    //初始運行代碼,第一輪遍歷排序，先找出最大節點數提升到堆頭
    buildMaxHeap(len);

    for (; i > 0; i--) {
      //首尾數據互換,原本的尾數被提到首位進行排序(排序的尾數,不是完整數組的尾數)
      swap(0, i);
      //忽略尾部正常順序數據,繼續排序
      maxHeapify(0, i);
    }

    return ary;
  }

  return _sort()
}

useTime("堆算法算法", maxHeapSort);

//是否數組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當前入參非數組類型!");
  return bol;
}

//計時小玩意
function useTime(name, fn) {
  var ary = [
    616,
    380,
    751,
    317,
    561,
    722,
    246,
    907,
    970,
    614,
    446,
    917,
    403,
    663,
    312
  ];
  console.time(name + "耗時");
  console.log("排序前: ", ary);
  console.log("排序后: ", fn(ary));
  console.timeEnd(name + "耗時");
}

排序前:  (15) [616, 380, 751, 317, 561, 722, 246, 907, 970, 614, 446, 917, 403, 663, 312]
排序后:  (15) [246, 312, 317, 380, 403, 446, 561, 614, 616, 663, 722, 751, 907, 917, 970]
堆算法算法耗時: 3.914999999999992ms