一些前端算法詳解-不定时更新

前言

因為比较随心所欲, 所以我不按难度分享算法, 所以你们会看到有时候顺序有变化, 因為我发表的时候会按照难度修改下位置, 尽量让你们看的时候能从简单开始,
以后每次更新都加个更新时间好了, 让你们知道我进度. 新增计时函数直观对比效率
并且因為资料比较杂, 很多都是我个人理解说法, 如果有发现问题欢迎批评, 造福更多人, 误人误己就不好了
思路是一样的, 写法不是唯一, 所以不用死记代码的
折腾了这麼久时间总算把十个算法都总结完了, 但是还不熟练, 一些思想还没吃透, 觉得有些写法应该还能更好, 以后肯定还会找时间优化一下的, 但是可能不是最近, 我有点迫不及待得想去总结下其他方面的知识点, 例如请求方面的东西, 好多短板需要学习

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 吧!(～~▽~)～)

排序方法	平均情况	最好情况	最坏情况	空间复杂度	排序方式	稳定性
选择排序	O(n²)	O(n²)	O(n²)	O(1)	In-place	不稳定
插入排序	O(n²)	O(n)	O(n²)	O(1)	In-place	稳定
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	In-place	稳定
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	In-place	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	Out-place	稳定
希尔排序	O(n log n)	O(n log² n)	O(n log² n)	O(1)	In-place	不稳定
计数排序	O(n + k)	O(n + k)	O(n + k)	O(k)	Out-place	稳定
桶排序	O(n + k)	O(n + k)	O(n²)	O(n + k)	Out-place	稳定
基数排序	O(n * k)	O(n * k)	O(n * k)	O(n + k)	Out-place	稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	In-place	不稳定

名词解释

术语	描述
n	数据规模
k	桶的个数
In-place	佔用常数内存，不佔用额外内存
Out-place	佔用额外内存
稳定性	存在相同的元素的话，排序前后他们的相对位置会不会发生变化

选择排序算法

思路：

1. 第一个循环, 从零开始, 假设它是最小值(i)
2. 第二个循环, 从最小值 +1(j)位置开始, 后续所有数据逐个跟最小值比较, 发现有更小值就替换掉
3. 第二层循环遍历完后如果最小值已经改变了, 就跟原最小值 (也就是第一层循环的 i) 互换位置
4. 继续重复步骤直到完成

要实现上述规则需要用双层 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. 第一个循环, 从 1 开始, 保存当前值作参考数
2. 第二个循环, 从 j=i-1 位置开始, 满足 j>=0 并且 j 位置值大於参考值时数值位置后移
3. 不满足条件中断循环, 参考值赋值当前 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

冒泡排序演算法

思路：

遍歷对比相邻两个数据，小的排在前面，如果前面的数据比后面的大就交换位置，这个算法的名字由来是因為越大的元素会经由交换慢慢“浮”到数列的顶端.

1. 外循环, 从数组长度开始递减
2. 内循环, 从 i=0 开始不超过数组长度开始递增，比较 i 和 i+1 位置数字排序
3. 重复一二步骤

优点：

① 最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需 (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

快速排序算法

思路：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

1. 声明两个新数组，原数组里选择一个中间元素作为参考数
2. 其他元素里比参考数小的和比参考数大的分别放进两个新数组裡并且重新组合成一个数组
3. 然后不断重复一二步骤直到完成为止

要实现上述规则需要用到 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 + "耗时");
}

归并排序算法

思路：

1. 第一步拆分, 数据不断从中间拆分, 直到无法继续为止(从上至下)
   [12,56,23,2] => [12,56] + [23,2] => [12] + [56] + [23] + [2]
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

希尔排序算法

基础：希尔排序是基於插入排序的以下两点性质而提出改进方法的：

1. 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
2. 但插入排序一般来说是低效的，因為插入排序每次只能将数据移动一位。
   希尔排序 (Shell Sort) 是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 DL．Shell 於 1959 年提出而得名。

思路：

1. 第一步拆分, 固定或动态定义一个间隔序列, 最关键是不管序列多大, 最终必须要逐个遍歷一遍收尾,(我在这步跪了一段时间才发现);

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

   例如长度 100, 跨度是 2, 初始间隔序列 = 长度 / 跨度, 递减量 = 自身 / 跨度即 50,25,22…..1

2. 第二步按间隔序列排序直到逐个排序為止

要实现上述规则需要用到多个循环和插入算法.

优点：

本质上讲，希尔排序算法是直接插入排序算法的一种改进，减少了其复製的次数，速度要快很多, 原因是
① 当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
② 当 n 值较小时，n 和 n² 的差别也较小，即直接插入排序的最好时间复杂度 O(n) 和最坏时间复杂度 O(n²)差别不大。
③ 在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由於已经按增量距离排过序，使文件较接近於有序状态，所以新的一趟排序过程也较快。

缺点：

对规模非常大的数据排序不是最优选择
示例图如下, 假设原数组[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

计数排序演算法

基础：计数排序是一个非基於比较的排序算法, 核心在於将输入的数据值转化為键存储在额外开闢的数组空间中。作為一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。计数排序对输入的数据有附加的限制条件：

1. 输入的线性表的元素属於有限偏序集 S；
2. 设输入的线性表的长度為 n，|S|=k(表示集合 S 中元素的总数目為 k)，则 k=O(n)。
   在这两个条件下，计数排序的复杂性為 O(n)。

思路：

1. 统计数组统计每个值出现次数和找出其中最大最小值
2. 统计数组从 min 位置开始对所有计数开始累加 (当前项和前一项相加) 直到最大值位置為止
3. 根据统计数组的值大小可以知道排列顺序，然后反向填充目标数组

优点：

① 在对一定范围内的整数排序时，它的复杂度為 Ο(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

桶排序演算法

基础：桶排序是计数排序的升级版。它利用了函数的映射关係，高效与否的关键就在於这个映射函数的确定。将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。

1. 在额外空间充足的情况下，合理规划桶的数量
2. 使用的映射函数能够将输入的 N 个数据合理的分配到相应桶中

思路：

1. 找出最大值最小值
2. 求出每一个桶的数值范围
3. 将数值装入相应桶中并排序
4. 开始合并数组

优点：

① 时间复杂度是 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

基数排序演算法

基础：将所有待比较数值 (正整数) 统一為同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

思路：

1. 找出最大数值的单位长度(我网上看到的别人写法都是没有这一步, 而是已知单位长度然后传参进去, 我改為自动判断了)
2. 根据排序方式 LSD/MSD, 从低位数或者高位数為基层开始分配,
3. 直到所有位数都分配完之后合并数组

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 语言的链表在实现上更能表现堆排序，堆排序或许更适合指针类的计算机语言。(二叉树算法)

1. 二叉树的每个结点至多只有二棵子树
2. 二叉树的第 i 层至多有 2^(i − 1)个结点
3. 深度為 k 的二叉树至多有 2^k − 1 个结点

堆排序的时间，主要由建立初始堆和反覆重建堆这两部分的时间开销构成

思路：

堆排序就是把最大堆堆顶的最大数取出，将剩餘的堆继续调整為最大堆，再次将堆顶的最大数取出，这个过程持续到剩餘数只有一个时结束。在堆中定义以下几种操作：

1. 最大堆调整(Max-Heapify)：将堆的末端子节点作调整，使得子节点永远小於父节点
2. 创建最大堆(Build-Max-Heap)：将堆所有数据重新排序，使其成為最大堆
3. 堆排序(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