07 | 数组原理（上）：帮你梳理眼花缭乱的数组 API

数组概念的探究

截至 ES7 规范，数组共包含 33 个标准的 API 方法和一个非标准的 API 方法

Array 的构造器

Array 构造器用于创建一个新的数组

  1. // 1. 对象字面量
  2. let arr1 = [];
  3. // 使用对象字面量
  4. var b = [];
  5. b.length = 6; // [empty × 6]
  7. // 2. 使用 Array 构造器，可以自定义长度
  8. var a = Array(6); // [empty × 6]

Array 构造器根据参数长度的不同，有如下两种不同的处理方式：

  • new Array(arg1, arg2,…)
    • 参数长度为 0 或长度大于等于 2 时，传入的参数将按照顺序依次成为新数组的第 0 至第 N 项（参数长度为0 时，返回空数组）
  • new Array(len)
    • 如果传入的不是数字类型，作为数组的元素
    • 如果传入的是数字类型的，表示创建一个长度为len的数组，元素都为空
      • len 最大不能超过 32 位无符号整型，即需要小于 2 的 32 次方（len 最大为 Math.pow(2,32)），否则将抛出 RangeError。
      • [empty × 6]

        ES6 新增的构造方法：Array.of 和 Array.from

        Array.of

        Array.of 用于将参数依次转化为数组中的一项，然后返回这个新数组，而不管这个参数是数字还是其他 ```javascript Array.of(8.0); // [8] Array(8.0); // [empty × 8]

Array.of(8.0, 5); // [8, 5] Array(8.0, 5); // [8, 5]

Array.of(‘8’); // [“8”] Array(‘8’); // [“8”]

  1. <a name="FndNu"></a>
  2. ### Array.from
  3. Array.from 的设计初衷是快速便捷地基于其他对象创建新数组，准确来说就是从一个类似数组的可迭代对象中创建一个新的数组实例。其实就是，只要一个对象有迭代器，Array.from 就能把它变成一个数组（注意：是返回新的数组，不改变原对象）
  5. Array.from 拥有 3 个参数：
  7. 1. 类似数组的对象，必选；<br />
  8. 2. 加工函数，新生成的数组会经过该函数的加工再返回；<br />
  9. 3. this 作用域，表示加工函数执行时 this 的值
  10. ```javascript
  11. var obj = {0: 'a', 1: 'b', 2:'c', length: 3};
  12. Array.from(obj, function(value, index){
  13.   console.log(value, index, this, arguments.length);
  14.   return value.repeat(3);   //必须指定返回值，否则返回 undefined
  15. }, obj);  
  16. // ["aaa","bbb","ccc"]

除了objectm, 有迭代器的对象还包括 String、Set、Map 等

  1. // String
  2. Array.from('abc');         // ["a", "b", "c"]
  3. // Set
  4. Array.from(new Set(['abc', 'def'])); // ["abc", "def"]
  5. // Map
  6. Array.from(new Map([[1, 'ab'], [2, 'de']])); 
  7. // [[1, 'ab'], [2, 'de']]

Array 的判断

  1. var a = [];
  2. // 1.基于instanceof
  3. a instanceof Array;
  4. // 2.基于constructor
  5. a.constructor === Array;
  6. // 3.基于Object.prototype.isPrototypeOf
  7. Array.prototype.isPrototypeOf(a);
  8. // 4.基于getPrototypeOf
  9. Object.getPrototypeOf(a) === Array.prototype;
  10. // 5.基于Object.prototype.toString
  11. Object.prototype.toString.apply(a) === '[object Array]';
  12. // 6.ES6 新增的方法 Array.isArray 如果兼容性有问题，其实也是用的方法5
  13. Array.isArray(a)

数组API - 改变自身的方法

