本文共 3628 字，大约阅读时间需要 12 分钟。

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

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;		}	}

测试类

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.change(1, 48);;		arr.print();	}}

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

[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的数组会不会自动排序。

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.print();	}}

运行结果

[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]15-1

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

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

转载地址：http://vkows.baihongyu.com/