java数据结构-Arrays类

选择排序
选择排序是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。
复杂度
选择排序的交换操作介于0和(n − 1)次之间。选择排序的比较操作为n(n − 1) / 2次之间。选择排序的赋值操作介于0和3(n − 1)次之间。
比较次数O(n^2),比较次数与关键字的初始状态无关，总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。交换次数O(n),最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

顺序收缩
复杂度
假设X在list的中的概率为q, 则不在list中的概率为 1-q.
同时假设X在list中等于任何一个元素是等可能的,即 P(X=list[i]) = q/N
则平均复杂度为
A(N) = ｛从i=1到i=N累加｝P(X=list[i-1]) * i  +  P(X=out_list)*N
     = (q + 2*q + ... +N*q)/N + (1-q)/N
     = q(N+1)/2 +(1-q)/N
     = q/2 + N -qN/2

q=1,即X在list中的平均复杂度为(N+1)/2

二叉搜索
给定一个目标值, 二叉搜索算法会通过选择中心点进行搜索. 如果中心点的值与目标值匹配,那么搜索完成; 如果搜索中心点的值与目标值不匹配, 应为列表已经进故宫排序, 所以算法会继续 搜索列表的前半部分(下子列表)或列表的后半部分(上子列表).如果目标值小于当前中心点,那么通过选择下子表的中心点在这个子列表中搜索目标值, 否则选择上子表的中心点在这个子列表中搜索目标值 .通过查看越来越小的子列表

顺序搜索的lastIndexOf()
方法lastIndexOf()是顺序搜索的一个变化形式.其实参数包括一个数组array,整数fromIndex以及target的值.这个方法 指定一个索引处开始搜索数组中最后一个目标值, 如果查找到这样的目标值就返回其索引,否者就返回-1

双端顺序排序
选择排序的遍i(0<=i<=n-1)查找子列表{array[i],array[i+1],...,array[n-1]}的最小元素并将其与array[i]交换. 这种算法的变化形式是采用双端排序定位子列表的最小和最大元素, 并且这两个元素放在子列表的首尾.遍0定位子列表{array[0],array[1],...,array[n-1]}中的最小和最大元素,并且将两个元素放在索引0,n-1处.继续这个过程,直至子列表最左端变得等于或大于最右端的索引.双端的排序会进行n/2遍

冒泡排序
　冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再大于第2个数），将小数放前，大数放后，一直比较到最小数前的一对相邻数，将小数放前，大数放后，第二趟结束，在倒数第二个数中得到一个新的最小数。如此下去，直至最终完成排序。
　　由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。
　　用二重循环实现，外循环变量设为i，内循环变量设为j。外循环重复9次，内循环依次重复 9，8，...，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,...,9，对于每一个i, j的值依次为1,2,...10-i。
复杂度
若记录序列的初始状态为"正序"，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次比较，且不移动记录；反之，若记录序列的初始状态为"逆序"，则需进行n(n-1)/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。

package ds.util;

import test.ds.util.ArraysUtil;

/**
 *数组工具, 选择排序
 * 
 * @author liao
 * 
 */
public class Arrays {

	/**
	 * 选择排序: 从索引0处开始并确定列表中最小的元素位置, 交换这个最小元素与array[0]中元素的位置, 该步骤将最小的元素放在array[0],
	 * 列表中的其他元素则保持不变. 排序处理继续前进至索引1, 并且选择确定子列表array[1]...array[n-1]中最小元素的位置,
	 * 交换这个最小元素与array[1]的位. 从位置2到n-2处, 重复进行类似的排序处理.因为前面所有的交换已经使array[n-1]的元素最大了,
	 * 所以在位置n-1处不会发生任何选择操作
	 * 
	 * @param arr
	 *            被排序的数组
	 */
	public static void selectionSort(int[] arr) {

		int n = arr.length, smallIndex = 0;
		for (int i = 0; i < n; i++) { // 遍历array数组
			smallIndex = i;
			for (int j = i + 1; j < n; j++)
				if (arr[smallIndex] > arr[j]) // 选择最小的索引j
					smallIndex = j;
			// if (smallIndex != i) {
			exchange(arr, i, smallIndex);// 交换array[i]与 min(array[i+1,..,n])
			// }
		}
	}

