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

因?yàn)楸容^隨心所欲,所以我不按難度分享算法,所以你們會(huì)看到有時(shí)候順序有變化,因?yàn)槲野l(fā)表的時(shí)候會(huì)按照難度修改下位置,盡量讓你們看的時(shí)候能從簡(jiǎn)單開始,
以后每次更新都加個(gè)更新時(shí)間好了,讓你們知道我進(jìn)度.新增計(jì)時(shí)函數(shù)直觀對(duì)比效率
并且因?yàn)橘Y料比較雜,很多都是我個(gè)人理解說法,如果有發(fā)現(xiàn)問題歡迎批評(píng),造福更多人,誤人誤己就不好了
思路是一樣的,寫法不是唯一,所以不用死記代碼的
折騰了這麼久時(shí)間總算把十個(gè)算法都總結(jié)完了,但是還不熟練,一些思想還沒吃透,覺得有些寫法應(yīng)該還能更好,以后肯定還會(huì)找時(shí)間優(yōu)化一下的,但是可能不是最近,我有點(diǎn)迫不及待得想去總結(jié)下其他方面的知識(shí)點(diǎn),例如請(qǐng)求方面的東西,好多短板需要學(xué)習(xí)

PS:
2018/12/18 全新排版,代碼優(yōu)化

PS:經(jīng)博友點(diǎn)明之后,為了提高嚴(yán)謹(jǐn)性,我把測(cè)試方法都新增類型判斷和過濾,生成函數(shù)新增能否重復(fù)取值的參數(shù).
首先介紹一些生成測(cè)試?yán)拥姆椒ńo大家，方便效率不用手動(dòng)添加。

為了提高測(cè)試直觀性,我們采用固定亂序數(shù)組使用.

//是否數(shù)組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當(dāng)前入?yún)⒎菙?shù)組類型!");
  return bol;
}

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


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

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

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

(友情鏈接,什麼叫l(wèi)og,應(yīng)該不少人跟我一樣忘了什麼叫l(wèi)og吧!(～￣▽￣)～)

第一個(gè)循環(huán),從零開始,假設(shè)它是最小值( i )

第二個(gè)循環(huán),從最小值+1( j )位置開始,后續(xù)所有數(shù)據(jù)逐個(gè)跟最小值比較,發(fā)現(xiàn)有更小值就替換掉

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

繼續(xù)重復(fù)步驟直到完成

要實(shí)現(xiàn)上述規(guī)則需要用雙層for循環(huán)

① 最最最簡(jiǎn)單粗暴,不佔(zhàn)用額外的內(nèi)存空間

① 最最最噁心,計(jì)算過程消耗性能巨大,數(shù)組越長(zhǎng)遍歷次數(shù)越多,并且效率極度不穩(wěn)定,不管數(shù)據(jù)亂序程度,它都必定會(huì)遍歷所有數(shù)據(jù)

//選擇排序
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++) {
      //假設(shè)當(dāng)前是最小值
      min = i;

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

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

    return ary;
  })();

  //返回新數(shù)組
  return select;
}

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

//是否數(shù)組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當(dāng)前入?yún)⒎菙?shù)組類型!");
  return bol;
}

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

運(yùn)行結(jié)果:

排序前:  [ 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 ]
選擇排序算法耗時(shí): 12.634ms

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

第一個(gè)循環(huán),從 1 開始,保存當(dāng)前值作參考數(shù)

第二個(gè)循環(huán),從 j=i-1 位置開始,滿足 j>=0 并且 j 位置值大於參考值時(shí)數(shù)值位置后移

不滿足條件中斷循環(huán),參考值賦值當(dāng)前 j+1 位置

要實(shí)現(xiàn)上述規(guī)則需要用到for和while循環(huán)

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

① 計(jì)算過程消耗性能巨大,越往后遍歷次數(shù)越多,跟數(shù)據(jù)亂序程度有關(guān)，最壞情況就是，序列是降序排列，那麼此時(shí)需要進(jìn)行的比較共有 n(n-1)/2 次。插入排序的賦值操作是比較操作的次數(shù)加上 (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, //臨時(shí)變量
    copy = ary.slice(0); // 設(shè)置數(shù)組副本

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

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

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

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

//是否數(shù)組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當(dāng)前入?yún)⒎菙?shù)組類型!");
  return bol;
}

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

