对象允许存储键值化的集合,这很好。

但很多时候我们需要的是有序集合,里面的元素都是按顺序排列的。例如,我们可能需要存储一些列表,比如用户、商品以及 HTML 元素等。

这里使用对象就不是很方便了,因为对象不提供能够管理元素顺序的方法。我们不能在已有的元素“之间”插入一个新的属性。这种场景下对象就不太适用了。

这时一个特殊的数据结构数组(Array)就派上用场了,它能存储有序的集合。

声明

创建一个空数组有两种语法:

let arr = new Array();
let arr = [];

绝大多数情况下使用的都是第二种语法。我们可以在方括号中添加初始元素:

let fruits = ["Apple", "Orange", "Plum"];

数组元素从 0 开始编号。

我们可以将元素的索引值填写在方括号内来获取元素:

let fruits = ["Apple", "Orange", "Plum"];

alert( fruits[0] ); // Apple
alert( fruits[1] ); // Orange
alert( fruits[2] ); // Plum

可以替换元素:

fruits[2] = 'Pear'; // 现在变成 ["Apple", "Orange", "Pear"]

…或者新加一个元素:

fruits[3] = 'Lemon'; // 现在变成 ["Apple", "Orange", "Pear", "Lemon"]

length 属性的值是数组中元素的总个数

let fruits = ["Apple", "Orange", "Plum"];

alert( fruits.length ); // 3

也可以用 alert 来显示整个数组。

let fruits = ["Apple", "Orange", "Plum"];

alert( fruits ); // Apple,Orange,Plum

数组可以存储任何类型的元素。

例如:

// 混合值
let arr = [ 'Apple', { name: 'John' }, true, function() { alert('hello'); } ];

// 获取索引为 1 的对象然后显示它的 name
alert( arr[1].name ); // John

// 获取索引为 3 的函数并执行
arr[3](); // hello
以逗号结尾

数组和对象一样,都可以在末尾冗余一个逗号:

let fruits = [
  "Apple",
  "Orange",
  "Plum",
];

因为每一行都是相似的,所以这种以“逗号结尾”的方式使得插入/移除项变得更加简单。

pop/push, shift/unshift 方法

队列是最常见的使用数组的方法之一. 在计算机科学中,这意味着一个有序的元素的集合支持两个操作:

  • push 在末端添加一个元素.
  • shift 取出队列最前端的一个元素,整个队列往前移,这样原先排第二的元素现在排在了第一。

这两种操作数组都支持.

队列的应用在实践中经常会碰到,例如需要在屏幕上显示消息队列。

数组还有另一个用例,就是数据结构

它支持两种操作:

  • push 在末端添加一个元素.
  • pop 从末端取出一个元素.

所以新元素的添加和取出都是从“末端”开始的。

栈通常被被形容成一叠卡片:要么添加卡片放到最上面,要么从最上面拿走卡片:

对于栈来说,最后放进去的是最先接收的,也叫做 LIFO(后进先出)法则。而与队列相对应的叫做 FIFO(先进先出)。

JavaScript 中的数组既可以用作队列,也可以用作栈。它们允许从前端/末端来添加/删除元素。

这在计算机科学中叫做双端队列

作用于数组末端的方法:

pop

取出并返回数组的最后一个元素:

let fruits = ["Apple", "Orange", "Pear"];

alert( fruits.pop() ); // 移除 "Pear" 然后 alert 显示出来

alert( fruits ); // Apple, Orange
push

在数组末端添加元素:

let fruits = ["Apple", "Orange"];

fruits.push("Pear");

alert( fruits ); // Apple, Orange, Pear

调用 fruits.push(...)fruits[fruits.length] = ... 是一样的。

作用于数组前端的方法:

shift

取出数组的第一个元素并返回它:

let fruits = ["Apple", "Orange", "Pear"];

alert( fruits.shift() ); // 移除 Apple 然后 alert 显示出来

alert( fruits ); // Orange, Pear
unshift