基于 ES6，会改变自身值的方法一共有 9 个，分别为 pop、push、reverse、shift、sort、splice、unshift，以及两个 ES6 新增的方法 copyWithin 和 fill。

  1. // pop方法
  2. var array = ["cat", "dog", "cow", "chicken", "mouse"];
  3. var item = array.pop();
  4. console.log(array); // ["cat", "dog", "cow", "chicken"]
  5. console.log(item); // mouse
  6. // push方法
  7. var array = ["football", "basketball",  "badminton"];
  8. var i = array.push("golfball");
  9. console.log(array); 
  10. // ["football", "basketball", "badminton", "golfball"]
  11. console.log(i); // 4
  12. // reverse方法
  13. var array = [1,2,3,4,5];
  14. var array2 = array.reverse();
  15. console.log(array); // [5,4,3,2,1]
  16. console.log(array2===array); // true
  17. // shift方法
  18. var array = [1,2,3,4,5];
  19. var item = array.shift();
  20. console.log(array); // [2,3,4,5]
  21. console.log(item); // 1
  22. // unshift方法
  23. var array = ["red", "green", "blue"];
  24. var length = array.unshift("yellow");
  25. console.log(array); // ["yellow", "red", "green", "blue"]
  26. console.log(length); // 4
  27. // sort方法
  28. var array = ["apple","Boy","Cat","dog"];
  29. var array2 = array.sort();
  30. console.log(array); // ["Boy", "Cat", "apple", "dog"]
  31. console.log(array2 == array); // true
  32. // splice方法
  33. var array = ["apple","boy"];
  34. var splices = array.splice(1,1);
  35. console.log(array); // ["apple"]
  36. console.log(splices); // ["boy"]
  37. // copyWithin方法
  38.   // array.copyWithin(target, start, end)
  39.   // target    必需。复制到指定目标索引位置。
  40.   // start    可选。元素复制的起始位置。
  41.   // end    可选。停止复制的索引位置 (默认为 array.length)。如果为负值，表示倒数。
  42. var array = [1,2,3,4,5]; 
  43. var array2 = array.copyWithin(0,3);
  44. console.log(array===array2,array2);  // true [4, 5, 3, 4, 5]
  45. // fill方法
  46. var array = [1,2,3,4,5];
  47. var array2 = array.fill(10,0,3);
  48. console.log(array===array2,array2);  // true [10, 10, 10, 4, 5], 可见数组区间[0,3]的元素全部替换为10

数组API - 不改变自身的方法

基于 ES7，不会改变自身的方法也有 9 个，分别为 concat、join、slice、toString、toLocaleString、indexOf、lastIndexOf、未形成标准的 toSource，以及 ES7 新增的方法 includes。

  1. // concat方法
  2. var array = [1, 2, 3];
  3. var array2 = array.concat(4,[5,6],[7,8,9]);
  4. console.log(array2); // [1, 2, 3, 4, 5, 6, 7, 8, 9]
  5. console.log(array); // [1, 2, 3], 可见原数组并未被修改
  6. // join方法
  7. var array = ['We', 'are', 'Chinese'];
  8. console.log(array.join()); // "We,are,Chinese"
  9. console.log(array.join('+')); // "We+are+Chinese"
  10. // slice方法
  11. var array = ["one", "two", "three","four", "five"];
  12. console.log(array.slice()); // ["one", "two", "three","four", "five"]
  13. console.log(array.slice(2,3)); // ["three"]
  14. // toString方法
  15. var array = ['Jan', 'Feb', 'Mar', 'Apr'];
  16. var str = array.toString();
  17. console.log(str); // Jan,Feb,Mar,Apr
  18. // tolocalString方法
  19. var array= [{name:'zz'}, 123, "abc", new Date()];
  20. var str = array.toLocaleString();
  21. console.log(str); // [object Object],123,abc,2016/1/5 下午1:06:23
  22. // indexOf方法
  23. var array = ['abc', 'def', 'ghi','123'];
  24. console.log(array.indexOf('def')); // 1
  25. // includes方法
  26. var array = [-0, 1, 2];
  27. console.log(array.includes(+0)); // true
  28. console.log(array.includes(1)); // true
  29. var array = [NaN];
  30. console.log(array.includes(NaN)); // true

