DSA 数组
数组
数组是用于存储多个元素的数据结构。
数组被许多算法使用。
例如,算法可以用来查找数组中的最小值,如下面的动画所示
速度
{{ msgDone }}最小值: {{ minVal }}
在 Python 中,数组的创建方式如下
my_array = [7, 12, 9, 4, 11]
注意:上面的 Python 代码实际上生成的是 Python 的 'list' 数据类型,但在此教程的范围内,'list' 数据类型可以像数组一样使用。在此 处 了解更多关于 Python 列表的信息。
数组是带索引的,这意味着数组中的每个元素都有一个索引,该索引指示元素在数组中的位置。本教程中的编程语言(Python、Java 和 C)对数组使用基于零的索引,这意味着数组中的第一个元素可以在索引 0 处访问。
在 Python 中,此代码使用索引 0 将第一个数组元素(值为 7)写入控制台
算法:查找数组中的最小值
让我们使用数组数据结构创建我们的第一个算法。
以下是查找数组中最小值的算法。
工作原理
- 逐一遍历数组中的值。
- 检查当前值是否是迄今为止的最小值,如果是,则存储它。
- 查看所有值后,存储的值将是数组中所有值中的最小值。
尝试下面的模拟,看看查找最小值算法是如何工作的(动画与本页顶部的动画相同)
速度
{{ msgDone }}最小值: {{ minVal }}
下一个模拟也查找数组中的最小值,就像上面的模拟一样,但在这里我们可以看到数组中的数字是如何被检查以找到最小值的
实现
在用实际编程语言实现算法之前,通常最好先将算法写成一个分步过程。
如果你能用介于人类语言和编程语言之间的语言写下算法,那么之后实现算法会更容易,因为我们避免了陷入所有编程语言语法的细节。
- 创建一个变量 'minVal' 并将其设置为数组的第一个值。
- 遍历数组中的每个元素。
- 如果当前元素的值低于 'minVal',则将 'minVal' 更新为此值。
- 遍历完数组中的所有元素后,'minVal' 变量现在包含最小值。
如果你愿意,也可以用更像编程语言的方式来写算法,例如
变量 'minVal' = array[0]
对于数组中的每个元素
如果当前元素 < minVal
minVal = 当前元素
注意:上面我们写的两个分步描述可以称为“伪代码”。伪代码是用一种介于人类语言和编程语言之间的语言描述程序的功能。
写下算法后,用特定编程语言实现算法就容易多了
示例
Python
my_array = [7, 12, 9, 4, 11]
minVal = my_array[0] # Step 1
for i in my_array: # Step 2
if i < minVal: # Step 3
minVal = i
print('Lowest value: ',minVal) # Step 4
运行示例 »
算法时间复杂度

在探索算法时,我们通常会查看算法相对于数据集的大小需要多长时间来运行。
在上面的例子中,算法运行所需的时间与数据集的大小成正比,即线性关系。这是因为算法必须访问每个数组元素一次才能找到最小值。循环必须运行 5 次,因为数组中有 5 个值。如果数组有 1000 个值,循环就必须运行 1000 次。
尝试下面的模拟,看看查找最小值所需的比较操作次数与数组大小之间的关系。
有关时间复杂度的更详细解释,请参阅 此页面。
本教程中的每个算法都将连同其时间复杂度一起呈现。
{{ this.userX }}
操作次数:{{ operations }}