在数组的前端添加元素:

let fruits = ["Orange", "Pear"];

fruits.unshift('Apple');

alert( fruits ); // Apple, Orange, Pear

pushunshift 可以一次添加多个元素:

let fruits = ["Apple"];

fruits.push("Orange", "Peach");
fruits.unshift("Pineapple", "Lemon");

// ["Pineapple", "Lemon", "Apple", "Orange", "Peach"]
alert( fruits );

内部

数组是一种特殊的对象。使用方括号来访问属性 arr[0] 实际上是来自于对象的语法。这个数字被用作键值。

他们扩展了对象,提供了特殊的方法来处理有序的数据集合,还添加了 length 属性。但是核心还是一个对象。

记住,在 JavaScript 中只有 7 种基本类型。数组是一个对象因此其行为也像一个对象。

例如,它是通过引用来复制的:

let fruits = ["Banana"]

let arr = fruits; // 通过引用复制 (两个变量引用的是相同的数组)

alert( arr === fruits ); // true

arr.push("Pear"); // 通过引用修改数组

alert( fruits ); // Banana, Pear — 现在有 2 项了

…但是数组真正特殊的是它们的内部实现。JavaScript 引擎尝试把这些元素一个接一个地存储在连续的内存区域,就像本章的插图显示的一样,而且还有一些其它的优化,以使数组运行得非常快。

但是如果我们放弃以“有序集合”的方式使用数组,而是像一个常规对象一样使用它,这些就都不生效了。

例如可以这样做:

let fruits = []; // 创建一个数组

fruits[99999] = 5; // 用一个远大于数组长度的索引分配属性

fruits.age = 25; // 用任意的名字创建属性

这是可能的,因为数组是基于对象的。我们可以给它们添加任何属性。

但是 Javascript 引擎会发现我们在像使用常规对象一样使用数组,那么针对数组的优化就不再适用了,而且还会被关闭,这些优化所带来的优势也就荡然无存了。

数组误用的几种方式:

  • 添加一个非数字的属性比如 arr.test = 5
  • 制造空洞,比如:添加 arr[0] 后添加 arr[1000] (它们中间什么都没有)。
  • 以倒序填充数组, 比如 arr[1000]arr[999] 等等。

请将数组视为作用于有序数据的特殊结构,它们为此提供了特殊的方法。数组在 JavaScript 引擎内部是经过特殊调整的,使得更好的作用于连续的有序数据,所以请以这种方式使用数组。如果你需要任意键值,那很有可能实际上你需要的是常规对象 {}

性能

push/pop 方法运行的比较快,而 shift/unshift 比较慢。

为什么作用于数组的末端会比前端快呢?让我们看看在执行期间都发生了什么:

fruits.shift(); // 从前端取出一个元素

只获取并移除数字 0 对应的元素是不够的。其它元素也需要被重新编号。

shift 操作必须做三件事:

  1. 移除索引为 0 的元素。
  2. 把所有的元素向左移动,将索引从 1 改成 02 改成 1 以此类推,对其重新编号。
  3. 更新 length 属性。

数组里的元素越多,移动它们就要花越多的时间,也就意味着越多的内存操作。

unshift 也是一样:为了在数组的前端添加元素,我们首先需要将现有的元素向右移动,增加它们的索引值。

push/pop 是什么样的呢?它们不需要移动任何东西。如果从末端移除一个元素,pop 方法只需要清理索引值和缩短 length 就可以了。

pop 操作的动作:

fruits.pop(); // 从末端取走一个元素

pop 方法不需要移动任何东西,因为其它元素都保留了各自的索引。这就是为什么 pop 会特别快。

push 方法也是一样的。

循环

遍历数组最古老的方式就是 for 循环

let arr = ["Apple", "Orange", "Pear"];

for (let i = 0; i < arr.length; i++) {
  alert( arr[i] );
}

但对于数组来说还有另一种循环方式,for..of

let fruits = ["Apple", "Orange", "Plum"];