運(yùn)行結(jié)果:

排序前:  [ 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 ]
插入排序耗時(shí): 10.002ms

遍歷對(duì)比相鄰兩個(gè)數(shù)據(jù)，小的排在前面，如果前面的數(shù)據(jù)比后面的大就交換位置，這個(gè)算法的名字由來是因?yàn)樵酱蟮脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端.

外循環(huán),從數(shù)組長(zhǎng)度開始遞減

內(nèi)循環(huán),從 i=0 開始不超過數(shù)組長(zhǎng)度開始遞增，比較 i 和 i+1 位置數(shù)字排序

重復(fù)一二步驟

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

① 是比較次數(shù)多，效率較低，每次只能移動(dòng)相鄰兩個(gè)數(shù)據(jù)。最壞情況就是，序列是降序排列，那麼此時(shí)需要進(jìn)行的比較共有 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);

//是否數(shù)組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當(dāng)前入?yún)⒎菙?shù)組類型!");
  return bol;
}

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

運(yùn)行結(jié)果:

排序前:  [ 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 ]
冒泡排序算法耗時(shí): 12.200ms

通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

聲明兩個(gè)新數(shù)組，原數(shù)組里選擇一個(gè)中間元素作為參考數(shù)

其他元素里比參考數(shù)小的和比參考數(shù)大的分別放進(jìn)兩個(gè)新數(shù)組裡并且重新組合成一個(gè)數(shù)組

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

要實(shí)現(xiàn)上述規(guī)則需要用到 for 循環(huán)和遞歸.

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

① 在初始序列有序或者基本有序時(shí)，其時(shí)間復(fù)雜度降為 O(n*n) ,數(shù)據(jù)越多遞歸層級(jí)越深占用堆?？臻g越大。

//快速排序
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; //上面有個(gè)刪除步驟，不能放前面

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

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

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

//是否數(shù)組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當(dāng)前入?yún)⒎菙?shù)組類型!");
  return bol;
}

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

運(yùn)行結(jié)果:

排序前:  [ 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 ]
快速排序算法耗時(shí): 13.195ms

有個(gè)需要注意的地方是過濾數(shù)組部分必須放在聲明變量，再具體點(diǎn)就是提取參考數(shù)之前,放在后面如果數(shù)組長(zhǎng)度為 2,刪除參考數(shù)之后會(huì)因?yàn)榉蠗l件被直接返回剩餘的數(shù)組,可以看看實(shí)例.(如果一次看不到效果,加加減減空格再查看效果就有變化了)

//快速排序
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;

  //過濾部分?jǐn)?shù)組
  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);

//是否數(shù)組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當(dāng)前入?yún)⒎菙?shù)組類型!");
  return bol;
}

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

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

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

要實(shí)現(xiàn)上述規(guī)則需要用到while循環(huán)和嵌套遞歸。

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

① 比較佔(zhàn)用內(nèi)存，復(fù)雜度稍微高一點(diǎn)點(diǎn)

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

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

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

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

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

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

  return excrete(ary);
}

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

//是否數(shù)組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當(dāng)前入?yún)⒎菙?shù)組類型!");
  return bol;
}

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

運(yùn)行結(jié)果:

排序前:  [ 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 ]
歸并排序算法耗時(shí): 13.403ms

基礎(chǔ)：希爾排序是基於插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率。

但插入排序一般來說是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位。
希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。該方法因 DL．Shell 於 1959 年提出而得名。

第一步拆分,固定或動(dòng)態(tài)定義一個(gè)間隔序列,最關(guān)鍵是不管序列多大,最終必須要逐個(gè)遍歷一遍收尾,(我在這步跪了一段時(shí)間才發(fā)現(xiàn));

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

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

第二步按間隔序列排序直到逐個(gè)排序?yàn)橹?/p>

要實(shí)現(xiàn)上述規(guī)則需要用到多個(gè)循環(huán)和插入算法.

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

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

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

第三次循環(huán)增量:3/3=1,最終逐個(gè)遍歷一遍收尾

可以好好看看思維導(dǎo)圖,因?yàn)閱渭兯伎己萌菀酌院?
先來看看百度百科的寫法

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 ]

