Java 学习之路——数组

Java 学习之路——数组

数组的概述

1. 数组（Array）是多个相同类型数据按一定顺序排列的集合，并使用一个名字命名，并通过编号的方式对这些数据进行统一管理。

2. 数组的常见概念：

• 数组名
• 下标（或索引）
• 元素
• 数组的长度（元素的个数），一旦确定就不可以修改。

3.数组本身是引用数据类型，而数组中的元素可以是任何数据类型，包括基本数据类型和引用数据类型。

4.创建数组对象会在内存中开辟一整块连续的空间，而数组名中引用的是这块连续空间的首地址。

5.数组的长度一旦确定，就不能修改。

6.可以直接通过下标（或索引）的方式调用指定位置的元素，速度很快。

7.数组的分类：

• 按照维度：一维数组、二维数组、三维数组...
• 按照元素的数据类型分：基本数据类型元素的数组、引用数据类型元素的数组（即对象数组）。

一维数组的使用

1. 一维数组的声明和初始化：

int num;  // 声明
num = 10; // 初始化
int id = 1001;  // 声明 + 初始化
int[] ids;  // 声明
// 静态初始化：数组的初始化和数组元素的赋值操作同时进行。
ids = new int[]{1001,1002,1003,1004}; // 初始化
// 动态初始化：数组的初始化和数组元素的赋值操作分开进行。
String[] = new String[5];

2.调用数组的指定位置的元素：通过角标的方式调用。

• 数组的角标（或索引）从 0 开始，到数组的长度 -1 结束。

names[0] = "XXX";

3.获取数组的长度：（属性：length）

// names.length
System.out.println(names.length);

4.遍历数组：

for(int i = 0;i < names.length;i++){
  System.out.println(names[i]);
}

5.数组元素的默认初始化值：

6.数组的内存解析：

• 栈内存：栈内存首先是一片内存区域，存储的都是局部变量，凡是定义在方法中的都是局部变量（方法外的是全局变量），for循环内部定义的也是局部变量，是先加载函数才能进行局部变量的定义，所以方法先进栈，然后再定义变量，变量有自己的作用域，一旦离开作用域，变量就会被释放。栈内存的更新速度很快，因为局部变量的生命周期都很短。

• 堆内存：存储的是数组和对象（其实数组就是对象），凡是new建立的都是在堆中，堆中存放的都是实体（对象），实体用于封装数据，而且是封装多个（实体的多个属性），如果一个数据消失，这个实体也没有消失，还可以用，所以堆是不会随时释放的，但是栈不一样，栈里存放的都是单个变量，变量被释放了，那就没有了。堆里的实体虽然不会被释放，但是会被当成垃圾，Java有垃圾回收机制不定时的收取。

• 堆和栈的联系：

• 堆分配了一个地址，把堆的地址赋给arr，arr就通过地址指向了数组。所以arr想操纵数组时，就通过地址，而不是直接把实体都赋给它。这种我们不再叫他基本数据类型，而叫引用数据类型。称为arr引用了堆内存当中的实体。

• 堆和栈的区别：

• 栈内存存储的是局部变量而堆内存存储的是实体；
• 栈内存的更新速度要快于堆内存，因为局部变量的生命周期很短；
• 栈内存存放的变量生命周期一旦结束就会被释放，而堆内存存放的实体会被垃圾回收机制不定时的回收。

二维数组的使用

1. Java 语言里提供了支持多维数组的语法。

2. 如果说可以把一维数组当成几何中的线性图形，那么二维数组就相当于是一个表格。

3. 对于二维数组的理解，可以看成是一堆一维数组 array1 又作为另一个一维数组 array2 的元素而存在。其实，从数组底层的运行机制来看，其实没有多维数组。

4. 二维数组分为外层数组和内层数组。

int[] arr = new int[]{1,2,3}; // 一维数组
// 静态初始化
int[][] arr1 = new int[][]{{1,2,3},{4,5},{6,7,8}};
// 动态初始化1
String[][] arr2 = new String[3][2];
// 动态初始化2
String[][] arr3 = new String[3][];
// 以下这种方式也是对的
int[] arr4 = {1,2,3,4,5,6}; // 类型判断

5.遍历二维数组：

// 使用两个 for 循环对二维数组进行遍历。
for(int i = 0;i < arr.length;i++){
  for(int j = 0;j < arr[i].length;j++){
    System.out.println(arr[i][j] + "   ");
  }
  System.out.println();
}