// 迭代数组元素
for (let fruit of fruits) {
  alert( fruit );
}

for..of 不能获取当前元素的索引,但大多数情况是够用的。而且这样写更短。

技术上来讲,因为数组也是对象,所以使用 for..in 也是可能的:

let arr = ["Apple", "Orange", "Pear"];

for (let key in arr) {
  alert( arr[key] ); // Apple, Orange, Pear
}

但这其实不是个好想法。会有一些潜在问题存在:

  1. for..in 循环会迭代所有属性,不仅仅是这些数字属性。

    在浏览器和其它环境中有一种“类数组”的对象,它们看似是数组,也就是说,它们有 length 和索引属性,但是也可能有其它的非数字的属性和方法,这通常是我们不需要的。for..in 循环会把它们都列出来。所以如果我们需要处理类数组对象,这些“额外”的属性就会存在问题。

  2. for..in 循环适用于普通对象,不适用于数组,而且会慢 10-100 倍。当然即使是这样也依然非常快。只有在遇到瓶颈或者一些不相关的场景增速可能会有问题。但是我们仍然应该了解这其中的不同。

通常来说,我们不应该用 for..in 来处理数组。

关于 “length”

当我们修改数组的时候,length 属性会自动更新。准确来说,它实际上不是数组里元素的个数,而是最大的数字索引值加一。

例如,一个数组只有一个元素,但是这个元素的索引值很大,那么这个数组的 length 也会很大:

let fruits = [];
fruits[123] = "Apple";

alert( fruits.length ); // 124

要知道的是我们通常不会这样使用数组。

length 属性的另一个有意思的点是它是可写的。

如果我们手动增加长度,一切正常。但是如果我们减少长度,数组就会变短。这种处理是不可逆的,下面是一个例子:

let arr = [1, 2, 3, 4, 5];

arr.length = 2; // 只剩 2 个元素
alert( arr ); // [1, 2]

arr.length = 5; // 又把 length 加回来
alert( arr[3] ); // undefined: 被截断的那些数值并没有回来

所以,清空数组最好的方法就是:arr.length = 0;

new Array()

创建数组还有另一种语法:

let arr = new Array("Apple", "Pear", "etc");

它很少被使用,因为方括号 [] 更短更简洁。而且这种语法还存在一些诡异的特性。

如果调用 new Array 使用的是一个单独的数字作为参数,那么就会创建一个指定了长度,却没有任何项的数组。

让我们看看如何搬起石头砸自己的脚:

let arr = new Array(2); // 会创建一个数组 [2] 吗?

alert( arr[0] ); // undefined!没有元素.

alert( arr.length ); // length 2

在上面的代码中,new Array(number) 所有的元素都是 undefined

为了避免这种乌龙事件,我们通常都是使用方括号的,除非我们清楚地知道自己正在做什么。

多维数组

数组里的项也可以是数组。我们可以以多维数组的方式存储矩阵:

let matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

alert( matrix[1][1] ); // 最中间的那个数

toString

数组有自己的 toString 方法的实现,会返回以逗号隔开的元素列表。

例如:

let arr = [1, 2, 3];

alert( arr ); // 1,2,3
alert( String(arr) === '1,2,3' ); // true

或者尝试一下这个:

alert( [] + 1 ); // "1"
alert( [1] + 1 ); // "11"
alert( [1,2] + 1 ); // "1,21"

数组没有 Symbol.toPrimitive,也没有 valueOf,它们只能执行 toString 进行转换,所以这里 [] 就变成了一个空字符串,[1] 变成了 "1" 然后 [1,2] 变成了 "1,2"

"+" 操作符把一些项加到字符串后面时,加号后面的项也会被转换成字符串,所以下一步就会是这样:

alert( "" + 1 ); // "1"
alert( "1" + 1 ); // "11"
alert( "1,2" + 1 ); // "1,21"

总结

