保持对世界的渴望与好奇，而非被浅薄的快乐左右
数组的概述
概述：数组是一种数据结构，用来存储同一类型值的集合。通过一个整形下标（index，或称索引）可以访问数组中的每一个值。
特点：
- 数组是有序排列的
- 数组长度一旦确定，不能修改
- 创建数组对象会在内存中开辟一整块连续的空间
- 数组属于引用类型的变量。数组的元素，既可以是基本数据类型，也可以是引用数据类型
分类：
- 按照维度：一维数组、二维数组、…
- 按照数组元素的类型：基本数据类型元素的数组、引用数据类型元素的数组
数据结构：
- 数据与数据之间的逻辑关系：集合（关系很弱）、一对一（数组里面的元素）、一对多（二叉树）、多对多（社交网络）
- 数据的存储结构：
- 线性表：顺序表（比如：数组）、链表、栈、队列、
- 树形结构：二叉树、树形结构
数组的声明
Java 虚拟机的内存划分
为了提高运算效率，就对空间进行了不同区域的划分，因为每一片区域都有特定的处理数据方式和内存管理方式。
| 区域名称 | 作用 |
|---|
虚拟机栈 | 用于存储正在执行的每个Java方法的局部变量表等。局部变量表存放了编译期可知长度
的各种基本数据类型、对象引用，方法执行完，自动释放。 |
堆内存 | 存储对象（包括数组对象），new来创建的，都存储在堆内存。 |
方法区 | 存储已被虚拟机加载的类信息、常量、（静态变量）、即时编译器编译后的代码等数据。 |
| 本地方法栈 | 当程序中调用了native的本地方法时，本地方法执行期间的内存区域 |
| 程序计数器 | 程序计数器是CPU中的寄存器，它包含每一个线程下一条要执行的指令的地址 |
注：摘自康师傅 Java 课件与电子教材
一维数组
在声明数组变量时，需要指定数组类型（数据元素类型紧跟 [] ）和数组变量的名称
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
int[] a;
a = new int[]{1001, 1002, 1003, 1004};
String[] names = new String[5];
int[] smallPrimes = {2, 3, 4, 5, 6};
int[] b;
int c[];
|
错误的方式
数组元素调用、获取数组 length、两种方式遍历数组元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public class ArrayTest1 {
public static void main(String[] args) {
String[] names = new String[5];
names[0] = "张三";
names[1] = "李四";
names[2] = "王五";
names[3] = "赵六";
names[4] = "孙七";
System.out.println(names.length);
for (int i = 0; i < names.length; i++) {
System.out.print(names[i] + " ");
}
System.out.println();
for (String element : names) {
System.out.print(element + " ");
}
}
}
|
默认初始化值
- 数组元素是整型：0
- 数组元素是浮点型：0.0
- 数组元素是char型：0或’\u0000’，而非’0’
- 数组元素是boolean型：false
- 数组元素是引用数据类型：null
一维数组内存解析大致过程
二维数组
二维数组元素获取、获取数组 length、两种方式遍历数组元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| public class ArrayTest2 {
public static void main(String[] args) {
int[][] arr1 = new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {22, 12, 9}};
String[][] arr2 = new String[3][2];
String[][] arr3 = new String[3][];
int arr4[][] = new int[][]{{1, 2, 3}, {4, 5, 9, 10}, {6, 7, 8}};
int[] arr5[] = new int[][]{{1, 2, 3}, {4, 5, 9, 10}, {6, 7, 8}};
int[][] arr6 = {{1, 2, 3}, {4, 5}, {6, 7, 8}};
System.out.println(arr1[0][2]);
System.out.println(arr2[1][1]);
System.out.println(arr1.length);
System.out.println(arr1[1].length);
for (int i = 0; i < arr1.length; i++) {
for (int j = 0; j < arr1[i].length; j++) {
System.out.print(arr1[i][j] + " ");
}
System.out.println();
}
System.out.println();
for (int[] e : arr1) {
for (int j : e) {
System.out.print(j + " ");
}
System.out.println();
}
}
}
|
错误的方式
数组元素的默认初始化值
二维数组内存解析大致过程
数组的常见算法
数组元素的赋值
杨辉三角
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| public class ArrayEver {
public static void main(String[] args) {
int[][] yangHui = new int[10][];
for (int i = 0; i < yangHui.length; i++) {
yangHui[i] = new int[i + 1];
yangHui[i][0] = yangHui[i][i] = 1;
for (int j = 1; j < yangHui[i].length - 1; j++) {
yangHui[i][j] = yangHui[i - 1][j - 1] + yangHui[i - 1][j];
}
}
for (int[] ints : yangHui) {
for (int anInt : ints) {
System.out.print(anInt + " ");
}
System.out.println();
}
}
}
|
针对数值型的数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
public class ArrayEver1 {
public static void main(String[] args) {
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * (99 - 10 + 1) + 10);
}
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
int maxValue = arr[0];
for (int i : arr) {
if(maxValue < i){
maxValue = i;
}
}
System.out.println("最大值：" + maxValue);
int minValue = arr[0];
for (int i : arr) {
if(maxValue > i){
maxValue = i;
}
}
System.out.println("最小值：" + minValue);
double sum = 0;
for (int i : arr) {
sum += i;
}
System.out.println("总和：" + sum);
double avgValue = sum / arr.length;
System.out.println("平均数：" + avgValue);
}
}
|
Math.random()方法
在 Java 中主要提供了两种方式产生随机数，分别为调用 Math 类的 random()方法 和 Random 类提供的产生各种数据类型随机数的方法。
在 Math 类中存在一个 random() 方法，用于产生随机数字，这个方法默认生成大于等于 0.0 且小于 1.0 的 double 型随机数；即 0 <= Math.random() < 1.0，虽然 Math.random() 方法只可以产生 0 ~ 1 之间的double 型数字，其实只要在 Math.random() 语句上稍加处理，就可以产生任意范围的随机数。
(int)(Math.Random() * n ) → 返回大于等于 0 且小于 n 的随机数
m + (int)(Math.Random() * n ) → 返回大于等于 m 且小于 m+n（不包括m+n）的随机数
使用 Math 类的 random() 方法也可以随机生成字符，可以使用如下代码生成 a ~ z 之间的字符。
(char)(‘a’ + Math.random() * (‘z’ - ‘a’ + 1));
上述表达式可以求出更多的随机字符，如 A ~ Z 之间的随机字符，进而推理出求任意字符之间的随机字符，可以使用下列语句表示。
(char)(char1 + Math.random() * (cha2 - cha1 + 1));
数组的赋值与复制
赋值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public class ArrayTest3 {
public static void main(String[] args) {
int[] array1, array2;
array1 = new int[]{2, 3, 5, 7, 11, 13, 17, 19};
array2 = array1;
for (int i = 0; i < array2.length; i++) {
if (i % 2 == 0) {
array2[i] = i;
}
}
for (int i : array1) System.out.print(i + " ");
System.out.println();
for (int i : array2) System.out.print(i + " ");
}
}
|
简单理解如下图
复制，目前复制 Java 数组的复制，可以使用 System.arraycopy() 方法，但在这里，先用最简单的方式描述
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class ArrayTest4 {
public static void main(String[] args) {
int[] array1, array2;
array1 = new int[]{2, 3, 5, 7, 11, 13, 17, 19};
array2 = new int[array1.length];
for (int i = 0; i < array2.length; i++) {
array2[i] = array1[i];
}
array2[0] = 33;
for (int i : array1) System.out.print(i + " ");
System.out.println();
for (int i : array2) System.out.print(i + " ");
}
}
|
简单理解如下图
3.4 数组元素的反转
数组的反转，主要是找个临时变量 temp 进行替换操作即可
1
2
3
4
5
6
7
8
9
10
11
12
| public class ArrayTest5 {
public static void main(String[] args) {
String[] arr = new String[]{"SS", "QQ", "YY", "XX", "TT", "KK", "EE", "GG", "KK"};
for (int i = 0; i < arr.length / 2; i++) {
String temp = arr[i];
arr[i] = arr[arr.length - i -1];
arr[arr.length - i -1] = temp;
}
for (String i : arr) System.out.print(i + " ");
}
}
|
数组中指定元素的查找
线性查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public class ArrayTest6 {
public static void main(String[] args) {
String[] arr = new String[]{"SS", "QQ", "YY", "XX", "TT", "KK", "EE", "GG", "KK"};
String dest = "YY";
boolean isFlag = true;
for (int i = 0; i < arr.length; i++) {
if(dest.equals(arr[i])){
System.out.println("找到了指定元素，索引位置为: " + i);
isFlag = false;
break;
}
}
if(isFlag) System.out.print("很遗憾，没有找到元素");
}
}
|
二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
public class ArrayTest7 {
public static void main(String[] args) {
int[] arr2 = new int[]{-12, -8, 2, 12, 33, 35, 78, 89, 99, 112, 333, 456};
int dest = 33;
int head = 0;
int end = arr2.length - 1;
boolean isFlag = true;
while (head <= end) {
int minddle = (head + end) / 2;
if (dest == arr2[minddle]) {
System.out.println("找到了指定元素，索引位置为：" + minddle);
isFlag = false;
break;
} else if (arr2[minddle] > dest) {
end = minddle - 1;
} else {
head = minddle + 1;
}
}
if (isFlag) System.out.print("很遗憾，没有找到元素");
}
}
|
数组的排序算法
「十大排序算法」
- 选择排序：
- 交换排序：
- 插入排序：
- 归并排序
- 桶排序
- 基数排序
一些理解内容
- 衡量排序算法的优劣：时间复杂度、空间复杂度、稳定性
- 排序的分类：内部排序 与 外部排序（需要借助磁盘）
- 不同排序算法的性能对比
算法的五大特性
| 输入（Input） | 有 0 个或多个输入数据，这些输入必须有清楚的描述和定义 |
|---|
| 输出（Output） | 至少有 1 个或多个输出结果，不可以没有输出结果 |
| 有穷性（有限性，Finiteness） | 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成 |
| 确定性（明确性，Definiteness） | 算法中的每一步都有确定的含义，不会出现二义性 |
| 可行性（有效性，Effectiveness） | 算法的每一步都是清楚且可行的，能让用户用纸笔计算而求出答案 |
冒泡排序
冒泡排序的基本思想：通过对待排序序列从前向后，依次比较相邻元素的排序码，若发现逆序则交换，使排序码较大的元素逐渐从前部移向后部。
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序， 因此要在排序过程中设置一个标志 swap 判断元素是否进行过交换。从而减少不必要的比较。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class ArrayTest8 {
public static void main(String[] args) {
int[] arr = new int[]{2, 44, 11, 23, 1, 6, 47, 89, 56, 62, 38, 68, 46, 35, 99};
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
for(int i : arr) System.out.print(i + " ");
}
}
|
快速排序
这里暂时先不写，后续补充，目前冒泡，快速排序是必须掌握的内容
Arrays 工具类的使用
定义在 java.util 包下，Arrays 工具类提供了很多操作数组的方法，更多方法可参考 API 文档
| boolean equals(int[] a, int[] b) | 判断两个数组是否相等 |
|---|
| String toString(int[] a) | 输出数组信息 |
| void fill(int[] a,int val) | 将指定值填充到数组之中 |
| void sort(int[] a) | 对数组进行排序 |
| int binarySearch(int[] a,int key) | 对排序后的数组进行二分法检索指定的值 |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| import java.util.Arrays;
public class ArrayTest9 {
public static void main(String[] args) {
int[] arr1 = new int[]{1, 2, 3, 4};
int[] arr2 = new int[]{9, 5, 3, 7};
boolean isEquals = Arrays.equals(arr1, arr2);
System.out.println(isEquals);
System.out.println(Arrays.toString(arr1));
Arrays.fill(arr1, 10);
System.out.println(Arrays.toString(arr1));
Arrays.sort(arr2);
System.out.println(Arrays.toString(arr2));
int index = Arrays.binarySearch(arr2, 5);
if (index >= 0) {
System.out.println(index);
} else {
System.out.println("未找到");
}
}
}
|
数组使用中的常见异常
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
public class ArrayTest10 {
public static void main(String[] args) {
int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
int[] arr1 = new int[]{1, 2, 3};
}
}
|
提示：一旦程序出现异常，未处理时，就终止执行。
