第3章_数组
数组的概述
4
数组(Array),是多个相同类型数据
按⼀定顺序排列的集合,并使⽤⼀
个名字命名,并通过编号的⽅式对
这些数据进⾏统⼀管理。
数组的常⻅概念
5
数组名(标识符命名)
下标(或索引),从0开始,这⾥务
必注意,很容易引起数组⻆标异常
元素(可以是任意类型的数据)
数组的⻓度(.length)
数组本身是引⽤数据类型,⽽数组
中的元素可以是任何数据类型,包
括基本数据类型和引⽤数据类型。
6
创建数组对象会在内存中开辟⼀整
块连续的空间,⽽数组名中引⽤的
是这块连续空间的⾸地址。
因为数组是引⽤数据类型变量,不
管数组中存储的数组是什么类型,
它本身都是引⽤数据类型变量,因
此数组名中存放的要么是地址值,
要么是null
6
数组的⻓度⼀旦确定,就不能修
改。
6
即便是像Arraylist这种所谓的动态
数组,其底层仍然是⽤数组进⾏存
储,在数组容量不⾜时重新造⼀个
容量更⼤的数组⽽已。
我们可以直接通过下标(或索引)的
⽅式调⽤指定位置的元素,速度很
快。
6
务必记住下标从0开始调⽤
数组的分类:
6
按照维度:⼀维数组、⼆维数组、
三维数组、…
6
按照元素的数据类型分:基本数据
类型元素的数组、引⽤数据类型元
素的数组(即对象数组)
6
⼀维数组的使⽤
7
⼀维数组的使⽤:声明
8
type var[] 或 type[] var
type可以是任意类型的数据,包括
基本数据类型,JDK⾃带的类,⾃
⼰定义的类,需要注意的是再创建
引⽤数据类型数组后,需要对其内
部元素进⾏实例化,通常可以使⽤
new⽅式进⾏匿名实例化,但
String类可以通过字⾯量的⽅式进
⾏实例化。
8
⼀维数组的使⽤:初始化
9
动态初始化
9
数组声明且为数组元素分配空间与
赋值的操作分开进⾏
9
9
静态初始化
9
在定义数组的同时就为数组元素分
配空间并赋值。
9
9
⼀维数组的使⽤:数组元素的引⽤
10
数组元素的引⽤⽅式:数组名[数组
元素下标]
10
数组元素下标可以是整型常量或整
型表达式。如a[3] , b[i] , c[6*i];
数组元素下标从0开始;⻓度为n的
数组合法下标取值范围: 0 —>n-1;
如int a[]=new int[3]; 可引⽤的数
组元素为a[0]、a[1]、a[2]
10
每个数组都有⼀个属性length指明
它的⻓度,例如:a.length 指明数组a
的⻓度(元素个数)
10
数组⼀旦初始化,其⻓度是不可变
的
⼀维数组的使⽤:数组元素的默认
初始化值
11
数组是引⽤类型,它的元素相当于
类的成员变量,因此数组⼀经分配
空间,其中的每个元素也被按照成
员变量同样的⽅式被隐式初始化。
例如:
11
变量可以分为成员变量
(在类中声明的变量,例
如属性)和局部变量(在
⽅法中声明的变量,例如
在MAIN⽅法中声明的变量
全部为局部变量)
注意:成员变量会默认初始化,⽽
局部变量不会默认初始化。
数组元素的默认初始化值
12
⼀维数组的使⽤:创建基本数据类
型数组
13
由图可知,数组的创建分为三步。
第⼀:在栈空间中创建局部变量
(数组名)⽤来存储数据在堆空间
的地址值。
第⼆:在堆空间中开辟数组空间,
其内部数据皆为默认初始值。
第三:根据需要对堆空间中的数据
进⾏修改,如不修改,则为初始
值。
Java中使⽤关键字new来创建数组
13
13
根据此图可以得出,数组名是存储
在栈空间中的,⽽数据则存储在堆
空间中,数组名只存储地址值⽽
已。
14
14
15
15
多维数组的使⽤
23
对于⼆维数组的理解,我们可以看
成是⼀维数组array1⼜作为另⼀个
⼀维数组array2的元素⽽存在。其
实,从数组底层的运⾏机制来看,其
实没有多维数组。
⼆维数组[][]:数组中的数组
25
SUMMARY
27
格式1(动态初始化):int[][] arr =
new int[3][2];
25
定义了名称为arr的⼆维数组⼆维
数组中有3个⼀维数组每⼀个⼀维
数组中有2个元素⼀维数组的名称
分别为arr[0], arr[1], arr[2] 给第⼀
个⼀维数组1脚标位赋值为78写法
是:arr[0][1] = 78;
25
格式2(动态初始化):int[][] arr =
new int[3][];
25
⼆维数组中有3个⼀维数组。
每个⼀维数组都是默认初始化值
null (注意:区别于格式1) 可以对这
个三个⼀维数组分别进⾏初始化
arr[0] = new int[3]; arr[1] = new
int[1]; arr[2] = new int[2];
25
格式3(静态初始化):int[][] arr =
new int[][]{{3,8,2},{2,7},{9,0,1,6}};
26
定义⼀个名称为arr的⼆维数组,⼆
维数组中有三个⼀维数组
每⼀个⼀维数组中具体元素也都已
初始化
第⼀个⼀维数组 arr[0] = {3,8,2};
第⼆个⼀维数组 arr[1] = {2,7};
第三个⼀维数组 arr[2] = {9,0,1,6};
第三个⼀维数组的⻓度表示⽅
式:arr[2].length;
26
⼆维数组的内存解析
28
28
⼆维数组内存解析说明:
⾸先必须了解的是,在Java底层
中根本没有⼆维数组和多维数组,
⼆维数组只是⼀维数组的元素为数
组⽽已。
如图所示:
在栈空间中⾸先创建了局部变量数
组名,⽤来存储位于堆空间中数据
的地址值。
在堆空间中⾸先开辟了⼀个⻓度为
4的⼀维数组空间,该⼀维数组在
还未实例化之前存储的是null,在
实例化之后存储的是其他⼀维数组
的地址值
根据⻓度在堆空间中创建相应的⼀
维数组,并存储数据。
29
左边红⾊第⼀⾏显示
NULL,因为此时的数组仍
未实例化,并未指向具体
的数组,因此只能是
NULL。红⾊第⼆⾏之所以
报错是因为此时的数组并
未实例化,ARR4[0][0]根
本就不存在,因此报错。
数组中涉及到的常⻅算法
35
数组元素的赋值(杨辉三⻆、回形
数等)
36
求数值型数组中元素的最⼤值、最
⼩值、平均数、总和等
36
数组的复制、反转、查找(线性查
找、⼆分法查找)
36
线性查找:
线性查找很简单,就是遍历数组,
然后⼀个⼀个去查找,但效率太
差。
⼆分法查找:
⼆分法查找效率较⾼,难度也不
⼤。实现原理:⾸先确定⾸索引位
置和尾索引位置以及⽐较索引的位
置,初始⾸索引位置为0,初始尾
索引位置为length - 1;⽐较索引
的位置为⾸索引位置与尾索引位置
加和除以2,将⽐较索引的数据与
需要查找的数据进⾏⽐较,如果相
等皆⼤欢喜,如果⽐较索引数据⼩
于查找数据,那么令⾸索引位置等
于⽐较索引-1。如果⽐较数据索引
⼤于查找数据,那么令尾索引位置
等于⽐较索引+1。
⼆分法的实现代码
42
数组元素的排序算法
36
通常来说,排序的⽬的是快速查
找。
衡量排序算法的优劣:
43
时间复杂度:分析关键字的⽐较次
数和记录的移动次数
空间复杂度:分析排序算法中需要
多少辅助内存
稳定性:若两个记录A和B的关键字
值相等,但排序后A、B的先后次序
保持不变,则称这种排序算法是稳
定的。
排序算法分类:
44
内部排序:整个排序过程不需要借
助于外部存储器(如磁盘等),所有排
序操作都在内存中完成。
44
外部排序:参与排序的数据⾮常多,
数据量⾮常⼤,计算机⽆法把整个
排序过程放在内存中完成,必须借
助于外部存储器(如磁盘)。外部排
序最常⻅的是多路归并排序。可以
认为外部排序是由多次内部排序组
成。
44
⼗⼤内部排序算法
45
SUMMARY
排序算法性能对⽐
52
52
各种内部排序⽅法性能⽐较
53
53
排序算法的选择
54
54
选择排序
45
直接选择排序、堆排序
交换排序
45
冒泡排序、快速排序
冒泡排序
47
47
由上述的排序思想可知,冒泡排序
的遍历次数为(n - 1)次。
快速排序 ⾮常重要的⼀种排序⽅
法
48
快速排序(Quick Sort)由图灵奖获
得者Tony Hoare发明,被列为20世
纪⼗⼤算法之⼀,是迄今为⽌所有
内排序算法中速度最快的⼀种。冒
泡排序的升级版,交换排序的⼀
种。快速排序的时间复杂度为
O(nlog(n))。
49
插⼊排序
45
直接插⼊排序、折半插⼊排序、
Shell排序
归并排序
45
桶式排序
45
基数排序
45
算法的5⼤特征
46
46
Arrays⼯具类的使⽤
55
因为是⼯具类,因此⾥⾯的⽅法全
部为静态⽅法。
boolean equals(int[] a,int[] b) 判
断两个数组是否相等。
56
String toString(int[] a) 输出数组信
息。
56
void fill(int[] a,int val) 将指定值填
充到数组之中
56
void sort(int[] a) 对数组进⾏排
序。
56
int binarySearch(int[] a,int key) 对
排序后的数组进⾏⼆分法检索指定
的值。
56
数组使⽤中的常⻅异常
58
数组脚标越界异常
(ArrayIndexOutOfBoundsExcepti
on)
59
访问到了数组中的不存在的脚标时
发⽣。
空指针异常
(NullPointerException)
59
arr引⽤没有指向实体,却在操作实
体中的元素时。