数组是一种特殊的对象,适用于存储和管理有序的数据项。

  • 声明:

    // 方括号 (常见用法)
    let arr = [item1, item2...];
    
    // new Array (极其少见)
    let arr = new Array(item1, item2...);

    调用 new Array(number) 会创建一个指定长度的数组,且不含有任何项。

  • length 属性是数组的长度,准确地说,是它的最后一个数字索引值加一。它由数组方法自动调整。

  • 如果我们手动缩短 length,那么数组就会被截断。

我们可以通过下列操作以双端队列的方式使用数组:

  • push(...items) 在末端添加项 items
  • pop() 从末端移除并返回该元素。
  • shift() 从前端移除并返回该元素。
  • unshift(...items) 从前端添加项 items

遍历数组的元素:

  • for (let i=0; i<arr.length; i++) — 运行的最快, 可兼容旧版本浏览器。
  • for (let item of arr) — 现代语法,只能访问 items。
  • for (let i in arr) — 永远不会使用。

在下一章节我们会回顾数组然后学习更多添加、移动、提取元素和数组排序的方法。 数组方法

任务

重要程度: 3

下面的代码将会显示什么?

let fruits = ["Apples", "Pear", "Orange"];

// 在“副本”里 push 了一个新的值
let shoppingCart = fruits;
shoppingCart.push("Banana");

// fruits 里面是什么?
alert( fruits.length ); // ?

结果是 4:

let fruits = ["Apples", "Pear", "Orange"];

let shoppingCart = fruits;

shoppingCart.push("Banana");

alert( fruits.length ); // 4

这是因为数组是对象。所以 shoppingCartfruits 是同一数组的引用。

重要程度: 5

我们试试下面的 5 个数组操作。

  1. 创建一个数组 styles,里面有两项 “Jazz” 和 “Blues”.
  2. 将 “Rock-n-Roll” 从数组末端添加进去.
  3. 用 “Classics” 替换掉数组最中间的元素。你的查找数组最中间的元素的代码应该适用于任何奇数长度的数组。
  4. 去掉数组的第一个值并显示它。
  5. 在数组前面添加 RapReggae

处理中的数组:

Jazz, Blues
Jazz, Bues, Rock-n-Roll
Jazz, Classics, Rock-n-Roll
Classics, Rock-n-Roll
Rap, Reggae, Classics, Rock-n-Roll
let styles = ["Jazz", "Blues"];
styles.push("Rock-n-Roll");
styles[Math.floor((styles.length - 1) / 2)] = "Classics";
alert( styles.shift() );
styles.unshift("Rap", "Reggie");
重要程度: 5

结果是什么?为什么?

let arr = ["a", "b"];

arr.push(function() {
  alert( this );
})

arr[2](); // ?

arr[2]() 调用从句法来看可以类比于 obj[method](),与 obj 对应的是 arr,与 method 对应的是 2

所以调用 arr[2] 函数也就是调用对象函数。自然地,它接收 this 引用的对象 arr 然后输出该数组:

let arr = ["a", "b"];

arr.push(function() {
  alert( this );
})

arr[2](); // "a","b",function

该数组有3项:最开始有两个,后来添加进来一个函数。

重要程度: 4

写出函数 sumInput(),要求如下:

  • 使用 prompt 向用户索要值,并存在数组中。
  • 当用户输入了非数字、空字符串或者点击“取消”按钮的时候,问询结束。
  • 计算并返回数组所有项之和。

P.S. 0 是有效的数字,不要因为是 0 就停止问询。

运行 demo

请注意一些微妙的但是很重要的处理细节。我们没有在 prompt 输入后立即把 value 转换成数字,因为在执行 value = +value 之后,就没办法区分出空字符串(中断标志)和数字 0(合法输入)了,所以要放到后面再处理。

function sumInput() {

  let numbers = [];

  while (true) {

    let value = prompt("A number please?", 0);

    // 应该结束吗?
    if (value === "" || value === null || !isFinite(value)) break;

    numbers.push(+value);
  }

  let sum = 0;
  for (let number of numbers) {
    sum += number;
  }
  return sum;
}

