数组的定义与创建
-
数组是相同类型数据的有序集合。数组描述的是相同类型的若干个数据，按照先后一定的次序排列组合而成。每个数据被称为一个数组元素，每个数组元素可以通过一个下标来访问它们。
-
声明创建：
-
首先必须声明数组变量，才能在程序中使用数组。语法为：
dataType[] arrayRefVar；//首选的方法,如int[] nums; 或者 dataType arrayRefVar[]；//效果相同，但不是首选方法,如int nums[]; -
Java 使用 new 操作符来创建数组，语法为：
dataType[] arrayRefVar = new dataType[arraySize]; nums=new int[10] //即创建一个有 10 个元素的数组 int[] nums = new int[10] //可以同时声明并创建数组 -
数组的元素是通过索引访问的，数组索引从 0 开始。
int num[0] = 1 ;//给数组第一个元素赋值 1 -
获取数组长度：
arrays.length //如nums.length
-
三种初始化及内存分析
-
堆（Heap）
- 存放 new 的对象和数组
- 可以被所有线程共享，不会存放别的对象引用
- 堆内存是动态的，一般不被引用时会被垃圾收集器回收
-
栈（Stack）
- 每个线程在启动时都会创建一个对应的栈，用来存储该线程的方法调用、局部变量等。
- 存放基本变量类型（会包含这个基本类型的具体数值）
- 引用对象的变量（会存放这个引用在堆里面的具体位置）
- 栈内存是固定的，不需要进行垃圾回收，变量的作用域一旦结束，所占的内存就被自动释放
-
方法区
-
可以被所有的线程共享
-
包含了所有的 class 和 static 变量
-
三种初始化
-
静态初始化（创建+赋值，定义之后无法改变）
int[] a = {1,2,3}; Man[] mans = {new Man(1,1),new Man(2,2)}; -
动态初始化（使用 new）
int[] a =new int[2]; a[0] = 1; a[1] = 2; -
数组的默认初始化
数组是引用类型，它的元素相当于类的实例变化，因此数组一经分配空间，其中的每个元素也被按照实例变量同样的方式被隐式初始化。
-
数组的特点
- 其长度是确定的。数组一旦被创建，那么大小就无法改变
- 其元素必须是相同类型，不允许出现混合类型
- 数组中的元素可以是任何数据类型，包括基本类型和引用类型
- 数组变量属引用类型，数组也可以看作对象，数组中的每个元素都相当于该对象的成员变量。数组本身就是对象，Java 的对象是在堆中的，因此数组无论保存原始类型还是其他对象类型，数组对象本身就是在堆中的
数组边界
- 下标的合法区间：[0,length-1]，如果越界就会报错
- ArrayIndexOutOfBoundsException：数组下标越界异常
数组的使用
-
普通的 for 循环
public class TestArray { public static void main(String[] args) { double[] myList = {1.9, 2.9, 3.4, 3.5}; // 打印所有数组元素 for (int i = 0; i < myList.length; i++) { System.out.println(myList[i] + " "); } // 计算所有元素的总和 double total = 0; for (int i = 0; i < myList.length; i++) { total += myList[i]; } System.out.println("Total is " + total); // 查找最大元素 double max = myList[0]; for (int i = 1; i < myList.length; i++) { if (myList[i] > max) max = myList[i]; } System.out.println("Max is " + max); } } -
For-Each 循环：能在不使用下标的情况下遍历数组
for(type element: array) { System.out.println(element); } //举例 public class TestArray { public static void main(String[] args) { double[] myList = {1.9, 2.9, 3.4, 3.5}; // 打印所有数组元素 for (double element: myList) { System.out.println(element); } } } -
数组作为方法的参数：
public static void printArray(int[] array) { for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } } -
数组作为方法的返回值：
public static int[] reverse(int[] list) { int[] result = new int[list.length]; for (int i = 0, j = result.length - 1; i < list.length; i++, j--) { result[j] = list[i]; } return result; }
多维数组
-
多维数组可以看成是数组的数组，比如二维数组就是一个特殊的一维数组，其每一个元素都是一个一维数组。
-
二维数组：
int a[][] = new int[2][5] //以上二维数组 a 可以看成一个两行五列的数组 public class ArrayDemo{ public static void main(String[] args){ //[4][2] /* 1,2 array[0] 2,3 array[1] 3,4 array[2] 4,5 array[3] */ int[][] array = {{1,2},{2,3},{3,4},{4,5}}; System.out.println(array[2][0])； //输出为3 System.out.println(array[2][1])； //输出为4 } } -
循环输出数组
public class ArrayDemo{ public static void main(String[] args){ //[4][2] /* 1,2 array[0] 2,3 array[1] 3,4 array[2] 4,5 array[3] */ int[][] array = {{1,2},{2,3},{3,4},{4,5}}; //循环输出数组 for (int i = 0;i < array.length ; i++){ for(int j = 0;j< array[i].length ; j++){ System.out.println(array[i][j]); //输出结果依次为1 2 2 3 3 4 4 5 } } } }
Arrays 类
-
数组的工具类 java.util.Arrays
-
功能：
-
给数组赋值：通过 fill 方法
-
对数组排序：通过 sort 方法，按升序
-
比较数组：通过 equals 方法比较数组中元素值是否相等
-
查找数组元素：通过 binarySearch 方法能对已经排序好的数组进行二分法查找
序号 方法和说明 1 public static int binarySearch(Object[] a, Object key) 用二分查找算法在给定数组中搜索给定值的对象(Byte,Int,double等)。数组在调用前必须排序好的。如果查找值包含在数组中，则返回搜索键的索引；否则返回 (-(插入点) - 1)。 2 public static boolean equals(long[] a, long[] a2) 如果两个指定的 long 型数组彼此相等，则返回 true。如果两个数组包含相同数量的元素，并且两个数组中的所有相应元素对都是相等的，则认为这两个数组是相等的。换句话说，如果两个数组以相同顺序包含相同的元素，则两个数组是相等的。同样的方法适用于所有的其他基本数据类型（Byte，short，Int等）。 3 public static void fill(int[] a, int val) 将指定的 int 值分配给指定 int 型数组指定范围中的每个元素。同样的方法适用于所有的其他基本数据类型（Byte，short，Int等）。 4 public static void sort(Object[] a) 对指定对象数组根据其元素的自然顺序进行升序排列。同样的方法适用于所有的其他基本数据类型（Byte，short，Int等）。
-
冒泡排序
-
冒泡排序（Bubble Sort）是一种基本的排序算法。其原理是通过相邻元素之间的比较和交换来将最大或者最小值“冒泡”到数组的末尾。
-
是嵌套循环，算法的时间复杂度为 O(n2)。
public class BubbleSort { public static void main(String[] args) { int[] arr = {5, 2, 8, 3, 1}; // 要排序的数组 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; } } } System.out.println("排序后的结果："); for (int num : arr) { System.out.print(num + " "); } } }
稀疏数组
-
当一个数组中大部分元素为 0，或者为同一值的数组时，可以使用稀疏数组来保存该数组。
-
稀疏数组的工作过程：
-
记录数组一共有几行几列，有多少不同值
-
把具有不同值的元素及值记录在一个小规模数组中，从而缩小程序的规模
行(row) 列(col) 值(value) [0] 5 6 3 [1] 1 0 1 [2] 1 3 6 [3] 4 3 2 - 其中第一列[0]的意思分别为原始数组有 5行 6 列，之后 row 和 col 都是从 0 开始计数建立新的数组
-
-
代码实现：
public class SparseArray { public static void main(String[] args) { //先创建原始二维数组 int[][] originalArray = new int[10][10]; originalArray[0][4] = 1; originalArray[0][8] = 1; originalArray[1][5] = 1; originalArray[1][7] = 1; originalArray[4][8] = 1; originalArray[5][5] = 1; originalArray[7][2] = 1; originalArray[8][7] = 1; //输出原始的二维数组 System.out.println("原始的二维数组:"); for (int[] row: originalArray) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } //将二维数组转成稀疏数组 //1.遍历二维数组，得到非0的有效数据的个数 int amount = 0; for (int i = 0; i < originalArray.length; i++) { for (int j = 0; j < originalArray[i].length; j++) { if (originalArray[i][j] != 0){ amount++; } } } System.out.println("amount = " + amount); //2.创建对应的稀疏数组 sparseArray[amount+1][3], 并初始化稀疏数组第一行的数据 //第一行第一列: 原数组的行数 第一行第二列: 原数组的列数 第一行第三列: 原数组的有效数据个数 int[][] sparseArray = new int[amount + 1][3]; sparseArray[0][0] = 10; sparseArray[0][1] = 10; sparseArray[0][2] = amount; //3.遍历二维数组,将非0值存储进稀疏数组 int count = 0; //用于记录是第几个非零数据 for (int i = 0; i < originalArray.length; i++) { for (int j = 0; j < originalArray[i].length; j++) { if (originalArray[i][j] != 0){ count++; sparseArray[count][0] = i; //记录所在行 sparseArray[count][1] = j; //记录所在列 sparseArray[count][2] = originalArray[i][j]; //记录值 } } } //输出稀疏数组 System.out.println("稀疏数组:"); for (int i = 0; i < sparseArray.length; i++) { System.out.printf("%d\t%d\t%d\n", sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]); } //将稀疏数组恢复成为二维数组 //1.根据稀疏数组的第一行初始化二维数组 int[][] recoveredArray = new int[sparseArray[0][0]][sparseArray[0][1]]; //2.读取稀疏数组的后面行数据，赋值给原始二维数组 for (int i = 1; i < sparseArray.length; i++) { recoveredArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2]; } //输出二维数组 System.out.println("恢复后的二维数组:"); for (int[] row: recoveredArray) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } } }//输出结果： 原始的二维数组: 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 amount = 8 稀疏数组: 10 10 8 0 4 1 0 8 1 1 5 1 1 7 1 4 8 1 5 5 1 7 2 1 8 7 1 恢复后的二维数组: 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0