一、冒泡排序
冒泡排序的思路：遍历数组，然后将最大数沉到最底部；
时间复杂度：O(N^2)；
空间复杂度：O(1)
function BubbleSort(arr) { if(arr == null || arr.length <= 0){ return []; } var len = arr.length; for(var end = len - 1; end > 0; end--){ for(var i = 0; i < end; i++) { if(arr[i] > arr[i + 1]){ swap(arr, i, i + 1); } } } return arr; } function swap(arr, i, j){ // var temp = arr[i]; // arr[i] = arr[j]; // arr[j] = temp; //交换也可以用异或运算符 arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; }
二、选择排序
选择排序的实现思路：遍历数组，把最小数放在头部；
时间复杂度：O(N^2)；
空间复杂度：O(1)
function SelectionSort(arr) { if(arr == null || arr.length < 0) { return []; } for(var i = 0; i < arr.length - 1; i++) { var minIndex = i; for(var j = i + 1; j < arr.length; j++) { minIndex = arr[j] < arr[minIndex] ? j : minIndex; } swap(arr, i, minIndex); } return arr; } function swap(arr, i, j) { if (i === j) { return; } arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; }
三、插入排序
插入排序实现思路：将一个新的数，和前面的比较，只要当前数小于前一个则和前一个交换位置，否则终止；
时间复杂度：O(N^2)；
空间复杂度：O(1)
function insertSort(arr) { if(arr == null || arr.length <= 0){ return []; } var len = arr.length; for(var i = 1; i < len; i++) { for(var j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { swap(arr, j, j + 1); } } return arr; } function swap(arr, i, j){ var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
四、归并排序
归并排序的思路：
1.先左侧部分排好序
2.再右侧部分排好序
3.再准备一个辅助数组，用外排的方式，小的开始填，直到有个动到末尾，将另一个数组剩余部分拷贝到末尾
4.再将辅助数组拷贝回原数组
时间复杂度:O(N * logN)
空间复杂度:O(N)
// 递归实现 function mergeSort(arr){ if(arr == null || arr.length <= 0){ return []; } sortProcess(arr, 0, arr.length - 1); return arr; } function sortProcess(arr, L, R){ //递归的终止条件，就是左右边界索引一样 if(L == R){ return; } var middle = L + ((R - L) >> 1);//找出中间值 sortProcess(arr, L, middle);//对左侧部分进行递归 sortProcess(arr, middle + 1, R);//对右侧部分进行递归 merge(arr, L, middle, R);//然后利用外排方式进行结合 } function merge(arr, L, middle, R){ var help = []; var l = L; var r = middle + 1; var index = 0; //利用外排方式进行 while(l <= middle && r <= R){ help[index++] = arr[l] < arr[r] ? arr[l++] : arr[r++]; } while(l <= middle){ help.push(arr[l++]); } while(r <= R){ help.push(arr[r++]); } for(var i = 0; i < help.length; i++) { arr[L + i] = help[i]; } //arr.splice(L, help.length, ...help);//这个利用了ES6的语法 }
// 循环实现 function mergeSort(arr){ if(arr ==null || arr.length <= 0){ return []; } var len = arr.length; //i每次乘2，是因为每次合并以后小组元素就变成两倍个了 for(var i = 1; i < len; i *= 2){ var index = 0;//第一组的起始索引 while( 2 * i + index <= len){ index += 2 * i; merge(arr, index - 2 * i, index - i, index); } //说明剩余两个小组，但其中一个小组数据的数量已经不足2的幂次方个 if(index + i < len){ merge(arr, index, index + i, len); } } return arr; } //利用外排的方式进行结合 function merge(arr, start, mid, end){ //新建一个辅助数组 var help = []; var l = start, r = mid; var i = 0; while(l < mid && r < end){ help[i++] = arr[l] < arr[r] ? arr[l++] : arr[r++]; } while(l < mid){ help[i++] = arr[l++]; } while(r < end){ help[i++] = arr[r++]; } for(var j = 0; j < help.length; j++){ arr[start + j] = help[j]; } }
五、快速排序
快速排序实现思路：随机取出一个值进行划分，大于该值放右边，小于该值放左边（该算法在经典快排的基础上经过荷兰国旗思想和随机思想进行了改造）
时间复杂度：O(N*logN)
空间复杂度：O(logN)
function quickSort(arr) { if(arr == null || arr.length <= 0){ return []; } quick(arr, 0, arr.length - 1); } function quick(arr, L, R){ //递归结束条件是L >= R if(L < R){ //随机找一个值，然后和最后一个值进行交换，将经典排序变为快速排序 swap(arr, L + Math.floor(Math.random() * (R - L + 1)), R); //利用荷兰国旗问题获得划分的边界，返回的值是小于区域的最大索引和大于区域的最小索引，在这利用荷兰国旗问题将等于区域部分就不用动了 var tempArr = partition(arr, L, R, arr[R]); quick(arr, L, tempArr[0]); quick(arr, tempArr[1], R); } } //返回值是小于区域最后的索引和大于区域的第一个索引 function partition(arr, L, R, num){ var less = L - 1; var more = R + 1; var cur = L; while(cur < more){ if(arr[cur] < num){ swap(arr, ++less, cur++); }else if(arr[cur] > num) { swap(arr, --more, cur); }else{ cur++; } } return [less, more]; } function swap(arr, i, j){ var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
六、堆排序
堆排序思路：
1.让数组变成大根堆
2.把最后一个位置和堆顶做交换
3.则最大值在最后，则剩下部分做heapify，则重新调整为大根堆，则堆顶位置和该部分最后位置做交换
4.重复进行，直到减完，则这样最后就调整完毕，整个数组排完序（为一个升序）
时间复杂度:O(N * logN)
空间复杂度:O(1)
function heapSort(arr) { if(arr == null || arr.length <= 0) { return []; } //首先是建立大顶堆的过程 for(var i = 0; i < arr.length; i++) { heapInsert(arr, i); } var size = arr.length;//这个值用来指定多少个数组成堆，当得到一个排序的值后这个值减一 //将堆顶和最后一个位置交换 /** * 当大顶堆建立完成后，然后不断将最后一个位置和堆顶交换； * 这样最大值就到了最后，则剩下部分做heapify，重新调整为大根堆，则堆顶位置和倒数第二个位置交换，重复进行，直到全部排序完毕*/ //由于前面已经是大顶堆，所以直接交换 swap(arr, 0, --size); while(size > 0) { //重新变成大顶堆 heapify(arr, 0, size); //进行交换 swap(arr, 0, --size); } } //加堆过程中 function heapInsert(arr, index) { //比较当前位置和其父位置，若大于其父位置，则进行交换，并将索引移动到其父位置进行循环，否则跳过 //结束条件是比父位置小或者到达根节点处 while(arr[index] > arr[parseInt((index - 1) / 2)]){ //进行交换 swap(arr, index, parseInt((index - 1) / 2)); index = parseInt((index - 1) / 2); } } //减堆过程 /** * size指的是这个数组前多少个数构成一个堆 * 如果你想把堆顶弹出，则把堆顶和最后一个数交换，把size减1，然后从0位置经历一次heapify，调整一下，剩余部分变成大顶堆*/ function heapify(arr, index, size) { var left = 2 * index + 1; while(left < size) { var largest = (left + 1 < size && arr[left] < arr[left + 1]) ? left + 1 : left; largest = arr[index] > arr[largest] ? index : largest; //如果最大值索引和传进来索引一样，则该值到达指定位置，直接结束循环 if(index == largest) { break; } //进行交换，并改变索引和其左子节点 swap(arr, index, largest); index = largest; left = 2 * index + 1; } } function swap(arr, i, j) { var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
七、桶排序
桶排序会经历三次遍历：准备一个数组、遍历一遍数组、重构一遍数组，是非基于比较的排序，下面以一个问题来阐述其思路。
问题：
给定一个数组，求如果排序之后，相邻两个数的最大差值，要求时间复杂度O(N),且要求不能用基于比较的排序
思路：
1.准备桶：数组中有N个数就准备N+1个桶
2.遍历一遍数组，找到最大值max和最小值min
。若min = max，则差值=0；若min≠max，则最小值放在0号桶，最大值放在N号桶，剩下的数属于哪个范围就进哪个桶
3.根据鸽笼原理，则肯定有一个桶为空桶，设计该桶的目的是为了否定最大值在一个桶中，则最大差值的两个数一定来自于两个桶，但空桶两侧并不一定是最大值
4.所以只记录所有进入该桶的最小值min和最大值max和一个布尔值表示该桶有没有值
5.然后遍历这个数组，如果桶是空的，则跳到下一个数，如果桶非空，则找前一个非空桶，则最大差值=当前桶min - 上一个非空桶max，用全局变量更新最大值
时间复杂度：O(N)
空间复杂度：O(N)
function maxGap(arr) { if(arr == null || arr.length <= 0) { return 0; } var len = arr.length; var max = -Infinity, min = Infinity; //遍历一遍数组,找到最大值max和最小值min for(var i = 0; i < len; i++) { max = max > arr[i] ? max : arr[i]; min = min > arr[i] ? arr[i] : min; } //若min = max,则差值为0; if(min == max) { return 0; } var hasNum = new Array(len + 1); var mins = new Array(len + 1); var maxs = new Array(len + 1); var bid = 0;//指定桶的编号 for(var i = 0; i < len; i++) { bid = bucket(arr[i], min, max, len);//获得该值是在哪个桶//由于有N+1个桶，所以间隔就是N个，所以此处除以的是len，然后通过这个函数得到应该放到哪个桶里 maxs[bid] = hasNum[bid] ? Math.max(arr[i], maxs[bid]) : arr[i]; mins[bid] = hasNum[bid] ? Math.min(arr[i], mins[bid]) : arr[i]; hasNum[bid] = true; } var res = 0; var lastMax = maxs[0]; for(var i = 0; i < len + 1; i++) { if(hasNum[i]) { res = Math.max(mins[i] - lastMax, res); lastMax = maxs[i]; } } return res; } //获得桶号 //这个函数用于判断在哪个桶中，参数分别为值、最小值、最大值、桶间隔 function bucket(value, min, max, len) { return parseInt((value - min) / ((max - min) / len)); }
八、new
function New (Fn, ...arg) { // 一个新的对象被创建 const result = {}; // 该对象的__proto__属性指向该构造函数的原型 if (Fn.prototype !== null) { Object.setPrototypeOf(result, Fn.prototype); } // 将执行上下文（this）绑定到新创建的对象中 const returnResult = Fn.apply(result, arg); // 如果构造函数有返回值，那么这个返回值将取代第一步中新创建的对象。否则返回该对象 if ((typeof returnResult === "object" || typeof returnResult === "function") && returnResult !== null) { return returnResult; } return result; }
九、instanceof
function Instanceof(left, right) { let leftVal = Object.getPrototypeOf(left); const rightVal = right.prototype; while (leftVal !== null) { if (leftVal === rightVal) return true; leftVal = Object.getPrototypeOf(leftVal); } return false; }
十、 Object.create()
Object.ObjectCreate = (proto, propertiesObject)=> { // 对输入进行检测 if (typeof proto !== 'object' && typeof proto !== 'function' && proto !== null) { throw new Error(`Object prototype may only be an Object or null:${proto}`); } // 新建一个对象 const result = {}; // 将该对象的原型设置为proto Object.setPrototypeOf(result, proto); // 将属性赋值给该对象 Object.defineProperties(result, propertiesObject); // 返回该对象 return result; }
十一、 Object assign()
function ObjectAssign(target, ...sources) { // 对第一个参数的判断，不能为undefined和null if (target === undefined || target === null) { throw new TypeError('cannot convert first argument to object'); } // 将第一个参数转换为对象(不是对象转换为对象) const targetObj = Object(target); // 将源对象(source)自身的所有可枚举属性复制到目标对象（target） for (let i = 0; i < sources.length; i++) { let source = sources[i]; // 对于undefined和null在源角色中不会报错，会直接跳过 if (source !== undefined && source !== null) { // 将源角色转换成对象 // 需要将源角色自身的可枚举属性（包含Symbol值的属性）进行复制 // Reflect.ownKeys(obj) 返回一个数组，包含对象自身的所有属性，不管属性名是Symbol还是字符串，也不管是否可枚举 const keysArray = Reflect.ownKeys(Object(source)); for (let nextIndex = 0; nextIndex < keysArray.length; nextIndex ++) { const nextKey = keysArray[nextIndex]; // 去除不可枚举属性 const desc = Object.getOwnPropertyDescriptor(source, nextKey); if (desc !== undefined && desc.enumerable) { // 后面的属性会覆盖前面的属性 targetObj[nextKey] = source[nextKey]; } } } } return targetObj; } // 由于挂载到Object的assign是不可枚举的,直接挂载上去是可枚举的，所以采用这种方式 if (typeof Object.myAssign !== 'function') { Object.defineProperty(Object, "myAssign", { value : ObjectAssign, writable: true, enumerable: false, configurable: true }); }
十二、 map
Array.prototype.myMap = function(fn) { // 判断输入的第一个参数是不是函数 if (typeof fn !== 'function') { throw new TypeError(fn + 'is not a function'); } // 获取需要处理的数组内容 const arr = this; const len = arr.length; // 新建一个空数组用于装载新的内容 const temp = new Array(len); // 对数组中每个值进行处理 for (let i = 0; i < len; i++) { // 获取第二个参数，改变this指向 let result = fn.call(arguments[1], arr[i], i, arr); temp[i] = result; } // 返回新的结果 return temp; }
十三、 filter
Array.prototype.myFilter = function (fn) { if (typeof fn !== 'function') { throw new TypeError(`${fn} is not a function`); } // 获取该数组 const arr = this; // 获取该数组长度 const len = this.length >>> 0; // 新建一个新的数组用于放置该内容 const temp = []; // 对数组中每个值进行处理 for (let i = 0; i < len; i++) { // 处理时注意this指向 const result = fn.call(arguments[1], arr[i], i, arr); result && temp.push(arr[i]); } return temp; }
十四、 reduce
Array.prototype.myReduce = function(fn) { if (typeof fn !== 'function') { throw new TypeError(`${fn} is not a function`); } const arr = this; const len = arr.length >>> 0; let value;// 最终返回的值 let k = 0;// 当前索引 if (arguments.length >= 2) { value = arguments[1]; } else { // 当数组为稀疏数组时，判断数组当前是否有元素，如果没有索引加一 while (k < len && !( k in arr)) { k++; } // 如果数组为空且初始值不存在则报错 if (k >= len) { throw new TypeError('Reduce of empty array with no initial value'); } value = arr[k++]; } while (k < len) { if (k in arr) { value = fn(value, arr[k], k, arr); } k++; } return value; }
十五、 flat
// 使用reduce和concat Array.prototype.flat1 = function () { return this.reduce((acc, val) => acc.concat(val), []); }
// 使用reduce + concat + isArray +recursivity Array.prototype.flat2 = function (deep = 1) { const flatDeep = (arr, deep = 1) => { // return arr.reduce((acc, val) => Array.isArray(val) && deep > 0 ? [...acc, ...flatDeep(val, deep - 1)] : [...acc, val], []); return deep > 0 ? arr.reduce((acc, val) => acc.concat(Array.isArray(val) ? flatDeep(val, deep - 1) : val), []) : arr.slice(); } return flatDeep(this, deep); }
// 使用forEach + concat + isArray +recursivity // forEach 遍历数组会自动跳过空元素 Array.prototype.flat3 = function (deep = 1) { const result = []; (function flat(arr, deep) { arr.forEach((item) => { if (Array.isArray(item) && deep > 0) { flat(item, deep - 1); } else { result.push(item); } }) })(this, deep); return result; }
// 使用for of + concat + isArray +recursivity // for of 遍历数组会自动跳过空元素 Array.prototype.flat4 = function (deep = 1) { const result = []; (function flat(arr, deep) { for(let item of arr) { if (Array.isArray(item) && deep > 0) { flat(item, deep - 1); } else { // 去除空元素，因为void 表达式返回的都是undefined，不适用undefined是因为undefined在局部变量会被重写 item !== void 0 && result.push(item); } } })(this, deep); return result; }
// 使用堆栈stack Array.prototype.flat5 = function(deep = 1) { const stack = [...this]; const result = []; while (stack.length > 0) { const next = stack.pop(); if (Array.isArray(next)) { stack.push(...next); } else { result.push(next); } } // 反转恢复原来顺序 return result.reverse(); }
