JavaSE - Note06 Array & Algorithm

Array

数组实际上是一个容器，一个数据的集合，可以容纳多个元素

Java 语言中的数组是一种引用数据类型，不属于基本数据类型

数组中可以存储基本数据类型的数据，也可以存储引用数据类型的数据

因为是引用类型，所以数组存储在堆内存中

数组中如果存储 Java 对象，实际上则是存储 Java 内存地址

数组一旦创建，在 Java 中长度不可变

数组的分类：一维数组、二维数组、三维数组…

所有的数组对象都有 length 属性（Java 自带，并非方法），用来获取数组中元素的个数

Java 数组要求数组中元素统一，比如 int 类型数组只放 int 类型数据

数组中首元素的内存地址作为数组对象的地址

数组中每一个元素都有下标，第一个元素为0，最后一个为 n-1

优缺点

优点

查询/查找/检索某个下标上的元素时效率极高，可以说是查询效率最高的一种数据结构

1. 数组在内存方面存储时，数组中的元素内存地址是连续的
2. 每一个元素类型相同，所占用空间大小一样
3. 知道第一个元素内存地址，知道每一个元素占用空间的大小，又知道下标，所以通过一个数学表达式就可以计算出下标元素上的内存地址，直接通过内存地址定位元素

缺点

1. 由于为了保证数组中每个元素内存地址连续，所以在数组上随机删除或增加元素的时候效率较低随机增删元素会涉及到后面元素统一向前或向后位移的操作
2. 数组不能存储大数据，很难在内存空间上找到一块特别大的连续的内存空间

最后一个元素的增删没有影响

语法格式

int[] array1;

初始化

静态初始化

int[] array = {100, 200, 300};

静态数组直接传递：

new int[] {1, 2, 3}

其中，中括号中不能有数字

动态初始化

int[] array = new int[5];

这里的 5 表示数组的元素个数，初始化 5 个长度为 int 类型数组，每个元素默认值为 0

String[] array = new String[6];

初始化 6 个长度的 String 类型数组，每个元素默认值为 null

创建数组时，确定存储哪些具体元素，采用静态初始化方式

创建数组时，不确定存储哪些数据，采用动态初始化方式，后期赋值

main 方法

public static void main(String[] args) {}

其中 main(String[] args) JVM调用 main 方法时，会自动传入一个 String 数组

这个数组是留给用户的，用户可以在控制台上输入参数，这个参数会被自动转换为 “String args” 数组

例如这样运行程序：

• cmd 窗口

  java ArrayTest05 abc def xyz

• IDEA

  菜单栏 -> run -> Edit Configuration -> Program arguments

JVM 会自动将 abc def xyz 通过空格的方式进行分离，然后放到 “String[] args” 数组

一维数组深入

数组存储引用数据类型

父类数组可以存放子类引用，若要调用子类特有方法，需要向下转型

数组扩容

Java 开发中，数组长度一旦确定即不可变，需要扩容

扩容思路

先新建一个大容量数组，然后将小容量数组中的数据一个一个拷贝到大数组中

涉及到拷贝问题，数组扩容效率较低，以后的开发尽可能预估准确，少的进行扩容

扩容语法

arraycopy(Object array1, int start1, Object array2, int start2, int length);

Object array1：拷贝源数组

int start1：拷贝源数组开始下标

Object array2：拷贝目标数组

int start2：目标数组开始下标

int length：拷贝长度

示例代码：

int[] a1 = {1, 2, 3};
int[] a2 = new int[5];
System.arraycopy(a1, 0, a2, 0, a1.length);

二维数组

二维数组其实就是一个特殊的一维数组，特殊在这个一维数组当中的每个元素是一个一维数组

实际开发中最多就是一维数组，二维数组很少使用，三维数组几乎不用

声明语法

静态初始化

int[][] array = {{1, 2}, {3, 4}}

动态初始化

int[][] array = new int[2][2]

访问二维数组

a[二维数组中一维数组下标][一维数组中元素下标]

二维数组的遍历

// 控制二维数组中一维数组下标
for (int m = 0; m < array.length; m++) {
    // 控制一维数组中元素下标
	for (int n = 0; n < array[m].length; n++) {
        // 打印第 m 个数组中的所有元素
		System.out.print(array[m][n] + " ");
	}
    // 换行
    System.out.println();
}

常见算法

Java 中封装了很多算法，例如：数组工具类 java.util.Arrays

其中有一个 sort() 方法，可以实现排序

排序算法

冒泡排序

水中同一维度的气泡，体积越大，上升到水面的速度越快

1. 每一次循环结束之后，找出最大的数据，放到参与比较这堆数据的最右边（冒出最大的气泡）
2. 用左边的数字与右边比对，当左边>右边的时候，交换位置

实现过程

原始数据：
9，8，7，6

第一次循环（最大的换到右边）
8，9，7，6（9和8比较，9>8交换位置）
8，7，9，6（9和7比较，9>7交换位置）
8，7，6，9（9和6比较，9>6交换位置）

第二次循环（剩余8，7，6）
7，8，6（8和7比较，8>7交换位置）
7，6，8（8和6比较，8>6交换位置）

第三次循环（剩余7，6）
6，7（7和6比较，7>6交换位置）

排序后位置：
6，7，8，9

核心代码

for (int i = a.length - 1; i > 0; i--) {
    for (int j = 0; j < i; j++) {
        if (a[j] > a[j+1]) {
            temp = a[j];
            a[j] = a[j+1];
            a[j + 1] = temp;
        }
    }
}

选择排序

每一次从这堆参与比较的数据中找出最小值，用这个最小值与前面元素交换位置

选择排序的好处是，每一次的交换都有意义

实现过程

原始数据：
4，5，3，6

第一次循环（最小的换到左边）
4，5，3，6（4和5比较，4<5位置不变）
3，5，4，6（4和3比较，4>3位置交换）
3，5，4，6（3和6比较，3<6位置不变）

第二次循环（剩余5，4，6）
4，5，6（5和4比较，5>4位置交换）
4，5，6（4和6比较，4<6位置不变）

第三次循环（剩余5，6）
5，6（5和6比较，5<6位置不变）

排序后：
3，4，5，6

核心代码

for (int i = 0; i < a.length - 1; i++) {
	for (int j = i + 1; j < a.length; j++) {
		if (a[j] < a[i]) {
            temp = a[j];
            a[j] = a[i];
            a[i] = temp;
		}
	}
}

查找算法

最简单的就是一个一个挨着找，直到找到为止

二分法查找

基于排序基础之上，没有排序的数据无法查找

实现过程

arr：10（下标0），11，12，13，14，15，16，17，18，19，20（下标10） 查找18

1. 找出中间元素的下标：

   （0 + 10） / 2 = 5

2. 将中间元素和目标元素进行对比：

   中间元素：arr[5] = 15 < 18（被查找的元素），且在中间元素右边

3. 重新计算中间元素下标：

   开始下标：5 + 1

   结束下标：10

   找出中间元素的下标：（6+10） / 2 = 8

4. arr[8]对应是18，完成

示例代码

while (min <= max) {
    mid = (min+max) / 2;
    if (a[mid] == e) {
        return mid;
    }
    else if (a[mid] < e) {
        min = mid + 1;
    }
    else {
        max = mid - 1;
    }
}
return -1;

Arrays 工具类

Java内置 java.util.Arrays 工具类，提供数组处理的常用算法

排序：Arrays.sort(array)

二分法查找：Arrays.binarySearch(array, key)