java 数据结构学习之（一）数组

数组是应用最广泛的数据结构，也是最简单的数据结构，它有着结构简单，算法通俗易懂的优点。数组又分为有序数组和无序数组，我们通常用的都是无序数组。下面是这两种数组之间的区别

 

无序数组的优点：插入快，根据索引查找快。缺点：在未知数组位置的情况下查找慢，删除慢。

有序数组的优点：使用二分法查找快。缺点：插入数据和删除数据慢。因为插入数据要做排序操作。

 

综合以上，可以看出他们各自的使用场景，无序数组适合经常做插入操作和用索引访问的环境，而有序数组更趋向于随机查找。

 

下面是封装的一个数组类，扩展了了insert,delete,find方法,有许多不足之处，比如insert方法没有判断数组界限。懒得搞了。

 

package ArrayDemo;

public class HighArray {
	
	private int[] arr = null;
	private int nElement = 0;//当前数组的实际长度
	public HighArray(int size){
		this.arr = new int[size];
		this.nElement = 0;
	}
	
	/**查找指定元素是否在数组中存在，返回结果
	 * @param c
	 * @return
	 */
	public boolean find(int c){
		int i;
		for ( i = 0; i < nElement && arr[i]!=c; i++);
		return i != nElement;
	}
	
	/**插入
	 * @param c
	 */
	public void insert(int c){
		arr[nElement++] = c;
	}
	
	/**删除
	 * @param c
	 * @return
	 */
	public boolean delete(int c){
		int i;
		for ( i = 0; i < nElement && arr[i]!=c; i++);
		if(i!=nElement){
			nElement--;
			for (int j = i; j < nElement; j++) {
				arr[j] = arr[j+1];
			}
			return true;
		}else{
			return false;
		}
	}
	
	/**获取当前最大元素
	 * @return
	 */
	public int getMax(){
		if(nElement > 0){
			int max = arr[0];
			for (int i = 1; i < nElement; i++) {
				if(arr[i] > max)max = arr[i];
			}
			return max;
		}
		return -1;
	}
	
	/**删除并且返回最大元素
	 * @return
	 */
	public int removeMax(){
		if(nElement > 0){
			int max = arr[0];
			for (int i = 1; i < nElement; i++) {
				if(arr[i] > max)max = arr[i];
			}
			delete(max);
			return max;
		}
		return -1;
	}
	
	public void display(){
		for (int i = 0; i <nElement; i++) {
			System.out.println(arr[i]);
		}
	}
	
	/**
	 * 删除数组中存在的重复元素并缩小数组长度
	 */
	public void noDup(){
		int count  = 0;
		for (int i = 0; i < nElement; i++) {
			if(arr[i] != -1){// -1为空值的表现
				for (int j = 0; j < nElement; j++) {
					if(i!=j && arr[i] == arr[j]){
						arr[j] = -1;
						count++;
					}
				}
			}
			
		}
		if(count > 0){
			int j = 0;
			for (int i = 0; i < nElement; i++) {
				if(arr[i]!=-1){
					arr[j++] = arr[i];
				}
			}
			for (int k = j; k < nElement; k++) {
				arr[k] = 0;
			}
		}
	
		nElement-=count;
		
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		HighArray h = new HighArray(100);
			h.insert(7);
			h.insert(74);
			h.insert(74);
			h.insert(74);
			h.insert(89);
			h.insert(12);
			h.insert(8);
			h.noDup();
			h.display();
		//	h.delete(12);
			
	}
	
	
}

 

 上面是对一个无序数组做了一些封装和扩展。实现起来稍微简单点。下面介绍下有序数组的二分查找法。

 要实现二分查找法数组必须先满足两个条件1.必须采用顺序存储结构 2.必须按关键字大小有序排列。

二分查找法的基本原理就是：逐渐缩小查询范围，直到查找到元素或者查找不到此元素。它的优点是查找次数较线性查找（也就是按顺序查找所有元素）要高，而且当数组越大时查找次数的优势较线性查找越明显。下面是它查找不同数据量所需要的次数

 怎么样，是不是数据量越大查找次数的优势就越大，比如在10000里查找一个元素，线性查找需要的平均次数是1000/2 = 5000次， 而二分查找法的计算公式是以二为基数的对数 ，所谓对数就是指数的反函数 ，一般计算器的log函数就是以10为基数的对数，那么计算10000的二分查找法所需次数的公式就是log(10000) * 3.322 ，乘以3.322是因为要将该结果从10的基数转换成2的基数，这样下来四舍五入差不多就是所需次数了。结果是 13.288 取整就是14次。5000比14可想而知效率高了多少。ps:也可以这样计算log2(x) = log(x) / log(2) 

 

 