	/**
	 * 用于数组的最简单搜索算法就是顺序搜索(sequential search).顺序收缩算法首先确定一个目标值以及定义的子列表范围的索引.
	 * 这种算法逐项扫描子类表的元素,从而找出头一个出现的target项匹配的元素.如果搜索成功,那么算法会返回匹配的索引. 如果扫描在
	 * 查找到target之前到达索引last, 那么搜索不成功, 在这种情况下, 顺序搜索算法方法返回-1
	 * 
	 * @param arr
	 *            搜索的数组, 范围[first,last)
	 * @param first
	 *            开始索引处
	 * @param last
	 *            结束索引处
	 * @param target
	 *            要搜索的目标
	 * @return 如果搜索成功,那么算法会返回匹配的索引. 如果扫描在查找到target之前到达索引last, 那么搜索不成功, 在这种情况下,
	 *         顺序搜索算法方法返回-1
	 */
	public static int seqSearch(int[] arr, int first, int last, int target) {
		for (int i = first; i < last; i++)
			if (arr[i] == target)
				return i;

		return -1;
	}

	/**
	 * 给定一个目标值, 二叉搜索算法会通过选择中心点进行搜索. 如果中心点的值与目标值匹配,那么搜索完成; 如果搜索中心点的值与目标值不匹配,
	 * 应为列表已经进故宫排序, 所以算法会继续 搜索列表的前半部分(下子列表)或列表的后半部分(上子列表).如果目标值小于当前中心点,
	 * 那么通过选择下子表的中心点在这个子列表中搜索目标值, 否则选择上子表的中心点在这个子列表中搜索目标值 .通过查看越来越小的子列表
	 * 
	 * @param arr
	 *            搜索的数组, 范围[first,last)
	 * @param first
	 *            开始索引处
	 * @param last
	 *            结束索引处
	 * @param target
	 *            要搜索的目标
	 * @return 如果找到这个中心点,则返回数组的索引; 否则,返回-1
	 */
	public static int binSearch(int[] arr, int first, int last, int target) {
		int mid, midVal;
		while (first < last) {
			mid = (first + last) / 2;
			midVal = arr[mid];

			if (target == midVal)
				return mid;
			else if (target < midVal)
				last = mid;
			else
				first = mid + 1;
		}
		return -1;
	}

	/**
	 * 方法lastIndexOf()是顺序搜索的一个变化形式.其实参数包括一个数组array,整数fromIndex以及target的值.这个方法
	 * 指定一个索引处开始搜索数组中最后一个目标值, 如果查找到这样的目标值就返回其索引,否者就返回-1
	 * 
	 * @param arr
	 *            搜索的数组, 范围[from,n)
	 * @param fromIndex
	 * @param target
	 *            要搜索的目标
	 * @return 在数组array中查找的最后一个target
	 */
	public static int lastIndexOf(int[] arr, int fromIndex, int target) {
		int n = arr.length;
		for (int i = n - 1; i >= fromIndex; i--)
			if (arr[i] == target)
				return i;

		return -1;
	}

	/*
	 * 本方法和上面的lastIndexOf()比较: array 10000个0-100随机数,fromindex为0,target为50
	 * 测试结果0.0010(上方法) 0.0040(本方法)
	 * 
	 * public static int lastIndexOf2(int[] arr, int fromIndex, int target) {
	 * int n = arr.length, index = -1; for (int i = 0; i < n; i++) if (arr[i] ==
	 * target) index = i;
	 * 
	 * return index;
	 * 
	 * }
	 */

	/**
	 * 如果目标值在数组出现一次,那么方法isUnique()返回true.实现这个算法时,需要使用seqSearch()方法在整个索引返回[0,
	 * array.length)内
	 * 判断是否存在目标值,如果seqSearch方法返回n!=-1,那么在返回调用seqSearch索引范围[n+1,array
	 * .length)内判断是否存在另外一个值:
	 * 
	 * @param arr
	 *            搜索的数组
	 * @param target
	 *            要搜索的目标
	 * @return 判断array数组中是否存在target是唯一存在的
	 */
	public static boolean isUnique(int[] arr, int target) {
		int length = arr.length;
		int n = seqSearch(arr, 0, length, target);
		if (n == -1)
			return false;
		int m = seqSearch(arr, n + 1, length, target);
		if (m == -1)
			return true;
		return false;
	}

	/**
	 * numUnique()方法返回一个指示数组中独特数据的个数的整数, 通过调用数组元素的isUnique()方法来实现numUnique()方法
	 * 
	 * @param arr
	 * @return 显示数组array中存在唯一数据的个数
	 */
	public static int numUnique(int[] arr) { // 此方的效率是非常高的,测试数据:array大小10000,测试时间1254889120422-1254889120401(微秒)
		int num = 0;
		for (int i = 0; i < arr.length; i++)
			if (isUnique(arr, arr[i]))
				num++;

		return num;
	}

