第六章 数组

数组是一种数据类型，引用类型

数组是可以保存多个相同类型元素的，连续的内存空间

数组一旦创建，大小就不可变

6.1 数组的定义

语法：

数据类型[] 数组名；

数据类型 数组名[]；（兼容C++）

例如: int[] scores; //定义一个数组，元素都是int类型的，保存分数

6.2 数组的初始化

6.2.1 分配内存空间

一个数组，定义好之后，没有内存空间

语法：

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

例如：scores = new int[20]；20*4个字节的内存空间

当分配好内存空间，同时会对每一个元素设定一个默认值

规则：

1） byte，short，int，long，float，double，默认值都是0（或0.0）；

2） char类型的默认值是空字符

3） boolean类型默认值是false

4） 引用类型默认值是null

6.2.2 初始化元素

1）单独为每一个元素设置初始值

int[] scores;

scores = new int[20]；

scores[0] = 99;

scores[10] = 89;

2）分配空间同时初始化元素

数组名 = new 数据类型[]{元素1，元素2，…};

给数组分配内存空间，长度取决于{}中元素的数量

同时将{}内的元素作为数组元素的初始值

3）数组定义是直接分配元素

数据类型[] 数组名 = {元素1，元素2，…};

6.3 数组元素的访问

数组元素的访问主要依赖于下标

语法：

数组名[下标];

下标：

1）下标必须是0~长度-1范围内的整数

2）下标超出数组范围，这时代码会报错

3）数组是用之前必须进行初始化；

6.4 数组的操作

6.4.1 数组的遍历

把数组中的元素逐个取出来

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

arr[0]

arr[1]

arr[2]

1）使用循环，迭代下标


2）使用foreach增强for循环

循环与foreach遍历的区别

1）循环遍历，可以使用下标，foreach不知道元素对应的下标


2）for循环遍历时，可以直接操作元素，而foreach不可以

6.4.2 求和，求平均数

6.4.3 最大值，最小值

6.5 二维数组

一维：int[] arr = {1,2,3,4,5}

二维：数组中的每一个元素也是一个数组 int[][]

三维：数组中的每一个元素都是一个二维数组 int[][][]

多维：数组中的每一个元素都是一个多维数组

6.5.1 数组的内存

Java程序运行时，都是运行在JVM中

JVM的内存可以分为

1）栈：在方法运行时，会被放到栈中

2）堆：保存对象

3）方法区：存放类及类方法

4）本地方法区：本地方法（由C++,C编写的方法）

5）程序计数器：记录当前的程序运行到哪个位置（哪一行）

当使用java运行一个类时

1）由JRE中的ClassLoader（类加载器），将类的信息交给JVM

2）JVM会将类的信息保存到方法区中

3）JVM启动主线程，将main方法压入栈中

4）程序计数器记录main方法中执行的顺序

5）如果main中调用了其他方法，将被调用的方法压入栈中

6）如果在程序运行过程中，需要创建对象，对象将被放到堆中

变量内存：是在栈中被分配的

数组内存：

一维数组

凡是引用类型的变量，保存的都是内存中的一个地址
二维数组

6.5.2 二维数组的定义

语法：

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

6.5.3 二维数组的初始化

1）直接给两个维度分配内存

2）先分配第一维度，再分配第二维度

6.5.4 二维数组的遍历

第七章 数组算法

7.1 Arrays类

这是一个操作数组的工具类

Arrays类提供了如下方法

1. copyOf（数组，长度）；复制数组
2. copyOfRange（数组，起点，终点）；复制数组中的一部分（左闭右开）
3. equals（数组1，数组2）；比较两个数组中的值是否一样
4. fill（数组，值）；将数组中的元素，统一赋值为指定值
5. sort（数组）；对数组进行排序
6. binarySearch（数组，目标元素）；二分搜索法，查找元素

7.2 数组搜索

从数组中查找元素

1）查找元素是否存在

2）查找元素的下标

3）查找元素的数量

7.2.1 二分搜索法

查找算法，

查找目标集合必须是已经排好序的，有序

必须知道数组是升序还是降序

1）找到数组中间的元素

2）与目标元素进行对比

3）相等：目标元素找到了

4）中间元素大于目标元素：升序，目标只能在前半部分；降序，目标元素只能在后半部分

5）中间元素小于目标元素：升序，目标只能在后半部分；降序，目标元素只能在前半部分

6）将范围缩小到原来的一半，在执行二分查找算法，直到元素找到或数组已经没有元素

7.3 数组排序

把一个无序数组，调整元素位置，最终得到一个有序的数组（升序或降序）

7.3.1 十大排序算法

冒泡排序

插入排序

选择排序

快速排序

堆排序

希尔排序

归并排序

桶排序

计数排序

基数排序

时间复杂度：衡量算法执行的效率

空间复杂度：算法在执行过程中使用的内存空间的大小

稳定性：排序前后，相同的值顺序会不会交换

7.3.2 冒泡排序

最经典的排序算法

思想：相邻的元素进行比较，如果前面的元素>后面的元素，交换位置

或者：

7.3.3 选择排序

思想：先从数组中找到最大值放到末尾，再从剩下的元素中找到最大值放到剩下元素的末尾

7.3.4 插入排序

思想：先把第一个元素看作是一个有序数组，然后将第二个元素加入数组中，找到合适的位置形成新的有序数组

7.3.5 快速排序

思想：先选定数组中的第一个元素，作为一个标准

将所有比它小的元素放到该元素前面，将所有比她大的元素放到该元素后面

将前后两个部分，分别进行快速排序

7.3.6 计数排序

思想：是一种非比较性质的排序算法，元素从未排序状态变为已排序状态的过程，是由额外空间的辅助和元素本身的值决定的。计数排序过程中不存在元素之间的比较和交换操作，根据元素本身的值，将每个元素出现的次数记录到辅助空间后，通过对辅助空间内数据的计算，即可确定每一个元素最终的位置。