分类目录归档:数据结构和算法

Shell Sort希尔排序Java实现

/**	希尔排序Java实现
 * 	by puladiao
 * 	http://blog.verypod.com
 */
 
import java.util.Random;

class ShellSort {
	int[] arr;

	public ShellSort(int num) {
		arr = new int[num];
	}
	
	// 将arr数组初始化为随机数数组
	public void randomArray() {
		Random rd = new Random();
		for (int i = 0; i < arr.length; i++) {
			arr[i] = rd.nextInt(arr.length * 2);
		}
	}

	// 将arr数组初始化为倒序数组
	public void reverseArray() {
		for (int i = 0; i < arr.length; i++) {
			arr[i] = arr.length - i;
		}
	}

	// 打印数组
	public void display() {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println("");
	}

	// 希尔排序
	public void shellSort() {
		int increment = 1;
		while (increment < arr.length) {
			increment = increment * 3 + 1;
		}
		increment = (increment - 1) / 3;
		while (increment >= 1) {
			for (int i = 0; i < increment; i++) {
				insertSort(i, increment);
			}
			display();
			increment = (increment - 1) / 3;
		}
	}
	
	// 插入排序,该方法会被希尔排序调用,该方法也可以直接使用,使用方法为 insertSort(0,1);
	// startIndex是排序起始索引,increment为增量,即元素之间的空间
	public void insertSort(int startIndex, int increment) {
		for (int i = startIndex + increment; i < arr.length; i += increment) {
			int j = i - increment;
			// System.out.println(i);
			int temp = arr[i];
			while (j >= startIndex && temp < arr[j]) {
				arr[j + increment] = arr[j];
				j -= increment;
			}
			arr[j + increment] = temp;
		}
	}
}

public class ShellSortApp {
	public static void main(String[] args) {
		ShellSort ss = new ShellSort(100);
		ss.reverseArray();
		ss.display();
		ss.shellSort();
		ss.display();
	}
}

Java数据结构和算法(第二版)第六章 编程作业

/**	Java数据结构和算法(第二版)第六章 编程作业
/**	Programming Projects in Chapter 6, Data Structure & Algorithms in Java 2nd Edition
 * 	by puladiao
 * 	http://blog.verypod.com
 */
// 6.3 递归解决N次方问题
public class Power {
	public static void main(String[] args) {
		System.out.println(doPower(2, 4));
	}

	public static long doPower(long base, long power) {
		long result = 1;
		if (power == 1) {
			result = base;
		} else {
			long factor = 1;
			if (power % 2 == 1) {
				factor = base;
			}
			power = power / 2;
			result = doPower(base, power) * doPower(base, power) * factor;
		}
		return result;
	}
}

// 6.4 递归解决背包问题
public class Knapsack {

	private static int[] arr = new int[] { 5, 6, 7, 8, 11 };

	public static void main(String[] args) {
		System.out.println(doKnapsack(arr.length-1, 20));
	}

	public static boolean doKnapsack(int n, int sum) {
		if (sum == 0) {
			return true;
		} 
		if (sum < 0 || (sum > 0 && n < 0)) {
			return false;
		} 
		if (doKnapsack(n - 1, sum - arr[n])) {
			System.out.println(arr[n]);
			return true;
		}
		System.out.printf("%d %d\n", arr[n],sum);
		return doKnapsack(n-1,sum);
	}
}

// 6.5 递归解决组合问题
public class Picker {
	static char[] arr = new char[] { 'A', 'B', 'C', 'D', 'E' };

	public static void main(String[] args) {
		Picker p = new Picker();
		p.pick(0, 5, 3, "");
	}

	// s为当前index,t为总数,n为组合数
	public void pick(int s,int t,int n,String str){
		if(n==1){
			for(int i=s;i<t+s;i++){
			System.out.println(str+arr[i]);
			}
		} else if(s<5) {
			//System.out.println(s);
			pick(s+1,t-1,n-1,str+arr[s]);
			pick(s+1,t-1,n,str);
		}
	}
}

Java解决Hanoi Tower(河内塔)问题

/**	Java解决Hanoi Tower(河内塔)问题
 * 	by puladiao
 * 	http://blog.verypod.com
 */
public class HanoiTower {

	public static void main(String[] args) {
		HanoiTower ht = new HanoiTower();
		ht.doMove(3, "a", "b", "c");
	}