数组API - 数组遍历

基于 ES6，不会改变自身的遍历方法一共有 12 个，分别为 forEach、every、some、filter、map、reduce、reduceRight，以及 ES6 新增的方法 entries、find、findIndex、keys、values。

  1. // forEach方法
  2. var array = [1, 3, 5];
  3. var obj = {name:'cc'};
  4. var sReturn = array.forEach(function(value, index, array){
  5.   array[index] = value;
  6.   console.log(this.name); // cc被打印了三次, this指向obj
  7. },obj);
  8. console.log(array); // [1, 3, 5]
  9. console.log(sReturn); // undefined, 可见返回值为undefined
  10. // every方法
  11. var o = {0:10, 1:8, 2:25, length:3};
  12. var bool = Array.prototype.every.call(o,function(value, index, obj){
  13.   return value >= 8;
  14. },o);
  15. console.log(bool); // true
  16. // some方法
  17. var array = [18, 9, 10, 35, 80];
  18. var isExist = array.some(function(value, index, array){
  19.   return value > 20;
  20. });
  21. console.log(isExist); // true 
  22. // map 方法
  23. var array = [18, 9, 10, 35, 80];
  24. array.map(item => item + 1);
  25. console.log(array);  // [19, 10, 11, 36, 81]
  26. // filter 方法
  27. var array = [18, 9, 10, 35, 80];
  28. var array2 = array.filter(function(value, index, array){
  29.   return value > 20;
  30. });
  31. console.log(array2); // [35, 80]
  32. // reduce方法
  33. var array = [1, 2, 3, 4];
  34. var s = array.reduce(function(previousValue, value, index, array){
  35.   return previousValue * value;
  36. },1);
  37. console.log(s); // 24
  38. // ES6写法更加简洁
  39. array.reduce((p, v) => p * v); // 24
  40. // reduceRight方法 (和reduce的区别就是从后往前累计)
  41. var array = [1, 2, 3, 4];
  42. array.reduceRight((p, v) => p * v); // 24
  43. // entries方法
  44. var array = ["a", "b", "c"];
  45. var iterator = array.entries();
  46. console.log(iterator.next().value); // [0, "a"]
  47. console.log(iterator.next().value); // [1, "b"]
  48. console.log(iterator.next().value); // [2, "c"]
  49. console.log(iterator.next().value); // undefined, 迭代器处于数组末尾时, 再迭代就会返回undefined
  50. // find & findIndex方法
  51. var array = [1, 3, 5, 7, 8, 9, 10];
  52. function f(value, index, array){
  53.   return value%2==0;     // 返回偶数
  54. }
  55. function f2(value, index, array){
  56.   return value > 20;     // 返回大于20的数
  57. }
  58. console.log(array.find(f)); // 8
  59. console.log(array.find(f2)); // undefined
  60. console.log(array.findIndex(f)); // 4
  61. console.log(array.findIndex(f2)); // -1
  62. // keys方法
  63. [...Array(10).keys()];     // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  64. [...new Array(10).keys()]; // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  65. // values方法
  66. var array = ["abc", "xyz"];
  67. var iterator = array.values();
  68. console.log(iterator.next().value);//abc
  69. console.log(iterator.next().value);//xyz

reduce
array.reduce(function(prevVal, curVal, curIndex, array), initialValue)

  • callback（一个在数组的每一项中调用的函数，接受四个参数）：
    • previousValue（上一次调用回调函数时的返回值，或者初始值）
    • currentValue（当前正在处理的数组元素）
    • currentIndex（当前正在处理的数组元素下标）
    • array（调用 reduce() 方法的数组）
  • initialValue（可选的初始值，作为第一次调用回调函数时传给 previousValue 的值）