	/**
	 * 选择排序的遍i(0<=i<=n-1)查找子列表{array[i],array[i+1],...,array[n-1]}的最小元素并将其与array
	 * [i]交换. 这种算法的变化形式是采用双端排序定位子列表的最小和最大元素,
	 * 并且这两个元素放在子列表的首尾.遍0定位子列表{array[0],array[1],...,array[n-1]}
	 * 中的最小和最大元素,并且将两个元素放在索引0,n-1处.继续这个过程,直至子列表最左端变得等于或大于最右端的索引.双端的排序会进行n/2遍
	 * 
	 * @param arr
	 */
	public static void doSelectionSort(int[] arr) {
		int first = 0, last = arr.length - 1, minIndex, maxIndex, min, max;
		while (first < last) {
			min = arr[first];
			max = arr[last];
			minIndex = first;
			maxIndex = last;

			for (int i = first; i <= last; i++) {
				if (min > arr[i]) {
					min = arr[i];
					minIndex = i;
				}
				if (max < arr[i]) {
					max = arr[i];
					maxIndex = i;
				}
			}
			exchange(arr, first, last, minIndex, maxIndex);
			first++;
			last--;
		}
	}

	/**
	 * 交换排序是另外一种基本的排序算法, 该算法重复扫描数组和交换元素, 直至列表按升序排列. 在较小元素的颠倒时,
	 * 这种算法会交换一对元素
	 * 
	 * @param arr
	 *            被排序的数组
	 */
	public static void exchageSort(int[] arr) {
		int length = arr.length;
		for (int i = 0; i < length; i++)
			for (int j = i + 1; j < length; j++)
				if (arr[i] > arr[j])
					exchange(arr, i, j);
	}

	/**
	 * 在对数组的多次扫描期间, 某个标记表明是否发生任何本地活动. 每个遍都会比较邻近的元素,
	 *  并且会在第一个元素大于第二个元素时发生交换元素, 最大的会"冒泡"至数组的顶端. 随后的各个遍将数组从后到前进行排列, 
	 *  冒泡排序需要至多n-1个遍, 如果标记表明期间没有发生任何交换,那么排序处理终止
	 * @param arr  被排序的数组
	 */
	public static void bubbleSort(int[] arr){
		int length = arr.length;
		boolean isExchange;
		for (int i = 0; i < length-1; i++) {	//冒泡排序需要至多n-1个遍
			isExchange=false;
			for (int j = 0; j < length-i-1; j++)  //最大的会"冒泡"至数组的顶端
				if (arr[j]>arr[j+1]) {
					exchange(arr, j, j+1);
					isExchange=true;
				}
			if (!isExchange) 
				return;
		}
	}
	
	/*
	 * 定义一个私有方法,交换array数组两个元素,索引aIndex和索引bIndex交换
	 */
	private static void exchange(int[] arr, int aIndex, int bIndex) {
		int temp = arr[aIndex];
		arr[aIndex] = arr[bIndex];
		arr[bIndex] = temp;
	}

	/*
	 * 定义一个私有方法,交换array数组两个元素,索引aIndex和索引toAIndex交换,索引bIndex和索引toBIndex交换
	 */
	private static void exchange(int[] arr, int aIndex, int bIndex,
			int toAIndex, int toBIndex) {
		exchange(arr, aIndex, toAIndex);
		if (aIndex == toBIndex) // 如果aIndex等于bIndex
								// 下面一次交换就会出现,"移位现象"(本来toBIndex要和toAIndex交换的结果和toAIndex交换了),这是因为以为的先后顺序所致的
			toBIndex = toAIndex;
		exchange(arr, bIndex, toBIndex);
	}

	/**
	 * 判断数组是否升序排列
	 * 
	 * @param arr
	 *            验证的数组
	 * @return 如果按升序排列,返回true;否则,返回false.
	 */
	public static boolean isArrayASC(int[] arr) {
		int length = arr.length;
		for (int i = 0; i < length; i++) {
			for (int j = i + 1; j < length; j++) {
				if (arr[i] > arr[j]) {
					return false;
				}
			}
		}
		return true;
	}

	public static void main(String[] args) {
		int[] arrVals = { 3, 1, 5, 1, 9, 5, 7, 2, 3, 8, 4 };
		ArraysUtil.printArrays(arrVals);
		exchange(arrVals, 0, 1);
		ArraysUtil.printArrays(arrVals);
	}

}

统计时间类工具类:

/*
 * @(#)Timing.java
 */
package ds.time;

/**
 * An instance of the class acts like a stop watch for measuring the time
 * required to execute a process; time is measured in seconds from start to stop
 * using millisecond intervals from the system clock.
 */
public class Timing {
	// starting and ending time measured in milliseconds
	private long startTime, stopTime;

	/**
	 * Creates an instance with default values 0 for both the start time and and
	 * the stop time.
	 */
	public Timing() {
		startTime = stopTime = 0;
	}