乍看之下好像挺好理解而且又簡(jiǎn)單沒毛病,但有個(gè)小問題,實(shí)際上這是一個(gè)只能固定增量的代碼,如果你把間隔序列換成其他,也就是 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 ]

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

我繼續(xù)挖掘下網(wǎng)上的代碼,另一種基本代碼都是這麼寫的

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) {
  //動(dòng)態(tài)定義間隔序列
  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 ]

中間動(dòng)態(tài)定義間隔序列的代碼就是解決上面說的問題
但我還不滿意,可擴(kuò)展度還不夠高,下面是我按自己理解寫的一個(gè)希爾算法,只用三個(gè)循環(huán)加個(gè)中斷條件.自測(cè)沒發(fā)現(xiàn)什麼問題,如果有錯(cuò)誤的地方麻煩指出來吧.

//希爾排序
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), //動(dòng)態(tài)間隔序列
    i,
    j;

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

  //間隔序列循環(huán)遞減
  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);
      }
    }
    //另一個(gè)關(guān)鍵地方,不加中斷條件引起死循環(huán)導(dǎo)致內(nèi)存溢出
    if (gap == 1) break;
  }

  return ary;
}

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

//是否數(shù)組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當(dāng)前入?yún)⒎菙?shù)組類型!");
  return bol;
}

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

排序前:  [ 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 ]
希爾排序算法耗時(shí): 8.988ms

基礎(chǔ)：計(jì)數(shù)排序是一個(gè)非基於比較的排序算法,核心在於將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開闢的數(shù)組空間中。作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。計(jì)數(shù)排序?qū)斎氲臄?shù)據(jù)有附加的限制條件：

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

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

統(tǒng)計(jì)數(shù)組統(tǒng)計(jì)每個(gè)值出現(xiàn)次數(shù)和找出其中最大最小值

統(tǒng)計(jì)數(shù)組從 min 位置開始對(duì)所有計(jì)數(shù)開始累加(當(dāng)前項(xiàng)和前一項(xiàng)相加)直到最大值位置為止

根據(jù)統(tǒng)計(jì)數(shù)組的值大小可以知道排列順序，然后反向填充目標(biāo)數(shù)組

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

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

② 不適用數(shù)值相差范圍太大的排序,例如[1, 2, 1000],因?yàn)榻y(tǒng)計(jì)數(shù)組會(huì)從0開始累加直到1000, 即中間太多冗余填充數(shù)據(jù)了.
(這裡只會(huì)打印出值,不會(huì)打印相對(duì)應(yīng)位置,但這是整個(gè)算法的關(guān)鍵,所以建議拷貝到本地去運(yùn)行.)

因?yàn)樗惴ǖ奶厥庑晕覀儞Q一組相差范圍比較小的亂序數(shù)組做測(cè)試.

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

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

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

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

  //算法精華，反向填充數(shù)組!!
  for (k = len - 1; k >= 0; k--) {
    console.log("位置: ", Count[ary[k]] - 1, "值: ", ary[k])
    //Result[位置] = ary值，-1是因?yàn)樾聰?shù)組該從0位置開始排序
    Result[Count[ary[k]] - 1] = ary[k];
    //減少Count數(shù)組中保存的計(jì)數(shù)，注釋掉的話當(dāng)數(shù)組存在重復(fù)數(shù)值時(shí)會(huì)跳過后續(xù)重復(fù)數(shù)值排序
    Count[ary[k]]--;
  }
  return Result;
}

useTime("計(jì)數(shù)排序算法", countingSort);

//是否數(shù)組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當(dāng)前入?yún)⒎菙?shù)組類型!");
  return bol;
}

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

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

第一個(gè)循環(huán)后的Count:  (21) [undefined, undefined, 1, 1, 1, 1, 1, 1, 1, undefined, 1, undefined, undefined, 1, undefined, 1, 1, 1, 1, 1, 1]

第二個(gè)循環(huán)后的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]
計(jì)數(shù)排序算法耗時(shí): 14.284999999999997ms

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

在額外空間充足的情況下，合理規(guī)劃桶的數(shù)量

使用的映射函數(shù)能夠?qū)⑤斎氲?N 個(gè)數(shù)據(jù)合理的分配到相應(yīng)桶中

找出最大值最小值

求出每一個(gè)桶的數(shù)值范圍

