目錄
- 一、陣列的基礎知識
- 二、陣列中資料的插入、查找、洗掉、遍歷
- 三、有序陣列中的查找
- 四、有序陣列
- 五、陣列存在的缺陷
一、陣列的基礎知識
- 陣列的創建
在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]);//2
- 陣列的length屬性
length屬性記錄陣列的長度，
//陣列的length屬性
System.out.println(array.length);//10
- 陣列的常用方法
繼承父類Object中的方法
//陣列的常用方法
System.out.println(array.equals(array2));
array.clone();
array.hashCode();
array.toString();
System.out.println(array.getClass());
二、陣列中資料的插入、查找、洗掉、遍歷
- 可以將陣列封裝在一個類中，通過呼叫物件的方法來實作插入、洗掉等操作，這種用來存取資料物件的類也叫做容器類，不僅可以存取資料，還提供訪問資料的方法和排序等操作的方法，
/**
* @author vetstein
* @creat 2021-03-2021/3/31-3:42
*/
public class ArrayInt {
private int[] a;//定義陣列
public int num;//記錄資料項長度
public ArrayInt(int size){
a = new int[size];//Java中陣列的長度可以在運行時再確定
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) { //找到回傳mid下標值
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; //初始化陣列長度為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; //沒找到回傳-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.uj5u.com/houduan/279500.html
標籤：Java
下一篇：Mybatis的日志工廠