排序算法

快排

  1. 算法原理是分治
  2. 取数组中的中间值为标杆，小于或大于这个标杆的分别放入不同数组left 和 right
  3. 分别快排这两个新数组，利用递归实现分治
  4. 排到底时，分出的数组最终只有一个值，合并所有值就行了
  5. 这就是空间换时间的思想
  1. Array.prototype.quickSort = function quickSort() {
  2.     if (this.length <= 1) return this;
  4.     let middleIndex = Math.floor(this.length / 2);
  5.     let middleValue = this.splice(middleIndex, 1)[0];
  7.     let left = [], right = [];
  8.     for (let i = 0; i < this.length; i++) {
  9.         let item = this[i];
  10.         item < middleValue ? left.push(item) : right.push(item);
  11.     }
  13.     return quickSort.call(left).concat(middleValue, quickSort.call(right));
  14. };
  17. let arr = [2, 1, 3, 7, 5];
  18. console.log(arr.quickSort());

归并排序

和快排基本一致，也是利用分治思想
不同的是，归并是在递归的归的时候实现排序，而快排是在递的过程中排序

  1. function merge(left, right) {
  2.     let result = [];
  3.     // 比较左右两个数组的第一个元素，小的就推入结果数组，直到其中一个数组为空
  4.     while (left.length > 0 && right.length > 0) {
  5.         left[0] <= right[0] ? result.push(left.shift())
  6.             : result.push(right.shift());
  7.     }
  9.     // 因为左右两个数组一定是已经分别排好序了，所以剩下一个不为空的数组FIFO推到结果数组result就行了、
  10.     while (left.length > 0) {
  11.         result.push(left.shift());
  12.     }
  14.     while (right.length > 0) {
  15.         result.push(right.shift());
  16.     }
  17.     return result;
  18. }
  20. Array.prototype.mergeSort = function mergeSort() {
  21.     if (this.length <= 1) return this;
  23.     let middleIndex = Math.floor(this.length / 2);
  24.     let left = this.slice(0, middleIndex); // 左边的数组
  25.     let right = this.slice(middleIndex);  // 右边的数组
  26.     // 继续分别对左右两个数组进行归并排序，最终合并结果
  27.     return merge(mergeSort.call(left), mergeSort.call(right));
  28. };
  29. console.log(arr.mergeSort());

数组去重的4种方法

includes法

  1. let ary = [1, 2, 3, 1, 2, 1, 2, 3, 2, 1, 2, 3];
  2. let newAry = [];
  3. for (let i = 0; i < ary.length; i++) {
  4.     let item = ary[i];
  5.     if (newAry.includes(item)) {
  6.         continue;
  7.     }
  8.     newAry.push(item);
  9. }
  10. console.log(newAry);

for循环依次比较筛除法

  1. let ary = [1, 2, 3, 1, 2, 1, 2, 3, 2, 1, 2, 3];
  2. for (let i = 0; i < ary.length; i++) {
  3.     let item = ary[i];
  4.     for (let j = i + 1; j < ary.length; j++) {
  5.         let compare = ary[j];
  6.         if (compare === item) {
  7.             ary.splice(j, 1);
  8.             j--;
  9.         }
  10.     }
  11. }
  12. console.log(ary);

对象去重法

  1. function unique(ary) {
  2.     let obj = {};
  3.     for (let i = 0; i < ary.length; i++) {
  4.         let item = ary[i];
  5.         if (obj[item] !== undefined) {
  6.             ary.splice(i, 1);
  7.             continue;
  8.         }
  9.         obj[item] = item;
  10.     }
  11.     return ary;
  12. }
  13. let aa = [1, 1, 2, 3, 3, 4, 1];
  14. aa = unique(aa);
  15. console.log(aa);

Set去重法

  1. let aa = [1, 1, 2, 3, 3, 4, 1];
  2. console.log(new Set(aa));

数组扁平化的5种方式

  1. let arr = [
  2.     [1, 2, 2],
  3.     [3, 4, 5, 5],
  4.     [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10
  5. ];

flat

字符串化与数组化

调用toSring转为字符串，再拼接成数组，注意需要再转回数字类型

  1. let arr = [
  2.     [1, 2, 2],
  3.     [3, 4, 5, 5],
  4.     [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10
  5. ];
  7. arr = arr.toString().split(',').map(item => {
  8.     return Number(item);
  9. });

序列化

  1. arr = JSON.stringify(arr).replace(/(\[|\])/g, '').split(',').map(item => Number(item));

使用展开运算符+concat拼接数组

  1. // 只要数组中存在数组，就不断展开并concat拼接数组
  2. while (arr.some(item => Array.isArray(item))) {
  3.     arr = [].concat(...arr);
  4.     console.log(arr);
  5. }

深度递归遍历

  1. Array.prototype.myFlat = function () {
  2.     const res = [];
  3.     const fn = arr => {
  4.         arr.forEach(item => {
  5.             Array.isArray(item) ? fn(item) : res.push(item);
  6.         });
  7.     };
  8.     fn(this);
  9.     return res;
  10. };
  12. console.log(arr.myFlat());

数组的交差并补

  1. let arr1 = [1, 2, 3, 4, 5],
  2.     arr2 = [5, 6, 7, 8, 9],
  3.     _arr1Set = new Set(arr1),
  4.     _arr2Set = new Set(arr2);
  6. // 交集
  7. let intersection = arr1.filter(item => _arr2Set.has(item));
  9. // 并集
  10. let union = Array.from(new Set([...arr1, ...arr2]));
  12. // 补集 两个数组各自没有的集合
  13. let complement = [
  14.     ...arr1.filter(item => !_arr2Set.has(item)),
  15.     ...arr2.filter(item => !_arr1Set.has(item))
  16. ];
  18. // 差集 数组arr1相对于arr2所没有的
  19. let diff = arr1.filter(item => !_arr2Set.has(item));

高频题目