javaSE学习-基础4-数组

Posted on | In |

数组介绍

数组是固定大小的存储同一种数据类型的多个元素的集合；

可以存放基本数据类型，也可以存放引用数据类型

数组可以给数组中元素标识

数组的定义

数组声明

  • 数据类型[] 数组名：int[] a;
  • 数据类型 数组名[]：int a[];

数组初始化

数组定义格式：

数据类型[] 数组名 = new 数据类型[数组长度];
或
数据类型[] 数组名 = {value1,value2,value3…};
数据类型[] 数组名 = new 数据类型[]{value1,value2,value3…};

用new操作符创建数组

可以先声明，后定义；也可以声明定义一起

1
2
3
4
5
//声明并且定义
int[] arr1 = new int[3];
//先声明数组变量arr2，后创建数组赋值给声明的arr2
double[] arr2;
arr2 = new double[10];
初始化

初始化：给系统开辟内存空间，并且给数组元素赋值

  • 动态初始化：必须指定数组长度，系统给数组分配初始值：new 数据类型[数组长度];
  • 静态初始化：仅指定数组中的元素初始值，长度由系统定义：{value1,value2,value3…};
1
2
3
4
5
6
7
8
//动态初始化
int[] a = new int[1];
a[0] = 1；
//静态初始化（两种写法）
int[] b1 = new int[]{1，2，3}；
int[] b2 = {4,5}；
//注意，不能动态和静态同时进行，如：
//int[] arr = new int[2]{4,5}；  写法错误！！！

获取数组元素

访问数组元素是通过数组的索引访问的

数组的每个元素有唯一的索引，从数组的第一个元素起，索引从0开始标识，一直到数组长度-1

数组长度：length方法获取数组的实际长度

访问数组方式：数组变量名[索引]（0<数组索引<数组长度-1）

注意，操作数组时，如果访问的数组索引不存在，超过了数组长度，则会报数组越界异常：ArrayIndexOutOfBoundsException

1
2
int[] arr = new int[2];
int a = arr[3];//访问的数组索引不存在：ArrayIndexOutOfBoundsException`

数组内存分配

数组定义内存分析

1
2
int a = 2;
int[] arr = new int[3];

new 数组内存分析如下：

javaSE_基础_数组_数组内存

对于分配内存：局部变量和变量名称放在栈中，new的对象放在堆中

堆分配内存时，对每一个new出来的对象都有一个地址，对象都会有默认值，如int的默认值是0，引用类型的默认值是null

栈中的变量在使用完之后会立即销毁；堆中的对象在使用完成之后就会成为垃圾，在java的垃圾回收器空闲时进行回收

数组之间赋值内存分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int[] arr1 = new int[3];
arr1[0] = 10;
arr1[1] = 20;
arr1[2] = 30;
int[] arr2 = new int[2];
arr2[0] = 100;
arr2[1] = 200;
int[] arr3 = arr1;
arr3[0] = 101;
arr3[3] = 301;
/*
  结果：arr1:[101，20，301]
  arr2:[100，200]
  arr3:[101，20，301]
*/

new 数组内存分析如下：

javaSE_基础_数组_数组赋值内存

分析：将数组arr1赋值给数组arr3，实际上是将arr1数组在堆中的对象地址赋值给arr3，所以arr3数组指向的地址是arr1的数组地址，于是arr3数组给数组元素赋值，改变的是堆中创建的0x001地址元素，所以最后arr3操作的是arr1创建的对象

数组常见异常

越界异常

数组下标越界异常：java.lang.IndexOutOfBoundsException

1
2
3
4
public static void main(String args[]){
	int[] arr={1,2,3};
	int a = arr[3];//arr数组的索引为0-2（数组最大索引为：数组长度-1），索引3不存在，报错
}

在上面的程序中，编译不报错，但在运行时会报java.lang.IndexOutOfBoundsException异常

原因：数组arr共有3个元素，元素下标分别为：0，1，2；但是变量a访问的是arr[3]，arr数组并没有下标为3的元素，超出了数组的范围，所以会报下标越界异常

空指针异常

空指针异常：java.lang.NullPointerException

调用了未经初始化的对象或者是不存在的对象 

1
2
3
4
5
public static void main(String args[]){
	int[] arr={1,2,3};
	arr = null;
	int a = arr[0];
}

以上程序会发生 java.lang.NullPointerException

原因：在第二句中程序将数组arr赋值为null，原先数组指向堆内存的数组{1,2,3}，现在arr指向null了，此时再通过数组下标访问数组，会报错

