1.数组基础1.什么是数组：
同一类型数据的集合，就是一个容器。
2.数组的好处：
可以自动为数组中的元素从零开始编号，方便操作这些数据。
3.格式： (一旦创建，必须明确长度)
格式1：
元素类型 [ ] 数组名 = new 元素类型 [元素个数即数组的长度]；
示例：int[] array =newint[5];
格式2：
元素类型 [ ] 数组名 = new元素类型 [ ]{元素1，元素2…}；
示例：int[] array =newint[]{1,2,3,4,5};
int[] array = {1,2,3,4,5};
数组有默认值：（不用初始化也可以使用，因为数组new int[5]是堆内存中的实例，堆内存中的实例都有默认的初始值）
如int[] array =newint[5];
System.out.PRitln(array[0]);
结果为0。
常见错误：
1.数组下标越界异常
int[] arr =newint[3];
System.out.println(arr[3]);
说明：编译不会报错，运行时报错。ArrayIndexOutOfBoundsException
当访问数组中不存在的下标时，就会报此异常。
2.空指针异常
int[] arr =newint[3];
arr=null;
System.ou.println(arr[0]);
说明：同样编译不会报错，运行时报错。NullPointeException
空指针异常，当引用型变量没有任何实体指向时，如果访问该变量，就会报此异常。
2.数组的常见操作1.遍历
打印数组中的所有元素
int[] arr = {43,6,645,43,3,2,1,54};for(inti=0; i<arr.length; i++) {
System.out.print("arr["+i+"]:"+arr[i]+";");}
2.获取最值
获取最大值
publicintgetMax(int[] arr){intmax = arr[0];//记录元素值for(inti = 1; i<arr.length; i++) {if(arr[i]>max){
max=arr[i];
}
}returnmax;
}
publicstaticintgetMax(int[] arr){intmaxIndex = 0;//记录元素下标for(inti = 1; i<arr.length; i++) {if(arr[i]>arr[maxIndex]){
arr[maxIndex]=arr[i];
}
}returnarr[maxIndex];
}
3.排序
javaAPI提供了排序的方法：java.util.Arrays.sort(arr);
1.选择排序法
原理：
代码：
publicvoidselectSort(int[] arr){inttemp;for(inti = 0; i<arr.length-1; i++) {for(intj = i+1; j<arr.length; j++) {if(arr[i]>arr[j]){//交换
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
}
2.冒泡排序法
原理：
代码：
publicstaticvoidbubblesort(int[] arr){inttemp;for(inti = 0; i<arr.length-1; i++) {for(intj = 0; j<arr.length-1-i; j++) {if(arr[j]>arr[j+1]){
temp=arr[j];
arr[j]= arr[j+1];
arr[j+1] =temp;
}
}
}
}
*封装交换代码：
//交换数组中两个元素的位置publicstaticvoidswap(int[] arr,inta,intb){inttemp =arr[a];
arr[a]=arr[b];
arr[b]=arr[a];
}
选择排序性能优化：
如上图所示，由于数组储存于堆内存中，重复多余的交换位置会带来多余的运算，所以想到定义中间变量来记录每次得到的最小值，再进行对应位置的交换，这样能减少交换的次数，提高效率。
代码：
publicstaticvoidselectSort_2(int[] arr){for(inti = 0; i<arr.length-1; i++) {intnum =arr[i];intindex =i;for(intj = i; j<arr.length; j++) {//内循环负责查找余下元素中的最小元素if(num>arr[j]){
num= arr[j];//用num记录最小的元素index = j;//用index记录最小元素的下标}
}
if(index!=i){
swap(arr, i, index);//交换最新要要排序的元素和查找到的最小元素位置
}}
}
4.查找
1.查找某元素第一次出现的位置
代码：
publicstaticintgetIndex(int[] arr ,intnum){for(inti = 0; i<arr.length; i++) {if(num==arr[i]){returni;
}
}return-1;
}
2.二分查找（折半查找）
**适用于有序数组
java API也提供了二分查找 。java.util.Arrays.binarySearch(int[],target);如果存在，返回下标，如果不存在，返回 -插入点-1
代码：
1.递归法：
publicstaticintfind(intarry[],inttarget,intbeginIndex,intendIndex) {if(beginIndex >endIndex) {return-1;
}intmiddleIndex = (beginIndex + endIndex) / 2;if(arry[middleIndex] ==target) {returnmiddleIndex;
}elseif(arry[middleIndex] <target) {
beginIndex= middleIndex + 1;
}elseendIndex= middleIndex - 1;returnfind(arry, target, beginIndex, endIndex);
}
2.while循环
1.
publicstaticinthalfSearch(int[] arr,inttarget){intmin = 0, max = arr.length-1, mid = (min + max)/2;while(arr[mid]!=target){//if(target>arr[mid])
min= mid + 1;elseif(target<arr[mid])
max= mid - 1;if(max<min){return-1;
}
mid= (min + max)/2;
}returnmid;
}
2.
publicstaticinthalfSearch(int[] arr,inttarget){intmin = 0, max = arr.length-1, mid;while(max>=min){
mid= (min + max)/2;if(target>arr[mid])
min= mid + 1;elseif(target<arr[mid])
max= mid - 1;elsereturnmid;
}return-1;
}
面试题：给定一个有序的数组，如果往数组中存储一个元素，并保证这个数组还是有序的，那么这个元素的存储的角标如何获取。
答案：直接使用上面的二分查找的函数，把返回-1改成返回min即可。
3.二维数组格式1：int[][] arr = new int[3][2];
定义了名称为arr的二维数组二维数组中有3个一维数组每一个一维数组有2个元素一维数组的名称分别是arr[0],arr[1],arr[2]给第一个一维数组1下标位赋值为78的写法是：arr[0][1]=78;格式2：int[][] arr = new int[3][];
二维数组中有3个一维数组每一个一维数组都是默认初始化值null可以对这3个一维数组分别进行初始化 arr[0] = new int[3];
arr[1] = new int[1];
arr[2] = new int[2];
格式3：int[][] arr = {{1,2},{3,4,5,6},{7,8,9}};
考虑如下代码：
int[][] arr =newint[3][2];
System.out.println(arr);//[[I@6dc57a92System.out.println(arr[0]);//[I@3ff23f8bSystem.out.println(arr[0][0]);//0int[][] arr2 =newint[3][];
System.out.println(arr2);//[[I@3929df79System.out.println(arr2[0]);//nullSystem.out.println(arr2[0][0]);//NullPointerException
说明：
第一种定义方式：在栈内存中保存一个arr的变量，用来记录二维数组在堆内存中的地址值。在堆内存中会创建一个二维数组，开辟三个连续的空间用来保存三个一维数组的首地址值。堆内存中还会有三个对应的一维数组的实体，每一个一维数组的每一个元素默认初始化值为0.
第二种定义方式：在栈内存中保存一个arr的变量，用来记录二维数组在堆内存中的地址值。在堆内存中会创建一个二维数组，开辟三个连续的空间默认初始化值为null。
二维数组的长度的获取：
二维数组的长度用arr.length获取，得到的是二维数组中一维数组的个数。如：
int [][] arr = new int[3][2];
arr.length的值为 3。
arr[0].length获取的是第一个一维数组的长度。
----------完----------
by_世界是我的床