下面是二分法查找的基本步骤（假如是数组元素升序排序的）

1.将需查找元素和数组中间的元素比较，如果相等则返回，如果数组中间元素比需查找元素大则说明目标元素的位置在中间元素的前面，反之在后面。

2.通过步骤1，已经缩小了一半的范围，然后重复步骤1，直到找到元素或者找不到元素为止，就算找不到也最多就是查找Math.ceil(log(数据长度）* 3.322 )次。

 

 

这有点象我们平常的猜数游戏

java代码二分法实现 

 

public int bianrySearch(int[] arr,int searchKey){
		int lowerBound = 0, upperBound = arr.length - 1;
		while(lowerBound <= upperBound){
			int curIn = (lowerBound + upperBound)/2;
			if(arr[curIn] == searchKey){
				return curIn;
			}else if(arr[curIn] > searchKey){
				upperBound = curIn - 1;
			}else{
				lowerBound = curIn + 1;
			}
		}
		return  src.length;
	}

 看的不是很懂？没关系，看下面一张图您可能就明白了。

 

就是二分法这样逐渐缩小查询范围的原理来实现的。

 

下面是一个用二分法实现了find,delete,insert方法的数组类

 

package ArrayDemo;

public class OrderArray {
	private int[] arr = null;
	private int nElement = 0;
	public OrderArray(int size){
		this.arr = new int[size];
		this.nElement = 0;
	}
	
	public int find(int c){
		int lowerBound = 0, upperBound = nElement - 1;
		while(lowerBound <= upperBound){
			int middle = (lowerBound + upperBound)/2;
			if(arr[middle] == c){
				return middle;
			}else if(arr[middle] > c){
				upperBound = middle - 1;
			}else{
				lowerBound = middle + 1;
			}
		}
		return nElement;
	}
		
	private int doSearchRecursive(int lower,int upper,int c){
		while(lower <= upper){
			int middle = (lower + upper)/2;
			if(arr[middle]==c){
				return middle;
			}else if(arr[middle] < c){
				return doSearchRecursive(middle + 1, upper, c);
			}else{
				return doSearchRecursive(lower, middle -1, c);
			}
		}
		return nElement;
	}
	
	
	/**二分法递归实现
	 * @param c
	 * @return
	 */
	public int findRecursive(int c){
		return doSearchRecursive(0,arr.length - 1,c);
	}

	public void insert(int c){
		int lowerBound = 0,upperBound = nElement -1,max = nElement;
		while(lowerBound <= upperBound ){//用二分法查找在数组中第一个比c大的元素
			int middle = (lowerBound + upperBound)/2;
			if(arr[middle] == c){
				max = middle;
				break;
			}else if(arr[middle] > c){
				max = middle;
				upperBound = middle - 1;
			}else{
				lowerBound = middle + 1;
			}
		}
		//移动数组
		for (int i = nElement; i > max; i--) {
			arr[i] = arr[i - 1];
		}
		arr[max] = c;
		nElement++;
	}
	
	/**将两个有序的数组合并成一个有序的数组
	 * @param src1 
	 * @param src2
	 */
	public void mearge(int[] src1,int[] src2){
		int[] tar = new int[src1.length + src2.length];
		for (int i = 0,k=0,j=0; i < tar.length; i++) {
			if(j >= src2.length || (k < src1.length && src1[k] < src2[j])){
				tar[i] = src1[k++];
			}else{
				tar[i] = src2[j++];
			}
		}
		for (int i = 0; i < tar.length; i++) {
			System.out.println(tar[i]);
		}
		
	}
	public boolean delete(int c){
		int index = find(c);
		if(index != nElement--){
			for (int i = index; i < nElement; i++) {
				arr[i] = arr[i + 1];
			}
			return true;
		}else{
			return false;
		}
	}
	
	public int[] getArr(){
		return this.arr;
	}
	public void display(){
		for (int i = 0; i <nElement; i++) {
			System.out.println(arr[i]);
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		OrderArray h1 = new OrderArray(12);
		for (int i = 0; i < 12; i++) {
			h1.insert((int)(Math.random() * 1000));
		}
	//	h1.display();
		OrderArray h2 = new OrderArray(10);
		for (int i = 0; i < 10; i++) {
			h2.insert((int)(Math.random() * 1000));
		}
		h1.mearge(h1.getArr(), h2.getArr());
	//	System.out.println(h.find(34));
	}
	
}

 

这就是对数组的二分查找法基本的学习。