数组操作

数组的遍历

1
int[] arr={5,9,3,10,34,1};

for循环遍历

1
2
3
4
//遍历数组中所有元素
for(int i=0;i<arr.length;i++){
	System.out.print(arr[i] + ",");
}

for循环加强版遍历

1
2
3
for(int i:arr){
	System.out.print(i + ",");
}

使用Arrays工具类

1
System.out.println(Arrays.toString(arr));

求数组最值

思路

  1. 创建一个临时变量，存储比较出来的最大值
  2. 循环遍历数组，将数组每个元素与临时变量进行比较
  3. 比较后将较大值赋值给临时变量
  4. 比较完成，临时变量存储的就是数组最大值

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int getMaxNum1(int[] arr){
	//使用临时变量当做数组元素，获取数组最大值
	int maxNum = arr[0];
	for(int i=1;i<arr.length;i++){
		if(arr[i]>maxNum) maxNum = arr[i];
	}
	return maxNum;
}

public int getMaxNum2(int[] arr){
	//使用数组角标获取数组最大值
	int index = 0;
	for(int i=1;i<arr.length;i++){
		if(arr[i]>arr[index]) index = i;
	}
	return index;
}

数组排序算法

选择排序

基本原理

从待排序的一组数据中，选出最小的元素，按顺序放在数组的起始处或末尾处，直到所有的待排序数据都排完

如：给定元素数为n的数组arr

  1. 第一次，选定arr[0]数组值，与其余待排序数据arr[1]-arr[n-1]进行排序，选出最小元素并与arr[0]交换；此时arr[0]处的值为数组中最小值；
  2. 第二次，选定arr[1]数组值，与其余待排序数据arr[2]-arr[n-1]进行排序，选出最小元素并与arr[1]交换；此时arr[0]、arr[1]处的值为排序好的数组中最小的值；
  3. …
  4. 第i次，选定arr[i-1]数组值，与其余待排序数据arr[i]-arr[n-1]进行排序，选出最小元素并与arr[i]交换；此时arr[0]、arr[1]…arr[i]处的值为排序好的数组中最小的值；
  5. 第n-1次，选定arr[n-2]数组值，与待排序数据arr[n-1]进行排序，选出最小元素并与arr[i]交换；
选择排序代码实现
1
2
3
4
5
6
7
8
9
10
11
public static void selectionSort(int[] arr) {
	for (int x = 0; x < arr.length-1; x++) {
		for (int y = x+1; y < arr.length; y++) {
			if (arr[x] > arr[y]) {
				int temp = arr[x];
				arr[x] = arr[y];
				arr[y] = temp;
			}
		}
	}
}
选择排序图例

javaSE_基础_数组_选择排序

冒泡排序

选择排序代码实现
1
2
3
4
5
6
7
8
9
10
11
12
public static void bubbleSort(int[] arr) {
	for (int x = 0; x < arr.length-1; x++) {
		//-x：前一次比较出的结果不再进行比较   -1：避免y+1角标越界
		for (int y = 0; y < arr.length-x-1; y++) {
			if (arr[y] > arr[y+1]) {
				int temp = arr[y];
				arr[y] = arr[y+1];
				arr[y+1] = temp;
			}
		}
	}
}
冒泡排序图例

javaSE_基础_数组_冒泡排序

数组逆序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void reverse(int[] arr){
	for(int i=0;i<arr.length/2;i++){
		int temp = arr[i];
		arr[i] = arr[arr.length-1-x];
		arr[arr.length-1-x] = temp;
	}
}
//升级版
public void reverse02(int[] arr){
	for(int start = 0,end = arr.length-1;start<=end;start++,end--){
		int temp = arr[start];
		arr[start] = arr[end];
		arr[end] = temp;
	}
}

数组排序时间空间复杂度

排序法 最差时间复杂度 平均时间复杂度 稳定度 空间复杂度
选择排序 O(n2) O(n2) 稳定 O(1)
插入排序 O(n2) O(n2) 稳定 O(1)
冒泡排序 O(n2) O(n2) 稳定 O(1)
快速排序 O(n2) O(n*log2n) 不稳定 O(log2n)~O(n)
归并排序 O(n2) O(n*logn) 稳定 不一定
希尔排序 O(n*(logn)2) O(n*(logn)2) 不稳定 O(1)
堆排序 O(n*log2n) O(n*log2n) 不稳定 O(1)