题目： var arr = [ {name: ‘brick1’}, {name: ‘brick2’}, {name: ‘brick3’} ]
希望最后返回到 arr 里面每个对象的 name 拼接数据为 ‘brick1, brick2 & brick3’ ，如果用 reduce 如何实现呢？

  1. function getName(arr){
  2.     return arr.reduce(function(prevVal, curVal, curIndex, arr){
  3.       // curIndex === 0 return curVal
  4.     // curIndex === arr.length-1 return prevVal + & curVal
  5.     // return prevVal + , + curVal
  6.     if(curIndex === 0){
  7.         return curVal.name;
  8.     }else if(curIndex === arr.length-1){
  9.         return prevVal + '&' + curVal.name
  10.     }else{
  11.         return prevVal + ',' + curVal.name
  12.     }
  13.   }, '')
  14. }
  16. let arr = [ {name: 'brick1'}, {name: 'brick2'}, {name: 'brick3'} ]
  17. getName(arr) // 'brick1, brick2 & brick3'

image.png
以上，数组的各方法基本讲解完毕，这些方法之间存在很多共性，如下：

  • 所有插入元素的方法，比如 push、unshift 一律返回数组新的长度；
  • 所有删除元素的方法，比如 pop、shift、splice 一律返回删除的元素，或者返回删除的多个元素组成的数组；
  • 部分遍历方法，比如 forEach、every、some、filter、map、find、findIndex，它们都包含 function(value,index,array){} 和 thisArg 这样两个形参

08 | 数组原理（中）：如何理解 JS 的类数组？

