手写new
new
首先创建了一个新的空对象
设置原型，将对象的原型设置为函数的 prototype 对象。
让函数的 this 指向这个对象，执行构造函数的代码（为这个新对象添加属性）
判断函数的返回值类型，如果是值类型，返回创建的对象。如果是引用类型，就返回这个引用类型的对象。
123456789101112function myNew(fn, ...args) { // 判断参数是否是一个函数 if (typeof fn !== "function") { return console.error("type error"); } // 创建一个对象，并将对象的原型绑定到构造函数的原型上 const obj = Object.create(fn.prototype); const value = fn.apply(obj, args); // 调用构造函数，并且this绑定到obj上 // 如果构造函数有返回值，并且返回的是对象，就返回value ;否 ...
手写Object.create、instanceof
Object.create
思路：将传入的对象作为原型
12345function create(obj) { function F() {} F.prototype = obj return new F()}
instanceof
instanceof 运算符用于判断构造函数的 prototype 属性是否出现在对象的原型链中的任何位置。
实现步骤：
首先获取类型的原型
然后获得对象的原型
然后一直循环判断对象的原型是否等于类型的原型，直到对象原型为 null，因为原型链最终为 null123456789101112function myInstanceof(left, right) { let proto = Object.getPrototypeOf(left), // 获取对象的原型 prototype = right.prototype; // 获取构造函数的 prototype 对象 // 判断构造函数的 prototype 对象是否在对象的原型链上 while (true) { ...
排序算法图解
算法复杂度图示
计数排序算法
计数排序算法算法简介
计数排序是一个分布式排序。分布式排序是使用已经组织好的辅助数据结构（称为 “桶”），来得到排好序的数组。它是用来排序整数的优秀算法（它是一个整数排序算法），但是需要更多的内存来存放临时的数组。
算法分析它主要的流程就是先通过原数组得到一个计数数组，然后通过计数数组恢复出排好序的数组：原数组——>计数数组——>排好序的数组。至于计数数组怎么得到，以及计数数组怎么恢复出原数组的问题，看看下面的例子就知道了。
假设有一个比较常规的数组（数组的最小值是 0，且数组中的每一项都是整数，且数值分布在 0~N 的区间内），常规的计数排序过程是这样的：
因为数组的下标是天然排好序的（从小到大），所以我们进行计数数组的下标与原数组的值进行关联 （这个关联的规律自己心里知道就行）。最简单的关联就是，计数数组下标是 0，则其对应了原数组中的数组值 0。那么此时，计数数组下标的最大值就对应了原数组中的数值的最大值。
找出原数组中的最大值 N，然后创建长度为 N + 1 的计数数组。比如原数组中的最大值为 20，那么计数数组的下标的最大值也要为 20（即数组下标范围：0 ~ ...
基数排序算法
基数排序算法算法简介
基数排序是 1887 年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或 bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法（稳定是指相等元素的顺序和原数组中的一直）基数排序(Radix Sort)是桶排序的扩展
算法分析主要思想：
比如：2，22，31，1221，90，85，105
个位排序：90，31，1221，2，22，85，105
十位排序：2，105，1221，22，31，85，90
百位排序：2，22，31，85，90，105，1221
千位排序：2，22，31，85，90，105，1221
注意：每次排序都是在上次排序的基础上进行排序的，也就是说此次排序的位数上他们相对时，就不移动元素（即顺序参数上一个位数的排序顺序）
算法步骤
把所有元素都分配到相 ...
堆排序算法
桶排序算法算法简介
堆是一个完全二叉树。
完全二叉树： 二叉树除开最后一层，其他层结点数都达到最大，最后一层的所有结点都集中在左边（左边结点排列满的情况下，右边才能缺失结点）。大顶堆：根结点为最大值，每个结点的值大于或等于其孩子结点的值。小顶堆：根结点为最小值，每个结点的值小于或等于其孩子结点的值。堆的存储： 堆由数组来实现，相当于对二叉树做层序遍历。如下图：
对于结点 i ，其子结点为 2i+1 与 2i+2 。
算法描述现在需要对如上二叉树做升序排序，总共分为三步：
将初始二叉树转化为大顶堆（heapify）（实质是从第一个非叶子结点开始，从下至上，从右至左，对每一个非叶子结点做shiftDown操作），此时根结点为最大值，将其与最后一个结点交换。除开最后一个结点，将其余节点组成的新堆转化为大顶堆（实质上是对根节点做shiftDown操作），此时根结点为次最大值，将其与最后一个结点交换。重复步骤2，直到堆中元素个数为1（或其对应数组的长度为1），排序完成。下面详细图解这个过程：
步骤1：初始化大顶堆，首先选取最后一个非叶子结点(我们只需要调整父节点和孩子节点之间的大小关系，叶 ...
桶排序算法
桶排序算法算法简介
说到桶排序，它的思想就是把分治用到极致，把一个序列分为一个个桶，然后对每个桶进行排序，最后再进行整合。
算法描述
确定这个序列要分为几个桶
把每个元素放到对应的桶里面
对每个桶进行排序
对所有的桶进行整合
图解倘若我有这样一个序列
现在我们要确定桶的数量，如和确定呢，这里面有一个计算公式
桶的数量 = （最大值 - 最小值）/ 数组长度 + 1
那这里面我们可以确定桶的数量为 49 / 13 +1 = 4；
现在我们再用另一个公式确定每个元素在哪个桶中
元素位置 =（ 元素大小 - 最小值）/ 数组长度
OK，根据这个公式我们可以确定每个元素都在第几个桶里面
现在再对每一个桶进行排序（这里面没有固定的排序算法）
对每个桶进行排序后最后我们进行整合，就变成了一个有序的序列。
代码示例1234567891011121314151617181920212223242526272829 function bucketSort(arr){ let max = Math.max(...arr); let min = Math.min(...arr); ...
归并排序算法
希尔排序算法算法简介
先递归的分解数列，再合并数列（分治思想的典型应用）
基本思想与过程：先递归的分解数列，再合并数列（分治思想的典型应用）
将一个数组拆成 A、B 两个小组，两个小组继续拆，直到每个小组只有一个元素为止。
按照拆分过程逐步合并小组，由于各小组初始只有一个元素，可以看做小组内部是有序的，合并小组可以被看做是合并两个有序数组的过程。
对左右两个小数列重复第二步，直至各区间只有 1 个数。
下面对数组【42,20,17,13,28,14,23,15】进行归并排序，模拟排序过程如下：
第一步：拆分数组，一共需要拆分三次（logN）；
第一次拆成【42,20,17,13】，【28,14,23,15】，
第二次拆成【42,20】，【17,13】，【28,14】，【23,15】，、
第三次拆成【42】，【20】，【17】，【13】，【28】，【14】，【23】，【15】；
第二步：逐步归并数组，采用合并两个有序数组的方法，每一步其算法复杂度基本接近于 O(N)
第一次归并为【20,42】，【13,17】，【14,28】，【15,23】
第二次归并为【13,17,20,42 ...
希尔排序算法
希尔排序算法算法简介
1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
算法描述将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
选择一个增量序列t1，t2，…，tk，其中t1>t2>…，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
代码示例12345678910111213141516171819function shellSort(arr) { let len = arr.length; // gap 即为增量 for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) { for (let i = gap; i < ...
插入排序算法
插入排序算法算法简介
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法步骤将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
动画演示
1234567891011121314function insertionSort(arr) { let len = arr.length; let preIndex, current; for (let i = 1; i < len; i++) { preIndex = i - 1; current = arr[i]; while(preIndex >= ...