將數(shù)值裝入相應(yīng)桶中并排序

開始合并數(shù)組

① 時(shí)間復(fù)雜度是 O(M+N)，據(jù)說是最快最簡(jiǎn)單的排序

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

第四步: 合并數(shù)組["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;

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

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

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

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

    //判斷是否有對(duì)應(yīng)桶
    if (bucket) {
      //因?yàn)閿?shù)組從小到大排列
      var bucketLen = bucket.length - 1;

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

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

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

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

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

//是否數(shù)組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當(dāng)前入?yún)⒎菙?shù)組類型!");
  return bol;
}

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

排序前:  (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]
桶排序算法耗時(shí): 2.3799999999999955ms

基礎(chǔ)：將所有待比較數(shù)值(正整數(shù))統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個(gè)有序序列。

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

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

直到所有位數(shù)都分配完之后合并數(shù)組

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

① 穩(wěn)定排序;時(shí)間復(fù)雜度可以突破 O(n)

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

按個(gè)位數(shù)排序

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

按十位數(shù)排序

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

按百位數(shù)排序

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

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

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

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

    //統(tǒng)計(jì)數(shù)組長(zhǎng)度,以最大長(zhǎng)度為準(zhǔn),即使中間有空數(shù)組.
    var counterLen = counter.length, // 統(tǒng)計(jì)數(shù)組長(zhǎng)度
      pos = 0; //定位

    //遍歷桶數(shù)組,修改原數(shù)組順序
    for (j = 0; j < counterLen; j++) {
      //過濾空數(shù)組
      if (counter[j]) {
        while (val = counter[j].shift()) {
          //用pos而不直接用j是因?yàn)閏ounter中間可能有斷層
          //修改原數(shù)組而不使用新數(shù)組是因?yàn)樵撗h(huán)多次執(zhí)行,并不是一次完成排序
          ary[pos++] = val;
        }
      }
    }
  }
  return ary;
}

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

//是否數(shù)組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當(dāng)前入?yún)⒎菙?shù)組類型!");
  return bol;
}

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

排序前:  (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]
基數(shù)排序算法耗時(shí): 12.169999999999987ms

因?yàn)?js 模擬二叉樹比較麻煩，所以堆排序的優(yōu)勢(shì)用 js 語言無法體現(xiàn)， 相對(duì)而言 C 語言的鏈表在實(shí)現(xiàn)上更能表現(xiàn)堆排序，堆排序或許更適合指針類的計(jì)算機(jī)語言。(二叉樹算法)

二叉樹的每個(gè)結(jié)點(diǎn)至多只有二棵子樹

二叉樹的第 i 層至多有 2^(i ? 1)個(gè)結(jié)點(diǎn)

深度為 k 的二叉樹至多有 2^k ? 1 個(gè)結(jié)點(diǎn)

堆排序的時(shí)間，主要由建立初始堆和反覆重建堆這兩部分的時(shí)間開銷構(gòu)成

堆排序就是把最大堆堆頂?shù)淖畲髷?shù)取出，將剩餘的堆繼續(xù)調(diào)整為最大堆，再次將堆頂?shù)淖畲髷?shù)取出，這個(gè)過程持續(xù)到剩餘數(shù)只有一個(gè)時(shí)結(jié)束。在堆中定義以下幾種操作：

最大堆調(diào)整(Max-Heapify)：將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小於父節(jié)點(diǎn)

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

堆排序(Heap-Sort)：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算

① 對(duì)於較大的序列，將表現(xiàn)出優(yōu)越的性能

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

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

可以好好看看思維導(dǎo)圖,因?yàn)閱渭兯伎己萌菀酌院?

//堆算法
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];
  };

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

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

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

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

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

  //移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算
  function _sort() {

    //首次排序之后得出第一個(gè)最大的數(shù)值也就是首結(jié)點(diǎn),
    var len = ary.length,
      i = len - 1; //尾部位置

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

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

    return ary;
  }

  return _sort()
}

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

//是否數(shù)組
function isArray(obj) {
  var bol = Object.prototype.toString.call(obj) === "[object Array]";
  !bol && alert("當(dāng)前入?yún)⒎菙?shù)組類型!");
  return bol;
}

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

排序前:  (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]
堆算法算法耗時(shí): 3.914999999999992ms