6.数组元素的默认初始值：

• 外层数组的默认初始值是地址值。
• 内层数组的默认值和一维数组的默认值相同。

Arrays 工具类的使用

1. java.util.Arrays 类即为操作数组的工具类，包含了用来操作数组（比如排序和搜索）的各种方法。

数组使用中的常见异常

1. 数组角标越界的异常：ArrayIndexOutOfBoundsExcetion 。

int[] arr = new int[]{1,2,3,4,5};
// 右侧越界
for(int i = 0;i <= arr.length;i++){
  System.out.println(arr[i]);
}
// 左侧越界
System.out.println(arr[-2]);

2.空指针异常：NullPointerException 。

// 情况一：
int[] arr1 = new int[]{1,2,3,4,5};
arr1 = null;
System.out.println(arr1[0]);
// 情况二：
int[][] arr2 = new int[4][];
System.out.println(arr2[0][0]);
// 情况三：
String[] arr3 = new String[]{"AA","BB","CC"};
arr3[0] = null;
System.out.println(arr3[0].toString());

数组中涉及到的常见算法

1. 数组元素的赋值（杨辉三角、回型数等）。

2. 求数值型数组中元素的最大值、最小值、平均数、总和等。

3. 数组的复制、反转、查找（线性查找、二分法查找）。

• 数组的复制

int[] arr1,arr2;
arr1 = new int[]{2,3,5,7,11,13,17,19};
arr2 = new int[arr1.length];
for(int i = 0;i<arr2.length;i++){
  arr2[i] = arr1[i];
}

数组的反转

// 方法一
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(int i = 0,j = arr.length - 1;i < j;i++,j--){
  String temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

线性查找

String dest = "BB";
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){
  Syetem.out.println("很遗憾没有找到。");
}

二分法查找（熟悉）

• 前提：所要查找的数组必须有序。

int[] arr2 = new int[]{-98,-34,2,34,54,66,79,105,210,333};
int dest1 = -34;
int head = 0;
int end = arr2.length - 1;
boolean isFlag1 = true;
while(head <= end){
  int middle = (head + end) / 2;
  if(dest1 == arr2[middle]){
    System.out.println("找到了指定的元素，位置为" + middle);
    isFlag1 = false;
    break;
  }else if(arr2[middle] > dest1){
    end = middle - 1;
  }else{
    head = middle + 1;
  }
  if(isFlag){
    System.out.println("很遗憾，没有找到！")
  }
}

4.数组元素的排序算法。

• 衡量排序算法的优劣：

• 时间复杂度：分析关键字的比较次数和记录的移动次数。
• 空间复杂度：分析排序算法中需要多少辅助内存。
• 定性：若两个记录 A 和 B 的关键字值相等，但排序后 A 、B 的先后次序保持不变，则称为这种算法是稳定的。

• 排序算法分类：内部排序和外部排序。

• 内部排序：整个排序过程不需要借助于外部存储器（如磁盘等），所有排序操作都在内存中完成。
• 外部排序：参与排序的数据非常多，数据量非常大，计算机无法把整个排序过程放在内存中完成，必须借助于外部存储器（如磁盘）。外部排序最常见的是多路归并排序。可以认为外部排序是由多次内部排序组成。

• 十大内部排序算法：

• 选择排序

• 直接选择排序、堆排序

• 交换排序

• 冒泡排序、快速排序

• 插入排序

• 直接插入排序、折半插入排序、Shell 排序

• 归并排序
• 桶式排序
• 基数排序

冒泡排序

1. 冒泡排序的原理非常简单，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

2. 排他思想：

• 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。

• 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

• 针对所有的元素重复以上的步骤，除了最后一个。

• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较为止。

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

快速排序

1. 快速排序通常明显比同为 O(nlogn) 的其他算法更快，因此常被采用，而且快速排序采用了分治法的思想，所以在很多笔试面试中经常看到快速排序的影子。可见掌握快速排序的重要性。

2. 快速排序（Quick Sort）由图灵奖获得者 Tony Hoare 发明，被列为20 世纪十大算法之一，是迄今为止所有内排序算法中速度最快的一种。冒泡排序的升级版，交换排序的一种。快速排序的时间复杂程度为 O(nlog(n)) 。

算法

1. 算法的五大特征：
   

• 说明：满足确定性的算法也称为：确定性算法。
• 不要求终止的计算描述，这种描述被称为过程（procedure）。