JavaScript 中有哪些情况下的对象是类数组

  • 函数里面的参数对象 arguments；
  • 用 getElementsByTagName/ClassName/Name 获得的 HTMLCollection；

  • 用 querySelector 获得的 NodeList。

    类数组基本介绍

    arguments

    函数参数列表

    1. function foo(name, age, sex) {
    2.   console.log(arguments);
    3.   console.log(typeof arguments); // object
    4.   console.log(Object.prototype.toString.call(arguments)); // [object Arguments]
    5. }
    6. foo('jack', '18', 'male');

    image.png

    HTMLCollection

    HTMLCollection 简单来说是 HTML DOM 对象的一个接口，这个接口包含了获取到的 DOM 元素集合，返回的类型是类数组对象，如果用 typeof 来判断的话，它返回的是 ‘object’。它是及时更新的，当文档中的 DOM 变化时，它也会随之变化。

    1. var elem1, elem2;
    2. // document.forms 是一个 HTMLCollection
    3. elem1 = document.forms[0];
    4. elem2 = document.forms.item(0);
    5. console.log(elem1);
    6. console.log(elem2);
    7. console.log(typeof elem1);
    8. console.log(Object.prototype.toString.call(elem1));

    image.png

    NodeList

    NodeList 对象是节点的集合，通常是由 querySelector 返回的。NodeList 不是一个数组，也是一种类数组。虽然 NodeList 不是一个数组，但是可以使用 for…of 来迭代。在一些情况下，NodeList 是一个实时集合，也就是说，如果文档中的节点树发生变化，NodeList 也会随之变化。

    1. var list = document.querySelectorAll('input[type=checkbox]');
    2. for (var checkbox of list) {
    3. checkbox.checked = true;
    4. }
    5. console.log(list);
    6. console.log(typeof list);
    7. console.log(Object.prototype.toString.call(list));

    image.png

    类数组应用场景

    遍历参数操作

    1. function add() {
    2.   var sum =0,
    3.       len = arguments.length;
    4.   for(var i = 0; i < len; i++){
    5.       sum += arguments[i];
    6.   }
    7.   return sum;
    8. }
    9. add()                           // 0
    10. add(1)                          // 1
    11. add(1，2)                       // 3
    12. add(1,2,3,4);                   // 10

    定义链接字符串函数

    1. function myConcat(separa) {
    2. var args = Array.prototype.slice.call(arguments, 1); // 类数组转化为数组，并从1截取到数组末尾 ["red", "orange", "blue"] 
    3. return args.join(separa);
    4. }
    5. myConcat(", ", "red", "orange", "blue");
    6. // "red, orange, blue"
    7. myConcat("; ", "elephant", "lion", "snake");
    8. // "elephant; lion; snake"
    9. myConcat(". ", "one", "two", "three", "four", "five");
    10. // "one. two. three. four. five"

    传递参数使用

    1. // 使用 apply 将 foo 的参数传递给 bar
    2. function foo() {
    3.   bar.apply(this, arguments); // apply 接受参数数组    call 接受参数列表
    4. }
    5. function bar(a, b, c) {
    6.  console.log(a, b, c);
    7. }
    8. foo(1, 2, 3)   //1 2 3

    如何将类数组转换成数组

    类数组借用数组方法转数组

  • Array.prototype.push.call(obj, a, b)

  • Array.prototype.concat.apply([], 参数数组)

  • [].slice.call(arguments)

    1. var arrayLike = { 
    2. 0: 'java',
    3. 1: 'script',
    4. length: 2
    5. } 
    6. Array.prototype.push.call(arrayLike, 'jack', 'lily'); 
    7. console.log(typeof arrayLike); // 'object'
    8. console.log(arrayLike);
    9. // {0: "java", 1: "script", 2: "jack", 3: "lily", length: 4}
    1. function sum(a, b) {
    2. let args = Array.prototype.slice.call(arguments);
    3. // let args = [].slice.call(arguments); // 这样写也是一样效果
    4. console.log(args.reduce((sum, cur) => sum + cur));
    5. }
    6. sum(1, 2);  // 3
    7. function sum(a, b) {
    8. let args = Array.prototype.concat.apply([], arguments);
    9. console.log(args.reduce((sum, cur) => sum + cur));
    10. }
    11. sum(1, 2);  // 3

    ES6 的方法转数组

  • Array.from({类数组对象})

  • [...arguments]
  • ...args
    1. function sum(a, b) {
    2. let args = Array.from(arguments);
    3. console.log(args.reduce((sum, cur) => sum + cur));
    4. }
    5. sum(1, 2);    // 3
    6. function sum(a, b) {
    7. let args = [...arguments];
    8. console.log(args.reduce((sum, cur) => sum + cur));
    9. }
    10. sum(1, 2);    // 3
    11. function sum(...args) {
    12. console.log(args.reduce((sum, cur) => sum + cur));
    13. }
    14. sum(1, 2);    // 3

    总结

    image.png

    09 | 数组原理（下）：实现数组扁平化的 6 种方式

    数组扁平化

    将多层嵌套数组拍扁
    1. var arr = [1, [2, [3, 4，5]]];
    2. console.log(flatten(arr)); // [1, 2, 3, 4，5]

    扁平化的实现

    方法一：普通的递归实

    1. var arr = [1, [2, [3, 4, 5]]];
    2.   function flatten(arr){
    3.       let res = [];
    4.       for(let i=0;i<arr.length;i++){
    5.           if(Array.isArray(arr[i])){
    6.               res = res.concat(flatten(arr[i]))
    7.           }else{
    8.               res.push(arr[i]);
    9.           }
    10.       }
    11.       return res;
    12.   }
    13.   console.log(flatten(arr))

    方法二：利用 reduce 函数迭代

    1. function flatten2(arr){
    2.       return arr.reduce(function(prev, cur){
    3.           return prev.concat(Array.isArray(cur) ? flatten2(cur) : cur)
    4.       }, [])
    5.   }
    6.   console.log(flatten2(arr))

    方法三：扩展运算符实现

    1. // 方法3
    2. var arr = [1, [2, [3, 4]]];
    3. function flatten(arr) {
    4.   while (arr.some(item => Array.isArray(item))) {
    5.       arr = [].concat(...arr);
    6.   }
    7.   return arr;
    8. }
    9. console.log(flatten(arr)); //  [1, 2, 3, 4，5]

    方法四：split 和 toString 共同处理

    转化为字符串后，用特定的分隔符转化为数组

  1. var arr = [1, [2, [3, 4]]];
  2. function flatten(arr) {
  3.     return arr.toString().split(',');
  4. }
  5. console.log(flatten(arr)); //  [1, 2, 3, 4，5]

