常用算法 Java语言描述

package com.linzhanghui.algorithm;

//二分法

public class OrdArray {
	private long[] a;
	private int nElems;
	
	public OrdArray(int max) {
		a = new long[max];
		nElems = 0;
	}
	
	public int size(){
		return nElems;
	}
	
	public int find(long searchKey) {
		int lowerBound = 0;
		int upperBound = nElems - 1;
		int curIn;
		while (true) {
			curIn = (lowerBound + upperBound) / 2;
			if(a[curIn] == searchKey)
				return curIn;
			else if(lowerBound > upperBound)
				return nElems;
			else {
				if(a[curIn] < searchKey)
					lowerBound = curIn + 1;
				else
					upperBound = curIn - 1;
			}
		}
	}
	
	public void insert(long value) {
		int j;
		for(j=0; j<nElems; j++)
			if(a[j] > value)
				break;
		for(int k=nElems; k>j; k--)
			a[k] = a[k-1];
		a[j] = value;
		nElems++;
	}
	
	public boolean delete(long value) {
		int j = find(value);
		if(j == nElems)
			return false;
		else {
			for(int k=j; k<nElems; k++)
				a[k] = a[k+1];
			nElems--;
			return true;
		}
	}
	public void display() {
		for(int j=0; j<nElems; j++)
			System.out.print(a[j] + " ");
		System.out.println(" ");
	}
}



package com.linzhanghui.algorithm;

public class OrderedApp {
	public static void main(String[] args) {
		int maxSize = 100;
		OrdArray arr = new OrdArray(maxSize);
		arr.insert(77);
		arr.insert(99);
		arr.insert(44);
		arr.insert(55);
		arr.insert(22);
		arr.insert(88);
		arr.insert(11);
		arr.insert(00);
		arr.insert(66);
		arr.insert(33);
		
		int searchKey = 55;
		if(arr.find(searchKey) != arr.size())
			System.out.println("找到" + searchKey);
		else
			System.out.println("找不到" + searchKey);
		
		arr.display();
		arr.delete(00);
		arr.delete(55);
		arr.delete(99);
		
		arr.display();
		
		
	}
}

package com.linzhanghui.algorithm;

/*
 * 冒泡排序，时间复杂度O(n^2)
 * 简单描述：
 * 			两两比较，比较出最大的一个数放在最后位置
 * 			剩下的继续比较
 * 
 */

public class ArrayBub {
	private long[] a;
	private int nElems;
	
	public ArrayBub(int max) {
		a = new long[max];
		nElems = 0;
	}
	
	public void insert(long value) {
		a[nElems] = value;
		nElems++;
	}
	
	public void display() {
		for(int j=0; j<nElems; j++)
			System.out.print(a[j] + " ");
		System.out.println("");
	}
	
	public void bubbleSort() {
		int out, in;
		for(out=nElems-1; out>1; out--)
			for(in=0;in<out;in++)
				if(a[in] > a[in+1])
					swap(in, in+1);
		
	}
	
	private void swap(int one,int two) {
		long temp = a[one];
		a[one] = a[two];
		a[two] = temp;		
	}
	
}


package com.linzhanghui.algorithm;

public class BubbleSortApp {
	public static void main(String[] args) {
		int maxSize = 100;
		ArrayBub arr = new ArrayBub(maxSize);
		
		arr.insert(77);
		arr.insert(99);
		arr.insert(44);
		arr.insert(55);
		arr.insert(22);
		arr.insert(88);
		arr.insert(11);
		arr.insert(00);
		arr.insert(66);
		arr.insert(33);
		
		arr.display();
		arr.bubbleSort();
		arr.display();
	}
}

  

package com.linzhanghui.algorithm;

/*随机生成1000个数字，并归并快速排序；
*/
public class ArrayIns {
	private long[] theArray;
	private int nElems;
	
	public ArrayIns(int max) {
		theArray = new long[max];
		nElems = 0;
	}
	
	public void insert(long value) {
		theArray[nElems] = value;
		nElems++;
	}
	
	public void display() {
		System.out.print("A=");
		for(int j=0; j<nElems; j++)
			System.out.print(theArray[j] + " ");
		System.out.println("");
	}
	
	public void quickSort() {
		recQuickSort(0, nElems-1);
	}
	
	public void recQuickSort(int left, int right) {
		if(right-left <= 0)
			return;
		else {
			long pivot = theArray[right];
			
			int partition = partitionIt(left, right, pivot);
			recQuickSort(left, partition-1);
			recQuickSort(partition+1, right);
		}
	}
	
	public int partitionIt(int left, int right, long pivot) {
		int leftPtr = left-1;
		int rightPtr = right;
		while(true) {
			while(theArray[++leftPtr] < pivot);
			while(rightPtr > 0 && theArray[--rightPtr] > pivot );
			if(leftPtr >= rightPtr)
				break;
			else
				swap(leftPtr, rightPtr);
		}
		swap(leftPtr, right);
		return leftPtr;
	}
	
	public void swap(int dex1, int dex2) {
		long temp = theArray[dex1];
		theArray[dex1] = theArray[dex2];
		theArray[dex2] = temp;
	}
}


package com.linzhanghui.algorithm;

public class QuickSort1App {
	public static void main(String[] args) {
		int maxSize = 1000;
		ArrayIns arr = new ArrayIns(maxSize);
		
		for(int j=0; j<maxSize; j++) {
			long n = (int)(java.lang.Math.random()*999);
			arr.insert(n);
		}
		arr.display();
		arr.quickSort();
		arr.display();
	}
}