	/**
	 * Establishes a starting time for the process by recording the current
	 * millisecond time on the system clock
	 */
	public void start() {
		startTime = System.currentTimeMillis();
	}

	/**
	 * Establishes a time in seconds by computing the interval from the start
	 * time to the current time on the system clock.
	 * 
	 * @return interval of time from start to stop measured in seconds.
	 */
	public double stop() {
		stopTime = System.currentTimeMillis();

		return (stopTime - startTime) / 1000.0;
	}
	public static void main(String[] args) {
		Timing time=new Timing();
		time.start();
		System.out.println(time.stop());
	}
}

测试工具类

package test.ds.util;

import java.util.Random;

/**
 * @author liao
 *
 */
public class ArraysUtil {
	/**
	 * 工具方法: 产生随机大小为size从0-100的数组
	 * @param size
	 * @return
	 */
	public static int[] getRandomInts(int size) {
		int[] arr = new int[size];
		Random rand = new Random();

		for (int i = 0; i < size; i++) {
			arr[i] = rand.nextInt(100);
		}
		return arr;
	}
	

	/**
	 * 工具方法: 输出数组到控制台
	 * @param arr
	 */
	public static void printArrays(int[] arr){
		System.out.println("输出的数组是: "+arr);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
		
	}
}

JUnit测试类:

package test.ds.util;

import ds.time.Timing;
import ds.util.Arrays;
import junit.framework.TestCase;

public class ArraysTestCase extends TestCase {
	public void seqSearch() {
		int[] arrVals = ArraysUtil.getRandomInts(10);
		ArraysUtil.printArrays(arrVals);
		System.out.println(Arrays.seqSearch(arrVals, 1, 10, arrVals[9]));
	}

	public void selectionSort() {
		int[] arrVals = ArraysUtil.getRandomInts(10);
		ArraysUtil.printArrays(arrVals);
		Timing time = new Timing();
		time.start();
		Arrays.selectionSort(arrVals);
		System.out.println(time.stop());

		ArraysUtil.printArrays(arrVals);
	}

	public void binSearch() {
		int[] arrVals = ArraysUtil.getRandomInts(10);
		Arrays.selectionSort(arrVals);// 排序, 升序
		ArraysUtil.printArrays(arrVals);

		System.out.println(Arrays.binSearch(arrVals, 4, 7, arrVals[8]));

	}

	public void lastIndexOf() {
		int[] arrVals = { 2, 5, 3, 5, 4, 7, 5, 1, 8, 9 };
		ArraysUtil.printArrays(arrVals);

		System.out.println(Arrays.lastIndexOf(arrVals, 0, 5));
		System.out.println(Arrays.lastIndexOf(arrVals, 4, 5));
	}

	public void isUnique() {
		int[] arrVals = { 3, 1, 5, 1, 9, 5, 7, 2, 3, 8, 4 };
		ArraysUtil.printArrays(arrVals);

		for (int i = 0; i < arrVals.length; i++) {
			int val = arrVals[i];
			System.out.println("arr: " + val + " : "
					+ Arrays.isUnique(arrVals, val));
		}
	}

	public void numUnique() {
		Timing time = new Timing();
		int[] arrVals = ArraysUtil.getRandomInts(10000);

		time.start();
		System.out.println(Arrays.numUnique(arrVals));
		time.stop();
		System.out.println();
	}

	public void deSelectionSort() {
//		int[] arrVals = { 1, 49, 6, 7, 6, 54, 9, 97, 18, 45 };
//		int[] arrVals = { 1, 6, 49, 7, 45, 18, 9, 6, 54, 97 };
		int[] arrVals = ArraysUtil.getRandomInts(10000);
//		ArraysUtil.printArrays(arrVals);
		Timing time = new Timing();
		time.start();
		
		Arrays.doSelectionSort(arrVals);
		
		System.out.println(time.stop());
		System.out.println(Arrays.isArrayASC(arrVals));
	}
	public void exchangeSort(){
		int[] arrVals = ArraysUtil.getRandomInts(10);
		ArraysUtil.printArrays(arrVals);
		Timing time = new Timing();
		time.start();
		
		Arrays.exchageSort(arrVals);
		
		System.out.println(time.stop());
		ArraysUtil.printArrays(arrVals);
		System.out.println(Arrays.isArrayASC(arrVals));
	}
	public void bubbleSort(){
		Timing time = new Timing();
		int[] arrVals ={35,10,40,15};
		ArraysUtil.printArrays(arrVals);
		time.start();
		
		Arrays.bubbleSort(arrVals);
		
		time.stop();
		ArraysUtil.printArrays(arrVals);
		System.out.println();
	}
}