一、数组的基础知识
-
数组的创建
在Java中把数组当做对象,不是基本数据类型来看待,所有创建数组要用new操作符。
例子:
|
@Test |
|
public void test1(){ |
|
int[] array; |
|
array = new int[10]; |
-
数组的初始化 动态初始化:
|
|
|
array[0] = 1; |
|
array[1] = 2; |
|
array[2] = 3; |
|
array[3] = 4; |
|
array[4] = 5; |
|
System.out.println(array); |
静态初始化:
|
//数组的静态初始化 |
|
int[] array2 = {1,2,3,4,5}; |
|
System.out.println(array2); |
-
数组数据项的访问 数组数据项的访问通过使用方括号中的下标数来访问。
|
|
|
System.out.println(array[1]); |
-
数组的length属性 length属性记录数组的长度。
|
|
|
System.out.println(array.length); |
-
数组的常用方法 继承父类Object中的方法
|
|
|
System.out.println(array.equals(array2)); |
|
array.clone(); |
|
array.hashCode(); |
|
array.toString(); |
|
System.out.println(array.getClass()); |
二、数组中数据的插入、查找、删除、遍历
-
可以将数组封装在一个类中,通过调用对象的方法来实现插入、删除等操作。这种用来存取数据对象的类也叫做容器类,不仅可以存取数据,还提供访问数据的方法和排序等操作的方法。
|
|
|
|
|
|
|
|
|
public class ArrayInt { |
|
private int[] a; |
|
public int num; |
|
|
|
public ArrayInt(int size){ |
|
a = new int[size]; |
|
num = 0; |
|
} |
|
|
|
|
|
public boolean find(int key){ |
|
int j; |
|
for (j = 0; j < num; j++) { |
|
if (a[j] == key) { |
|
break; |
|
} |
|
} |
|
if (j == num ){ |
|
return false; |
|
}else{ |
|
return true; |
|
} |
|
} |
|
|
|
|
|
public void insert(int data){ |
|
a[num] = data; |
|
num++; |
|
} |
|
|
|
|
|
public boolean delete(int value){ |
|
int j; |
|
for (j = 0; j < num; j++){ |
|
if (a[j] == value ){ |
|
break; |
|
} |
|
} |
|
if (j == num ){ |
|
return false; |
|
}else{ |
|
for(int i = j; i < num; i++){ |
|
a[i] = a[i+1] ; |
|
} |
|
num--; |
|
return true; |
|
} |
|
} |
|
|
|
|
|
public void show(){ |
|
System.out.println(a.length); |
|
for(int j = 0; j <num; j++){ |
|
System.out.println(a[j]); |
|
} |
|
} |
|
} |
三、有序数组中的查找
-
有序数组中有两种查找算法: 线形查找:依次向后,直到找到匹配项,当找到一个比目标数大的数就退出查找,时间复杂度(N); 二分查找:一开始设置变量low和higer分别指向数组第一个元素和最后一个元素,通过这两个变量可以确定查找目标值的范围; 在循环中,mid指向当前数组范围的中间值,可以查看mid指向的数据是否和目标值相等,是则找到了并返回mid下标值;循环中每一步将查找范围缩小一半,最终范围会小到无法分割。如果low比higer大,则范围不存在,查找停止。时间复杂度(log2 (N));
|
|
|
public int find(int key){ |
|
int low = 0; |
|
int high = num - 1; |
|
int mid; |
|
|
|
while(low <= high) { |
|
mid = (low + high)/2; |
|
if (a[mid] == key) { |
|
return mid; |
|
} else { |
|
if (a[mid] > key) { |
|
high = mid - 1; |
|
} else { |
|
low = mid + 1; |
|
} |
|
} |
|
} |
|
return -1; |
四、有序数组
-
同样按照上面将数组封装在一个类中,可以将有序数组封装成一个容器类,通过调用方法实现数据存取和查找、遍历操作。
|
public class Arraybina2 { |
|
|
|
private int[] array; |
|
public int num; |
|
|
|
public Arraybina2(int size) { |
|
array = new int[size]; |
|
num = 0; |
|
} |
|
|
|
|
|
public void insert(int value) { |
|
int j; |
|
for (j = 0; j < num; j++) { |
|
if (array[j] > value) { |
|
break; |
|
} |
|
} |
|
for (int i = num - 1 ; i >= j; i--) { |
|
array[i+1] = array[i]; |
|
} |
|
array[j] = value; |
|
num++; |
|
} |
|
|
|
|
|
public int find(int value) { |
|
int high = num - 1; |
|
int low = 0; |
|
int mid; |
|
|
|
while (low <= high) { |
|
mid = (low +high)/2; |
|
if (array[mid] == value) { |
|
return mid; |
|
} else { |
|
if (array[mid] > value) { |
|
high = mid - 1; |
|
} else { |
|
low = mid + 1; |
|
} |
|
} |
|
} |
|
return -1; |
|
} |
|
|
|
|
|
public boolean delete(int value) { |
|
int j = find(value); |
|
if (j == -1) { |
|
return false; |
|
} |
|
|
|
for (int i = j; i < num - 1; i++) { |
|
array[i] = array[i+1]; |
|
} |
|
num--; |
|
return true; |
|
} |
|
|
|
|
|
public void show() { |
|
for (int j = 0; j < num; j++) { |
|
System.out.println(array[j]); |
|
} |
|
} |
|
} |
-
测试代码:生成一个容量为10的有序数组,实现下面的操作
|
@Test |
|
public void test2(){ |
|
Arraybina2 a1 = new Arraybina2(10); |
|
a1.insert(10); |
|
a1.insert(22); |
|
a1.insert(16); |
|
a1.insert(1); |
|
a1.insert(160); |
|
|
|
a1.show(); |
|
System.out.println(a1.num); |
|
|
|
System.out.println(a1.find(16)); |
|
|
|
System.out.println(a1.delete(16)); |
|
a1.show(); |
|
} |
-
测试结果:
|
1 10 16 22 160 |
|
5 |
|
2 |
|
true |
|
1 10 22 160 |
由上面的结果可以看出这个类实现数组常见的操作,那么有序数组相比普通数组优点是什么呢?显然有序数组查找的速度比无序数组快,插入操作因为要右移部分数据项要慢一些,删除操作有序数组和无序数组都要左移数据项速度一样。
五、数组存在的缺陷
不论是有序数组还是无序数组,查找、插入、删除都不能满足同时都很快,存在这样的缺项。另一方面,创建数组时数组容量已经被确定了,扩容需要新建新的数组,复制旧数组中的数据,初始容量太大又会浪费存储空间,不太灵活。
原文:https://www.cnblogs.com/echoxiatiandefeng/p/14599748.html