方法五：调用 ES6 中的 flat

arr.flat([depth])

  1. // 方法5
  2. var arr = [1, [2, [3, 4]]];
  3. function flatten(arr) {
  4.   return arr.flat(Infinity);
  5. }
  6. console.log(flatten(arr)); //  [1, 2, 3, 4，5]

方法六：正则和 JSON 方法共同处理

  1. // 方法 6
  2. let arr = [1, [2, [3, [4, 5]]], 6];
  3. function flatten(arr) {
  4.   let str = JSON.stringify(arr);
  5.   str = str.replace(/(\[|\])/g, '');
  6.   str = '[' + str + ']';
  7.   return JSON.parse(str); 
  8. }
  9. console.log(flatten(arr)); //  [1, 2, 3, 4，5]

总结

image.png

10 | 数组排序（上）：如何用 JS 实现各种数组排序？

各种排序的 JS 实现

image.png

归并排序

时间复杂度
O(nlogn)
思想

  • 分解子问题：将需要被排序的数组从中间分割为两半，然后再将分割出来的每个子数组各分割为两半，重复以上操作，直到单个子数组只有一个元素为止。
  • 求解每个子问题：从粒度最小的子数组开始，两两合并、确保每次合并出来的数组都是有序的。（这里的“子问题”指的就是对每个子数组进行排序）。
  • 合并子问题的解，得出大问题的解：当数组被合并至原有的规模时，就得到了一个完全排序的数组
    1. /**
    2. * 分解：将数组一分为二, 直到拆分为单个元素组成的数组为止
    3. * 合并：将最小的数组排序并合并（两个单元素合并为一个双元素数组 两个双合并为一个四元素）
    4. */
    5. function mergeSort(arr) {
    6. let len = arr.length;
    7. // 递归边界
    8. if (len <= 1) {
    9.   return arr;
    10. }
    11. // 以数组中心为基准点进行拆分
    12. let mid = Math.floor(len / 2);
    13. //  递归查分左侧
    14. let left = mergeSort(arr.slice(0, mid));
    15. //  递归拆分右侧
    16. let right = mergeSort(arr.slice(mid, len));
    17. //  合并并排序两个数组
    18. arr = sortArrFn(left, right);
    19. //   console.log("sortArr", arr);
    20. return arr;
    21. }
    22. /**
    23. * 合并排序两个数组
    24. * @param {*} arr1
    25. * @param {*} arr2
    26. */
    27. function sortArrFn(arr1, arr2) {
    28. //   arr1.sort(); // 此处不需要对数组排序，因为进入的最小元素的数组本身有序
    29. //   arr2.sort();
    30. let i = 0,
    31.   j = 0;
    32. let len1 = arr1.length,
    33.   len2 = arr2.length;
    34. let res = [];
    35. while (i < len1 && j < len2) {
    36.   if (arr1[i] <= arr2[j]) {
    37.     res.push(arr1[i]);
    38.     i++;
    39.   } else {
    40.     res.push(arr2[j]);
    41.     j++;
    42.   }
    43. }
    44. if (i < len1) {
    45.   return arr1.slice(i, len1);
    46. } else {
    47.   return res.concat(arr2.slice(j, len2));
    48. }
    49. }
    50. // console.log(sortArrFn([3, 1, 2], [5, 6, 4]));
    51. console.log(mergeSort([1, 3, 4, 5, 6, 2, 9, 2]));

    快速排序

    时间复杂度
    O(nlogn)
    思想
    将原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组