什么是数组

数组是一种数据结构，其中值或项以线性顺序排列，这意味着分配给每个项的内存是连续的。数组中所有元素的`数据类型`都是相同的。

由于内存是连续分配的，因此通过知道第一个内存位置并加上偏移量，就可以轻松地找出数组中任何元素的内存位置。

例如

在上面的示例中，我们有一个整数数组，内存位置是连续的，每个整数占用 4 个字节，起始地址为 4000。

一旦声明了数组，我们就无法动态地增加或减少其大小。在大多数编程语言中，内存分配是静态的，因此我们必须在声明数组时指定其大小。

数组中的索引

我们可以通过数组中的索引号来识别和访问每个值。

例如，在零基索引中，`arr[1]` 将用于访问数组的第二个元素。

数组索引可以有以下类型：

零基索引

如果数组的第一个值索引为 0，则称为零基索引。大多数编程语言都遵循零基索引。

一基索引

如果数组索引从 1 开始，则称为一基索引。这意味着数组的第一个值将被分配索引 1。

N基索引

当第一个元素的索引可以是任何值，甚至可以是负值时，则称为 N 基索引。

数组中的初始化方法

在 Java 中，有多种方法可以声明和初始化数组。

1. 使用 'new' 关键字

借助 `new` 关键字，我们可以为数组分配特定大小的内存。在 Java 中，当我们使用 `new` 关键字时，它会在堆中分配内存，因此它会静态地分配内存。

例如

在上面的代码中，我们声明了一个大小为 12 的整数类型数组。我们使用 `new` 关键字分配了可以存储 12 个整数的内存。

2. 通过直接赋值

初始化和声明数组的另一种方法是直接在数组中插入值，而无需使用 `new` 关键字和指定数组大小。

例如

在上面的示例中，我们同时声明了数组并对其进行了初始化。

数组上的各种操作

1. 插入操作

如果数组中有任何值，我们可以将其插入到数组的任何索引处，但新值必须具有相同的数据类型。

示例

输出

old array is : 1 2 3 4 5 6
new array is : 1 2 98 4 5 6

说明

在上面的代码中，我们使用一些值声明了一个整数数据类型的数组。现在，我们在索引二处插入了一个新值 98，并更改了数组。

时间复杂度：O(1) 或常数时间复杂度。

2. 访问任何元素

要访问数组中的任何元素，只需使用其索引号即可访问。

示例

输出

4th element in the array is 4

说明

在上面的代码中，我们声明并初始化了一个数组，然后使用索引号 3（零基索引）访问了数组的第四个值。

时间复杂度： O(1)

3. 搜索元素

我们可以搜索数组中的任何元素。它可能存在于数组中，也可能不存在。我们可以使用线性搜索或二分搜索进行搜索操作。

示例

输出

we found the target value

说明

在上面的代码中，我们有一个数组和一个目标值。我们将一个循环应用于数组并搜索目标元素。由于我们在数组中找到了目标值，因此我们退出了循环并打印了语句。

时间复杂度

O(N)，其中 N 是数组中的元素数量。

在排序数组中，我们也可以使用二分搜索方法来降低时间复杂度。

二分搜索的时间复杂度：O(logN)

二分搜索示例

输出

target is not present

说明

在上面的代码中，我们使用二分搜索方法在数组中搜索目标元素。

• 首先，它将获得 lo 和 high 范围内的 mid 索引。然后，如果目标值存在于 mid 索引处，我们将停止。
• 如果目标值小于 mid 的值，我们将通过将 high 赋值为 mid-1 来丢弃右半部分。
• 否则，我们将移动到数组的右半部分，并通过将 lo 赋值为 mid+1 来丢弃左半部分。
• 因此，在每次迭代中，我们都将搜索空间除以 2，因此上述代码的实际时间复杂度将是 O(log n)，其中 n 代表数组中的元素数量。

4. 排序数组

排序基本上是指以特定顺序（升序或降序）排列或重新排序数组的元素。数组中有许多排序技术，例如冒泡排序、插入排序、归并排序、选择排序、基数排序、堆排序等。

示例

输出

array before sorting is: 5 3 7 8 4 6 1
array after sorting is: 1 3 4 5 6 7 8

说明

在上面的代码中，我们使用冒泡排序方法以升序对给定数组进行排序。我们有一个未排序的整数数组。我们比较了每个相邻的值，如果它们不按正确的顺序排列，就交换了它们。

时间复杂度：O(n²)

O(n²) 时间复杂度：冒泡排序、选择排序、插入排序

o(nlogn) 时间复杂度：归并排序、快速排序等。

数组的类型

根据维度，数组可以有多种类型，因此我们主要将其分为两类：

1. 一维数组

当数组的元素以线性方式排列时，称为一维数组。这是我们在问题中通常使用的一种基本数组。

2. 多维数组

当数组有多个维度时，称为多维数组。它可以是二维、三维或更多维的。

示例

输出

2D array is :
1 2 3
4 5 6
7 8 9

说明

在上面的代码中，我们创建了一个整数数据类型的二维数组。

数组的优点

• 数组在程序中性能非常好，因为它们具有非常好的缓存局部性。
• 我们可以用一个变量名表示相同数据类型的多个值，这使得代码更容易理解。
• 我们可以使用索引值随机访问数组中的任何元素，这使得对数组的操作非常容易。

数组的缺点

• 插入或删除操作可能成本很高，因为数组的大小是固定的，并且内存分配在数组中是静态的。
• 因此，如果我们想要一个插入和删除方便的数据结构，我们可以使用基于 LIFO 原理的栈数据结构。

数组的应用

• 我们可以将数组用于 CPU 调度算法。
• 可以使用数组数据结构来实现排序算法。
• 数组用于解决与矩阵相关的复杂问题。
• 数据库记录使用数组数据结构进行排列。
• 其他数据结构，如队列、栈、哈希映射等，都是通过数组实现的。
• 多个变量使用同一个名称。
• 它可以存储具有相同数据类型的元素。