alert( sumInput() );
重要程度: 2

输入是以数字组成的数组,例如 arr = [1, -2, 3, 4, -9, 6].

任务是:找出连续的 arr 的子数组,其里面所有项的和最大。

写出函数 getMaxSubSum(arr),用其找出并返回最大和。

例如:

getMaxSubSum([-1, 2, 3, -9]) = 5 (高亮项的加和)
getMaxSubSum([2, -1, 2, 3, -9]) = 6
getMaxSubSum([-1, 2, 3, -9, 11]) = 11
getMaxSubSum([-2, -1, 1, 2]) = 3
getMaxSubSum([100, -9, 2, -3, 5]) = 100
getMaxSubSum([1, 2, 3]) = 6 (所有项的和)

如果所有项都是负数,那就一个项也不取(数组是空的),所以返回的是 0:

getMaxSubSum([-1, -2, -3]) = 0

请尝试想出一个快速的解决方案:复杂度可以是 O(n2),有能力达到 O(n) 则更好。

打开带有测试的沙箱。

慢的解决方案

我们可以计算所有可能的子集的和。

最简单的方法就是获取每个元素然后计算从它开始所有子数组的和。

[-1, 2, 3, -9, 11] 为例:

// 从 -1 开始:
-1
-1 + 2
-1 + 2 + 3
-1 + 2 + 3 + (-9)
-1 + 2 + 3 + (-9) + 11

// 从 2 开始:
2
2 + 3
2 + 3 + (-9)
2 + 3 + (-9) + 11

// 从 3 开始:
3
3 + (-9)
3 + (-9) + 11

// 从 -9 开始:
-9
-9 + 11

// 从 -11 开始:
-11

这样写出来的代码实际上是一个嵌套循环:外部循环遍历数组所有元素,然后内部循环计算从当前元素之后的所有子数组集的和。

function getMaxSubSum(arr) {
  let maxSum = 0; // 如果没有取到任何元素,就返回 0

  for (let i = 0; i < arr.length; i++) {
    let sumFixedStart = 0;
    for (let j = i; j < arr.length; j++) {
      sumFixedStart += arr[j];
      maxSum = Math.max(maxSum, sumFixedStart);
    }
  }

  return maxSum;
}

alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100

该方案的时间复杂度是 O(n2)。也就是说,如果我们把数组大小增加 2 倍,那么算法的运行时间将会延长4倍。

对于大型数组(1000,10000 或者更多项)这种算法会导致严重的时间消耗。

快的解决方案

让我们遍历数组,将当前局部元素的和保存为变量 s。如果 s 在某一点变成负数了,就重新分配 s=0。所有 s 中的最大值就是答案。

如果文字描述不太好理解,就直接看下面的代码吧,真的很短:

function getMaxSubSum(arr) {
  let maxSum = 0;
  let partialSum = 0;

  for (let item of arr) { // arr 中的每个 item
    partialSum += item; // 将其添加到 partialSum
    maxSum = Math.max(maxSum, partialSum); // 记住最大值
    if (partialSum < 0) partialSum = 0; // 如果是负数就置为 0
  }

  return maxSum;
}

alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([-1, -2, -3]) ); // 0

该算法只需要遍历1轮数组,所以时间复杂度是 O(n)。

你也可以在此获取更多该算法的细节信息:Maximum subarray problem。如果还是不明白,那就调试上面的例子,观察它是怎样工作的,说得再多也没有自己去调试好使。

使用沙箱的测试功能打开解决方案。

教程路线图

评论

在评论之前先阅读本内容…
  • 欢迎你在文章下添加补充内容、提出你的问题或回答提出的问题。
  • 使用 <code> 标签插入几行代码,对于多行代码 — 可以使用 <pre>,对于超过十行的代码 — 建议使用沙箱(plnkrJSBincodepen 等)。
  • 如果你无法理解文章中的内容 — 请详细说明。