	public void doMove(int number, String f, String i, String t) {
		if (number == 1) {
			System.out.printf("Move 1 from %s to %s\n", f, t);
		} else {
			doMove(number-1,f,t,i);
			System.out.printf("Move %d from %s to %s\n", number,f,t);
			doMove(number-1,i,f,t);
		}
	}
}

Java实现归并排序(MergeSort)

/**	归并排序Java实现
 *	MertSort using Java
 * 	by puladiao
 * 	http://blog.verypod.com
 */
class MergeSorter {
	private int nElems;
	private int[] theArray, workSpace;

	public MergeSorter(int[] theArray) {
		nElems = theArray.length;
		this.theArray = theArray;
	}

	public void MergeSort() {
		workSpace = new int[nElems];
		recMergeSort(0, nElems - 1);
	}

	private void recMergeSort(int lowerBound, int upperBound) {
		if (lowerBound == upperBound) {
			return;
		} else {
			int mid = (lowerBound + upperBound) / 2;
			recMergeSort(lowerBound, mid);
			recMergeSort(mid + 1, upperBound);
			merge(lowerBound, mid, upperBound);
		}
	}

	private void merge(int lowerBound, int mid, int upperBound) {
		int leftIndex, rightIndex, index;
		leftIndex = lowerBound;
		index = lowerBound;
		rightIndex = mid + 1;
		while (leftIndex <= mid && rightIndex <= upperBound) {
			if (theArray[leftIndex] < theArray[rightIndex]) {
				workSpace[index++] = theArray[leftIndex++];
			} else {
				workSpace[index++] = theArray[rightIndex++];
			}
		}
		while (leftIndex <= mid) {
			workSpace[index++] = theArray[leftIndex++];
		}
		while (rightIndex <= upperBound) {
			workSpace[index++] = theArray[rightIndex++];
		}
		for (int i = lowerBound; i <= upperBound; i++) {
			theArray[i] = workSpace[i];
		}
	}

	public void display() {
		for (int i = 0; i < nElems; i++) {
			System.out.print(theArray[i] + " ");
		}
		System.out.println("");
	}
}

public class MergeSortApp {
	public static void main(String[] args) {
		int[] arr = new int[] { 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		MergeSorter ms = new MergeSorter(arr);
		ms.display();
		ms.MergeSort();
		ms.display();
	}
}

Java数据结构和算法(第二版)第三章编程

/**	Java数据结构和算法(第二版)第三章 编程作业
/**	Programming Projects for Chapter 3 Simple Sorting, Data Structure & Algorithms in Java 2nd Edition
 * 	by puladiao
 * 	http://blog.verypod.com
 */
// 编程作业3.1
	public void bubbleSort() {
		int out_r, out_l, in;
		out_l = 0;

		for (out_r = nElems - 1; out_r > out_l; out_r--) {
			for (in = out_l; in < out_r; in++)
				if (a[in] > a[in + 1])
					swap(in, in + 1);
			for (in = out_r - 1; in > out_l; in--)
				if (a[in] < a[in - 1])
					swap(in - 1, in);
			out_l++;
			System.out.println(out_r + " " + out_l);
		}
	}
// 编程作业3.2
	public long median() {
		insertionSort();
		return a[(nElems - 1) / 2];
	}
// 编程作业3.3
	public void noDups() {
		insertionSort();
		int dupNum = 0;// 记录重复个数
		for (int i = 0; i < nElems; i++) {
			if (a[i] == a[i + dupNum + 1]) {
				dupNum++;
				nElems--;
			}
			if (dupNum>0){
				a[i + 1] = a[i + dupNum + 1];
			}
		}
	}
// 编程作业3.4
	public void oddEvenSort() {
		//待排序数组项目为奇数个或偶数个时分别对两个for循环进行控制,防止超出数组下标边界
		int factor1, factor2;
		if (nElems % 2 == 0) {
			factor1 = 0;
			factor2 = 1;
		} else {
			factor1 = 1;
			factor2 = 0;
		}
		boolean sorted = false;
		while (!sorted) {
			sorted = true;
			for (int i = 0; i < nElems - 1 - factor1; i += 2) {
				if (a[i] > a[i + 1]) {
					swap(i, i + 1);
					sorted = false;
				}
			}
			for (int i = 1; i < nElems - 1 - factor2; i += 2) {
				if (a[i] > a[i + 1]) {
					swap(i, i + 1);
					sorted = false;
				}
			}
		}
	}

Java实现冒泡排序、插入排序和选择排序

/**	冒泡排序、插入排序和选择排序的Java实现
 * 	Bubble Sort, Insertion Sort and Selection Sort using Java
 * 	by puladiao
 * 	http://blog.verypod.com
 */
import java.util.Random;

class ArrayBub {
	private int[] a;
	
