数组

数组概述

数组是 Java 中一种基本的数据结构，用于存储相同类型的多个元素。数组在内存中是连续存储的，可以通过索引访问每个元素。数组的长度在创建时确定，且不可更改。

一维数组的创建和使用

一维数组是最简单的数组，它只有一行，实质上是一组相同类型数据的线性集合。

创建一维数组

声明一维数组有两种语法形式：

数据类型[] 数组名;
数据类型 数组名[];

例如：

int[] arr;
int arr[];

在数组声明之后不能立即访问它的任何元素，因为此时只是定义了数组的名称和元素的数据类型，在使用数组之前，必须先为数组分配内存空间。数组作为对象可以使用 new 关键字分配内存空间。

语法：

数组名 = new 数据类型[数组长度];

例如：

int[] arr;  // 声明数组
arr = new int[3];  // 分配空间

数组还可以在声明的同时分配空间。如下：

int[] arr = new int[3];  // 声明数组并分配空间

在上方的代码中的数组类型为 int，所以在分配内存时，每个元素固定的默认值均为 0。

图 一维数组的内存模型

初始化一维数组

在创建数组时，可以直接初始化数组元素的值（即赋值）。初始化数组时，可以使用以下两种方式：

// 第一种方式
int[] arr = {1, 2, 3};

// 第二种方式
int[] arr = new int[]{1, 2, 3};

使用一维数组

可以通过索引访问数组元素，索引从 0 开始，最大索引为数组长度减 1。

int[] arr = {1, 2, 3};
int first = arr[0];  // 获取第一个元素，结果为 1
int last = arr[arr.length - 1];  // 获取最后一个元素，结果为 3

二维数组的创建和使用

二维数组的元素是一维数组，每个一维数组的元素是基本数据类型或引用数据类型。

创建二维数组

二维数组可以看作是一个数组的数组。创建二维数组的语法如下：

数据类型[][] 数组名;

例如：

int[][] matrix;

分配内存空间：

数组名 = new 数据类型[行数][列数];

例如：

matrix = new int[3][4];

图 二维数组的内存模型

初始化二维数组

初始化二维数组时，可以使用以下两种方式：

// 第一种方式
int[][] matrix = {{1, 2, 3}, {4, 5, 6}};

// 第二种方式
int[][] matrix = new int[][]{{1, 2, 3}, {4, 5, 6}};

使用二维数组

通过行和列的索引访问二维数组元素：

int[][] matrix = {{1, 2, 3}, {4, 5, 6}};
int first = matrix[0][0];  // 获取第一个元素，结果为 1
int last = matrix[1][2];  // 获取最后一个元素，结果为 6

数组的基本操作

Java 中提供了 Arrays 类来操作数组，包括数组的排序、查找、填充、复制等。

遍历数组

可以使用 for 循环或 foreach 循环遍历数组。

int[] arr = {1, 2, 3};

// 使用 for 循环遍历数组
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i]);
}

// 使用 foreach 循环遍历数组
for (int num : arr) {
    System.out.println(num);
}

填充替换数组元素

使用 Arrays.fill() 方法填充数组。

语法：

Arrays.fill(数组名, 填充值);

示例：

int[] arr = {1, 2, 3};

// 将数组 arr 的所有元素填充为 0
Arrays.fill(arr, 0);

对数组进行排序

使用 Arrays.sort() 方法对数组进行排序。

语法：

Arrays.sort(数组名);

示例：

int[] arr = {1, 3, 2, 5, 4};

// 对数组 arr 进行升序排序
Arrays.sort(arr);

复制数组

使用 Arrays.copyOf() 或 Arrays.copyOfRange() 方法复制数组。

• Arrays.copyOf(原数组, 新数组长度)。复制数组的所有元素。

  int[] arr = {1, 2, 3, 4, 5};
  int[] copyArr1 = Arrays.copyOf(arr, arr.length);

• Arrays.copyOfRange(原数组, 起始索引, 结束索引)。复制数组的部分元素，范围是 [start, end)。

  int[] arr = {1, 2, 3, 4, 5};
  int[] copyArr2 = Arrays.copyOfRange(arr, 0, 2); // 表示复制 arr 数组的前 2 个元素

数组查询

使用 Arrays.binarySearch() 方法在已排序的数组中进行二分查找。在查找前，需要先对数组进行排序。如果找到，返回元素的索引；如果未找到，返回负数。

语法：

Arrays.binarySearch(数组名, 查找值)。

示例：

int[] arr = {1, 3, 2, 5, 4};

// 对数组 arr 进行升序排序
Arrays.sort(arr);

// 在数组 arr 中查找值为 3 的元素
int index = Arrays.binarySearch(arr, 3);

数组排序算法

冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历数组，比较相邻的元素并交换它们的位置。

冒泡排序的基本思想是：

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
5. 最终，数组按升序排序。

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {63, 4, 24, 1, 3, 15};
        bubbleSort(arr);
        System.out.println("排序后的数组：" + Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换 arr[j] 和 arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

图 使用冒泡排序的过程

直接选择排序

直接选择排序每次从未排序部分选择最小的元素，放到已排序部分的末尾。

直接选择排序的基本思想是：

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 在剩余未排序序列中继续寻找最小（大）元素，放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {63, 4, 24, 1, 3, 15};
        selectionSort(arr);
        System.out.println("排序后的数组：" + Arrays.toString(arr));
    }

    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换 arr[i] 和 arr[minIndex]
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

图 使用直接选择排序的示意图

反转排序

反转排序是一种简单的排序算法，它将数组中的元素按照相反的顺序排列。

反转排序的基本思想是：

1. 从数组的两端开始，交换两个元素的位置。
2. 依次向中间移动，直到所有元素都被交换。
3. 最终，数组按照相反的顺序排列。

public class ReverseSort {
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50, 60};
        reverseSort(arr);
        System.out.println("排序后的数组：" + Arrays.toString(arr));
    }
    
    public static void reverseSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n / 2; i++) {
            // 交换 arr[i] 和 arr[n-i-1]
            int temp = arr[i];
            arr[i] = arr[n - i - 1];
            arr[n - i - 1] = temp;
        }
    }
}

图 使用反转排序的示意图