1. 数组的概念
数组(Array)， 是多个相同类型数据按一定顺序排列的集合， 并使用一个名字命名， 并通过编号的方式对这些数据进行统一管理。
数组属于引用数据类型的变量，数组元素可以是基本数据类型，也可以是引用数据类型。
- 数组名： 用于标识一个连续数据集合，指向的是数组的首元素
- 数组元素： 同一个数组的数组元素类型必须相同，并且数组是有序排列，这里的有序指的是空间连续
- 下标： 可以通过下标索引对数组元素快速定位查找
- 数组长度：数组对象创建后会在内存中开辟一整块连续的空间，数组长度一旦确定不可更改，但是可以通过改变数组指向，赋予新的地址空间和长度
2. 数组的分类
按维度来分： 一维，二维，多维
按数据类型来分： 基本数据类型数组，引用数据类型数组
3. 一维数组的使用
3.1 一维数组的声明和初始化
- 声明： 数组类型[] 数组名; eg: int[] arr; 或者 数组类型 数组名[] eg: int arr[]; 声明数组时不能指定其长度(数组中元素的数)
- 静态初始化：数组的初始化和数组元素的赋值操作同时进行 eg: int[] arr=new int[]{1,2,3,4,5}; int[] brr={1,3,5,7,9};
- 动态初始化：数组的初始化和数组元素的赋值操作分开进行 eg: String[] arr=new String[5];
//常见的错误写法 //int[] arr1=new int[]; //int[5] arr2=new int[5]; //int[] arr3 =new int[3]{1,2,3}; //int[5] arr4; //正确声明方式 type var[] 或 type[] var； //声明数组时不能指定其长度(数组中元素的数) //静态初始化 int[] arr=new int[]{1,2,3,4,5}; int[] brr={1,3,5,7,9};//类型推断 //动态初始化 String[] arr=new String[5]; //随后进行赋值操作
3.2 如何调用数组的指定位置的元素
- 通过数组下标（索引）调用，索引从0开始，到数组的长度-1为止，引用格式为：数组名[数组元素下标]
- 数组越界属于运行时异常，编译越界会报错：ArrayIndexOutOfBoundsException
3.3 获取数组的长度
- 获取数组长度：数组名.length
- 遍历数组： for循环
3.4 数组元素的默认初始化
- 在位数组是引用类型，它的元素相当于类的成员变量，因此数组一经分配空间，其中的每个元素也被按照成员变量同样的方式被隐式初始化
- 默认初始化： 数组元素为整型，默认为0；数组元素是浮点型，默认为0.0；数组元素是char型，默认为0，这里的0 代表的是‘\u0000’，不是字符‘0’；引用数据类型默认为null
3.5 数组的内存解析
- java内存分配
- 数组内存解析
4. 多维数组的使用
Java 语言里提供了支持多维数组的语法；从数组底层运行机制来看，其实没有多维数组
/* * 二维数组的使用 * ① 二维数组的声明和初始化 * ② 如何调用数组的指定位置的元素 * ③ 如何获取数组的长度 * ④ 如何遍历数组 */ public class ArrayTest2 { public static void main(String[] args) { //1.二维数组的声明和初始化 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][]; //错误的情况 // String[][] arr4 = new String[][4]; // String[4][3] arr5 = new String[][]; // int[][] arr6 = new int[4][3]{{1,2,3},{4,5},{6,7,8}}; //也是正确的写法：没有规定各行的列数必须相等 int[] arr4[] = new int[][]{{1,2,3},{4,5,9,10},{6,7,8}}; int[] arr5[] = {{1,2,3},{4,5},{6,7,8}}; //2.如何调用数组的指定位置的元素 System.out.println(arr1[0][1]);//2 第一行第二个元素 System.out.println(arr2[1][1]);//null arr3[1] = new String[4]; System.out.println(arr3[1][0]); //3.获取数组的长度 System.out.println(arr4.length);//3 System.out.println(arr4[0].length);//3 System.out.println(arr4[1].length);//4 //4.如何遍历二维数组 for(int i = 0;i < arr4.length;i++){ for(int j = 0;j < arr4[i].length;j++){ System.out.print(arr4[i][j] + " "); } System.out.println(); } } }
/* * 二维数组的使用： * 规定：二维数组分为外层数组的元素，内层数组的元素 * int[][] arr = new int[4][3]; * 外层元素：arr[0],arr[1]等 * 内层元素：arr[0][0],arr[1][2]等 * * ⑤ 数组元素的默认初始化值 * 针对于初始化方式一：比如：int[][] arr = new int[4][3]; * 外层元素的初始化值为：地址值 * 内层元素的初始化值为：与一维数组初始化情况相同 * * 针对于初始化方式二：比如：int[][] arr = new int[4][]; * 外层元素的初始化值为：null * 内层元素的初始化值为：不能调用，否则报错。 * */ public class ArrayTest3 { public static void main(String[] args) { int[][] arr = new int[4][3]; System.out.println(arr[0]);//[I@15db9742 System.out.println(arr[0][0]);//0 // System.out.println(arr);//[[I@6d06d69c ，两个[[表示是一个二维数组 System.out.println("*****************"); float[][] arr1 = new float[4][3]; System.out.println(arr1[0]);//地址值 System.out.println(arr1[0][0]);//0.0 System.out.println("*****************"); String[][] arr2 = new String[4][2]; System.out.println(arr2[1]);//地址值 System.out.println(arr2[1][1]);//null System.out.println("*****************"); double[][] arr3 = new double[4][]; System.out.println(arr3[1]);//null // System.out.println(arr3[1][0]);//报错 } }
- 二维数组的内存解析
5. Arrays工具类的使用
- equals 源码
public static boolean equals(long[] a, long[] a2) { //静态方法，返回布尔类型 if (a==a2) return true; //如果二者指向的是同一块地址空间，相等 if (a==null || a2==null) return false; //如果有一方是null，返回false int length = a.length; if (a2.length != length) //如果二者数组长度不一致，返回false return false; return ArraysSupport.mismatch(a, a2, length) < 0; //逐个比较，如果都相等，mismatch返回-1，如果有不相同的元素，会返回该元素下标，则一定不小于0 }
- toString 源码
public static String toString(long[] a) { if (a == null) return "null"; //如果数组为null，输出null，但不代表数组元素值为null int iMax = a.length - 1; if (iMax == -1) return "[]"; //如果数组长度为0，则说明是一个空数组，输出[] StringBuilder b = new StringBuilder(); //用StringBuilder拼接输出，输出格式为[n1,n2,...,nm] b.append('['); for (int i = 0; ; i++) { b.append(a[i]); if (i == iMax) //判断到达数组最后元素 return b.append(']').toString(); b.append(", "); } }
- fill源码
public static void fill(long[] a, long val) { for (int i = 0, len = a.length; i < len; i++) //逐个遍历，赋予val a[i] = val; }
- sort 利用的快速排序思想，默认升序,
- 当元素个数小于286时，进入sort方法，如果元素少于47这个阀值，就用插入排序
- 如果元素大于47，用一种快速排序的方法
- 从数列中挑出五个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
- 当元素个数>286时，看看数组结构是否满足数据结构。
- 实际逻辑是分组排序，每降序为一个组，像1,9,8,7,6,8。9到6是降序，为一个组，然后把降序的一组排成升序：1,6,7,8,9,8。然后最后的8后面继续往后面找。每遇到这样一个降序组，++count
- 当count大于MAX_RUN_COUNT（67），被判断为这个数组不具备结构（也就是这数据时而升时而降），然后送给之前的sort(里面的快速排序)的方法
- count少于MAX_RUN_COUNT（67）的，说明这个数组还有点结构，就继续往下走下面的归并排序
public static void sort(int[] a) { DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); } // DualPivotQuicksort.sort方法 static void sort(int[] a, int left, int right, int[] work, int workBase, int workLen) { // Use Quicksort on small arrays if (right - left < QUICKSORT_THRESHOLD) { sort(a, left, right, true); return; } /* * Index run[i] is the start of i-th run * (ascending or descending sequence). */ int[] run = new int[MAX_RUN_COUNT + 1]; int count = 0; run[0] = left; // Check if the array is nearly sorted for (int k = left; k < right; run[count] = k) { // Equal items in the beginning of the sequence while (k < right && a[k] == a[k + 1]) k++; if (k == right) break; // Sequence finishes with equal items if (a[k] < a[k + 1]) { // ascending while (++k <= right && a[k - 1] <= a[k]); } else if (a[k] > a[k + 1]) { // descending while (++k <= right && a[k - 1] >= a[k]); // Transform into an ascending sequence for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) { int t = a[lo]; a[lo] = a[hi]; a[hi] = t; } } // Merge a transformed descending sequence followed by an // ascending sequence if (run[count] > left && a[run[count]] >= a[run[count] - 1]) { count--; } /* * The array is not highly structured, * use Quicksort instead of merge sort. */ if (++count == MAX_RUN_COUNT) { sort(a, left, right, true); return; } } // These invariants should hold true: // run[0] = 0 // run[<last>] = right + 1; (terminator) if (count == 0) { // A single equal run return; } else if (count == 1 && run[count] > right) { // Either a single ascending or a transformed descending run. // Always check that a final run is a proper terminator, otherwise // we have an unterminated trailing run, to handle downstream. return; } right++; if (run[count] < right) { // Corner case: the final run is not a terminator. This may happen // if a final run is an equals run, or there is a single-element run // at the end. Fix up by adding a proper terminator at the end. // Note that we terminate with (right + 1), incremented earlier. run[++count] = right; } // Determine alternation base for merge byte odd = 0; for (int n = 1; (n <<= 1) < count; odd ^= 1); // Use or create temporary array b for merging int[] b; // temp array; alternates with a int ao, bo; // array offsets from 'left' int blen = right - left; // space needed for b if (work == null || workLen < blen || workBase + blen > work.length) { work = new int[blen]; workBase = 0; } if (odd == 0) { System.arraycopy(a, left, work, workBase, blen); b = a; bo = 0; a = work; ao = workBase - left; } else { b = work; ao = 0; bo = workBase - left; } // Merging for (int last; count > 1; count = last) { for (int k = (last = 0) + 2; k <= count; k += 2) { int hi = run[k], mi = run[k - 1]; for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) { if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) { b[i + bo] = a[p++ + ao]; } else { b[i + bo] = a[q++ + ao]; } } run[++last] = hi; } if ((count & 1) != 0) { for (int i = right, lo = run[count - 1]; --i >= lo; b[i + bo] = a[i + ao] ); run[++last] = right; } int[] t = a; a = b; b = t; int o = ao; ao = bo; bo = o; } }
- binarySearch源码利用二分查找
private static int binarySearch0(long[] a, int fromIndex, int toIndex, long key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; long midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. }
6.数组常见异常（编译不报错，运行报错）
- 数组越界：ArrayIndexOutOfBoundsException
- 空指针：NullPointerException
public class ArrayExceptionTest { public static void main(String[] args) { //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]); // System.out.println("hello"); //2.2. 空指针异常：NullPointerException //情况一： // int[] arr1 = new int[]{1,2,3}; // 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()); } }