Java数据结构和算法-2-数组-自定义封装一个数组操作类（2）

Dear 丶 2022-03-10 07:52 119阅读 0赞

继续来写我们的数组操作类封装，前面写了新增元素和查找元素，增删改查是我们必须要封装的数组类方法。本篇来练习数组的删除，元素翻转，和其他方法的封装。

**1、数组删除元素**

根据索引index去删除元素，原理是这样的。假如有一个数组\[12,36,81\]，我要删除索引为1的元素也就是36，结果数组为\[12,81\]。这个规律就是，删除元素36，后面一个元素81需要前移到原来36的位置，而且数组的长度为原来长度减去1.

/**
    	 * 删除元素: 根据索引，删除元素。后面索引对应元素往前移，元素个数减1
    	 * 同样要考虑索引异界的异常
    	 */
    	public void delete(int index) {
    		if(index >= elements || index < 0) {
    			throw new ArrayIndexOutOfBoundsException();
    		} else {
    			arr[index] = arr[index+1];
    		}
    		elements--;
    	}

测试代码

package array;
    
    public class TestMyArray {
    
    	public static void main(String[] args) {
    		MyArray arr = new MyArray(3);
    		arr.insert(13);
    		arr.insert(24);
    		arr.insert(96);
            
    		arr.print();
    		arr.delete(1);
    		arr.print();
    	}
    }

运行结果：

[13 24 96]
    [13 96]

**2、修改元素的值**

下面的方法是根据索引，去修改元素的值。所以修改元素的方法就有两个参数，第一个参数是索引，第二个参数是要修改成新的值。

/**
    	 * 更新数据：根据索引修改元素的值
    	 */
    	public void change(int index, long value) {
    		if(index >= elements || index < 0) {
    			throw new ArrayIndexOutOfBoundsException();
    		} else {
    			arr[index] = value;
    		}
    	}

测试类

测试结果：这里由于有索引作为参数，但是我没有测试异常的场景。

[13 24 96]
    [13 48 96]

**3、有序数组**

什么是有序数组呢，就是数组中元素是按照从小到大或者从大到小的顺序排列，这个就是有序数组。有序数组，我们主要是通过插入元素来实现，当前我们还没有学排序相关算法。通过有序数组的创建，来引出排序算法。

为了和前面封装好的MyArray类区分开来，我这里复制了一个MyArray.java，然后新命名为MyOrderArray.java.

package array;
    
    public class MyOrderArray {
    	private long[] arr;
    	// 表示有效元素的长度
    	private int elements;
    	
    	public MyOrderArray() {
    		arr = new long[50];
    	}
    	
    	public MyOrderArray(int maxsize) {
    		arr = new long[maxsize];
    	}
    	
    	/**
    	 * 添加数据
    	 */
    	public void insert(long value) {
    		int i;
    		for (i = 0; i < elements; i++) {
    			if( arr[i] > value) {
    				break;
    			}
    		}
    		
    		for (int j = elements; j > i; j--) {
    			arr[j] = arr[j - 1];
    		}
    		arr[i] = value;
    		elements++;
    	}
    	
    	/**
    	 * 打印数组内容
    	 */
    	public void print() {
    		System.out.print("[");
    		for (int i = 0; i < elements; i++) {
    			if(i == elements - 1) {
    				System.out.print(arr[i]);
    			}else {
    				System.out.print(arr[i] + " ");
    			}
    		}
    		System.out.println("]");
    	}
    	
    }

重点看insert里面的j循环这段代码，思考下为什么要从数组后面操作，还有arr\[i\]>value这个判断。

测试代码，看看新Insert的数组会不会自动排序。

运行结果

[13 24 96]

4、二分查找算法

前面我们查找元素，是使用for循环，i从索引0开始一直查找到最后一个元素，查找到了就break，这种查找元素的方法就叫做线性查找算法。显然，这种线性查找效率并不高。接下来，我们学习二分查找。什么是二分查找呢？首先从中间开始，就是查找一次可以缩小一半的查找范围。再查找一次，再缩小一半范围，直到查找到。显然这个效率比线性查找至少高一倍。

/**
    	 * 二分法查找数据
    	 */
    	public int binarySearch(long value) {
    		//定义中间索引初始位置
    		int middle = 0;
    		//定义最左边的也是为0开始
    		int low = 0;
    		//定义最右边为数组长度
    		int pow = elements;
    		
    		//来一个死循环
    		while(true) {
    			middle = (low + pow) / 2;
    			//刚刚中间这个数就是要查找的，运气不错，查找一次就找到
    			if(arr[middle] == value) {
    				return middle;
    			} else if ( low > pow) {
    				return -1; //查找出问题，返回-1
    			} else {
    				//接下来判断元素是在左半部分还是右半部分
    				if (arr[middle] > value) {
    					//如果中间元素大于要查找的，那么在左半部分
    					pow = middle - 1; // 这个地方要思考
    				} else {
    					//否则，要查找的数在右半部分
    					low = middle + 1; //这个地方要思考下
    				}
    			}
    		}
    	}

测试类

package array;
    
    public class TestMyArray {
    
    	public static void main(String[] args) {
    		MyOrderArray arr = new MyOrderArray();
    		arr.insert(13);
    		arr.insert(24);
    		arr.insert(96);
    		arr.insert(48);
    		arr.insert(56);
    		arr.insert(31);
            
    		arr.print();
    		//注意二分查找前提是 有序数组
    		System.out.println(arr.binarySearch(24));
    		System.out.println(arr.binarySearch(96));
    		System.out.println(arr.binarySearch(200));
    		
    	}
    }

测试结果：

[13 24 31 48 56 96]
    1
    5
    -1

从结果来看，二分查找方法没有问题。

我们通过两篇文章，先是复习数组的基本知识，然后封装了数组的增删改查的方法，最后引出了线性查找算法和二分查找算法。这两个都是排序的算法。下一篇学习简单排序算法。