	public ArrayBub(int num){
		a=new int[num];
		Random r=new Random();
		for (int i=0;i<a.length;i++){
			a[i]=r.nextInt(num);
		}
	}
	//冒泡排序
	public void bubbleSort() {
		int temp;
		for (int i = 0; i < a.length - 1; i++) {
			for (int j = 0; j < a.length - i - 1; j++) {
				if (a[j] > a[j + 1]) {
					temp = a[j + 1];
					a[j + 1] = a[j];
					a[j] = temp;
				}
			}
		}
	}
	//选择排序
	public void selectSort() {
		int temp;
		for (int i = 0; i < a.length - 1; i++) {
			int minIn = i;
			for (int j = i + 1; j < a.length; j++) {
				if (a[minIn] > a[j]) {
					minIn = j;
				}
			}
			temp = a[i];
			a[i] = a[minIn];
			a[minIn] = temp;
		}
	}
	//插入排序
	public void insertionSort() {
		for (int i = 1; i < a.length; i++) {
			int temp = a[i];
			int j = i;
			while (j > 0 && temp < a[j - 1]) {
				a[j] = a[j - 1];
				j--;
			}
			a[j] = temp;
		}
	}
	//输出当前的数组
	public void display()
	{
		for (int j = 0; j < a.length; j++)
			System.out.print(a[j] + " "); 
		System.out.println("");
	}
}

public class SortApp {
	public static void main(String[] args) {
		long start,end;
		//创建一个含有一万随即项的随机数组
		ArrayBub a = new ArrayBub(10000);
		start=System.currentTimeMillis();
		a.selectSort();
		//a.insertionSort();
		//a.bubbleSort();
		end=System.currentTimeMillis();
		//输出排序所用时间,单位为毫秒
		System.out.println(end-start);	
	}
}

可用于插入新元素的Binary Search

/**	Java数据结构和算法(第二版)第二章 编程作业
/**	Programming Projects for Chapter 2 Arrays, Data Structure & Algorithms in Java 2nd Edition
 * 	by puladiao
 * 	http://blog.verypod.com
 */
class OrdArray {
	private long[] a; // ref to array a
	private int nElems; // number of data items

	public OrdArray(int max) // constructor
	{
		a = new long[max]; // create array
		nElems = 0;
	}

	public int size() {
		return nElems;
	}

	public void insert(long value) // put element into array
	{
		int j = findIndex(value);
		display();
		for (int k = nElems; k > j; k--)
			// move bigger ones up
			a[k] = a[k - 1];
		a[j] = value; // insert it
		nElems++; // increment size
	}

	public int findIndex(long value) {
		int lowerBound = 0;
		int upperBound = nElems - 1;
		int currentIndex = 0;

		if (nElems == 0) {
			return 0;
		} else if (nElems == 1) {
			if (value > a[0])
				return 1;
			else
				return 0;
		}

		while (true) {
			currentIndex = (lowerBound + upperBound) / 2;
			if (a[currentIndex] == value) {
				return currentIndex;
			} else if (lowerBound == upperBound - 1 || lowerBound==upperBound) {
				if (value < a[lowerBound])
					return lowerBound;
				else
					return upperBound;
			} else if (a[currentIndex] < value) {
				lowerBound = currentIndex + 1;
			} else {
				upperBound = currentIndex - 1;
			}
		}
	}

	public boolean delete(long value) {
		int j = find(value);
		if (j == nElems) // can't find it
			return false;
		else // found it
		{
			for (int k = j; k < nElems; k++)
				// move bigger ones down
				a[k] = a[k + 1];
			nElems--; // decrement size
			return true;
		}
	}

	public void display() // displays array contents
	{
		for (int j = 0; j < nElems; j++)
			// for each element,
			System.out.print(a[j] + " "); // display it
		System.out.println("");
	}

}