数据结构之数组（Array）详解
数组(Array)是由相同类型的元素(element)集合组成的固定长度(Size)的⼀种数据结构。在内存中是连续存储的，因此可以通过索引(Index)计算出某个元素的地址。
下⾯介绍都是已java为⽰例。对于没有详细了解过的相信有所收获。
基础知识
声明
type arrayName[] 或者 type[] arrayName。
如：
int arrInt[] 或者int[] arrInt
声明过程，只是告诉编译器: arrInt变量保存了⼀个int类型的数组。这个过程并没有分配内存。
new分配内存
分配内存需要通过new完成，同时指明类型和数组⼤⼩。
如：
int[] arrInt = new int[4];
数组中元素通过new分配后⾃动完成初始化，⼀般有⼏种：数字类型初始化为0(如：int/byte/short/long初始化为0，float/double初始化为0.0)，布尔型初始化为false(boolean 初始化为false),String或者其他对象类型初始化为null。
数组赋值也有两种
int[] arrInt = {1,3,5,7};
或
int[] arrInt = new int[4];
arrInt[0] = 1;
arrInt[1] = 3;
arrInt[2] = 5;
arrInt[3] = 7;
⽰意图如下：
多维数组
多维数组类似，即数组中的元素也是数组。如
int[][] arrInt = {{1,3,5},{2,4,6},{0,10,20}};
⽰意图如下：
数组特点
1. 索引(即下标) ⼀般从0开始，如java, C/C++。
2. 长度固定，在申请时长度固定。内存连续，在内存中则是申请⼀块连续的固定⼤⼩的空间。
3. 数组有⼀维数组和多维数组，数组元素可以是基本数据类型(Primitive)，也可以是对象引⽤(Reference)。
4. 随机访问，能够根据位置(下标)直接访问到元素。
注：
基本数据类型和对象引⽤数据类型
Primitive类型在java中有⼋种(具体内容后续整理)，Primitive类型在内存位置直接存⼊实际的值，引⽤对象的内存分配是在堆上(Heap)。
Primitive类型： boolean、char、byte、short、int、long、float、double
数组下标从0开始
数组变量引⽤指向了数组实际分配的连续内存的开始地址即第⼀个元素的地址(firstAdrr)，数组下标(index)即偏移量。假使每个元素⼤⼩为size.
那么数组元素位置计算：firstAdrr+index*size。
所以⼤部分语⾔数组下标是0开始。如果从1开始，计算位置时偏移量要减1操作，多了⼀步运算。
数组关联的Class对象
每个数组有⼀个关联的Class对象，与其他相同类型数组共享。
如：JNI中传递的参数经常看到：I表⽰int类型，[ 表⽰⼀个数组，[I 即int数组。
System.out.println("int array:" + new int[3].getClass());
System.out.println("int array:" + new int[3].getClass().getSuperclass());
System.out.println("String array:" + new String[3].getClass());
System.out.println("boolean array:" + new boolean[3].getClass());
结果为：
int array:class [I
int array super:class java.lang.Object
String array:class [Ljava.lang.String;
boolean array:class [Z
数组的拷贝
⼀维数组拷贝
⼀维数组的clone()是深度拷贝，拷贝了数组内的原始数据到新数组，⽽不是引⽤的复制。如：
int arrInt[] = {1,2,3};
int arrClone[] = arrInt.clone();
arrClone[1] = 5;
System.out.println(arrInt == arrClone);
for (int i = 0; i < arrClone.length; i++) {
System.out.println(arrInt[i]+" "+arrClone[i]);
}
结果为：
false
1 1
2 5
3 3
⽰意图如下：
多维数组拷贝
但多维数组则不是这样。如：
int arrInt[][] = {{1,2,3},{4,5,6}};
int[][] arrClone = arrInt.clone();
arrClone[0][1] = 50;
arrInt[0][1] = 100;
System.out.println(arrInt == arrClone);
System.out.println(arrInt[0] == arrClone[0]);
for (int i = 0; i < arrInt.length; i++) {
for (int j = 0; j < arrInt[i].length; j++) {
System.out.println(arrInt[i][j]+" "+arrClone[i][j]);
}
}
结果为：
false
true
1 1
100 100
3 3
4 4
5 5
6 6
⽰意图如下：
数组操作
插⼊
如图，向数组中插⼊⼀个元素，插⼊位置及之后的所有元素都需要向后挪动⼀位来完成插⼊操作。
如果数组已经满了(或者保证数组长度与元素个数⼀致)，则只能创建⼀个新的数组(长度增加的)来完成插⼊操作。
时间复杂度上，最好的是数组未满插⼊到最后只需直接插⼊，操作⼀次(O(1))。最坏是插⼊到第⼀位，需要操作N次。平均时间复杂度，(1 + 2 + ... + n) / n ~= O(n)
这是⼀个简单的插⼊⽰例。在现有数组的position位置插⼊value值，⾸先创建了⼀个新数组(长度+1)，依次填⼊数据。private int[] insertArr(int[] srcArr, int position, int value) {
if (position < 0 || position >= srcArr.length) return null;
int[] desArr = new int[srcArr.length+1];
System.arraycopy(srcArr, 0, desArr, 0, position);
desArr[position] = value;
System.arraycopy(srcArr, position, desArr, position+1, srcArr.length-position);
return desArr;
}
删除
类似插⼊的反向操作，删除某个元素，该位置及之后的所有元素向前挪⼀位。
如果要保证数组长度与数组元素个数⼀致，则也需要重新创建⼀个(长度减⼩的)数组来完成。
⽰意图：
查
查某⼀元素位置，只能⼀位位的遍历查了。
访问
array工艺详解
对于某位置的元素，直接读取或修改就可以了。数组是随机访问的。
时间复杂度总结
最后整理个表格，上述操作的时间复杂度⼤致如下，很容易理解就不详细解释了。
操作平均时间复杂度最坏条件时间复杂度
插⼊O(n)O(n)
删除O(n)O(n)
查O(n)O(n)
访问O(1)O(1)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。