数据结构与算法分析Java版第1章练习1.1

package ch01;

import java.util.Arrays;
import java.util.Random;

/**
 * 练习1.1 编写一个程序解决选择问题。令k = N/2。画出表格显示程序对于N种不同的值的运行时间。
 * @author yingli.zhang
 *
 */
public class EX01 {
	/**
	 * 第1种方案，先排序，然后直接返回第K大的数。 
	 */
	public static int selectKthNumber1(int a[], int k) {
		Arrays.sort(a);//从小到大排序, 内部实现是快速排序
		return a[a.length - k];
	}

	/**
	 * 第2种方案，先读数组前K个数，以递减顺序排序。接着，逐个读入后面元素比较并放入正确位置。
	 */
	public static int selectKthNumber2(int a[], int k) {
		int b[] = new int[k+1];
		Arrays.sort(a, 1, k+1);//从小到大
		for (int i = k, j = 1; j <= k; --i, ++j) {
			b[j] = a[i];//让b是a数组的逆序
		}

		for (int i = k+1; i < a.length; ++i) {
			if (a[i] <= b[k]) {
				continue;
			} else {
				int startPos = binarySearch0(b, 1, b.length, a[i]);
				if (startPos < 1) {					
					startPos = -startPos - 1;					
				}
				for (int m = k; m > startPos; --m) {
					b[m] = b[m - 1];
				}
				b[startPos] = a[i];
			}
		}
		return b[k];
	}

	/**
	 * 这个函数是从Arrays.java中摘抄过来的.并做了适当修改，让它按递减顺序进行查找。
	 */
	private static int binarySearch0(int[] a, int fromIndex, int toIndex,
            int key) {
		int low = fromIndex;
		int high = toIndex - 1;

		while (low <= high) {
			int mid = (low + high) >>> 1;
			int midVal = a[mid];

			if (midVal > key)
			low = mid + 1;
			else if (midVal < key)
			high = mid - 1;
			else
			return mid; // key found
		}
		return -(low + 1);  // key not found.
	}

	/**
	 * 第3种方法，通常的做法是利用快速排序的分割来定位
	 */
	public static int selectKthNumber3(int a[], int k) {
		return randomized_select(a, 1, a.length-1, k);
	}

	public static int randomized_select(int a[], int p, int r, int k) {
		if (p == r) {
			return a[p];
		}

		int q = partition(a, p, r);
		int i = q - p + 1;
		if (i == k) {
			return a[q];
		} else if (i < k) {
			return randomized_select(a, q + 1, r, k - i);
		} else {
			return randomized_select(a, p, q - 1, k);
		}

	}

	private static void quickSort(int a[], int p, int r) {
		if (p < r) {
			int q = partition(a, p, r);
			quickSort(a, p, q - 1);
			quickSort(a, q + 1, r);
		}
	}

	private static int partition(int a[], int p, int r) {
		int x = a[r];//pivot element
		int i = p - 1;
		for (int j = p; j <= r - 1; ++j) {
			if (a[j] >= x) {
				++i;
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
		int temp = a[r];
		a[r] = a[i+1];
		a[i+1] = temp;
		return i+1;
	}

	public static void main(String args[]) {			
		//先从10000个数据开始测试
		testCount(10000);
		testCount(100000);
		testCount(1000000);		
	}

	public static void testCount(final int COUNT) {
		Random rand = new Random(47);
		int a[] = new int[COUNT+1];
		int b[] = new int[COUNT+1];
		int c[] = new int[COUNT+1];
		//数组从索引1进行保存
		for (int i = 1; i <= COUNT; ++i) {
			a[i] = b[i] = c[i] = rand.nextInt(COUNT);
		}

		System.out.print("测试数据量("+COUNT+"): ");

		long time = System.currentTimeMillis();
		int result = selectKthNumber1(a, COUNT/2);		
		long time1 = System.currentTimeMillis();
		System.out.print(result+"("+(time1 - time) + "ms) ");

		result = selectKthNumber2(b, COUNT/2);
		long time2 = System.currentTimeMillis();
		System.out.print(result+"("+(time2 - time1) + "ms) ");

		result = selectKthNumber3(c, COUNT/2);
		long time3 = System.currentTimeMillis();
		System.out.println(result+"("+(time3 - time2) + "ms) ");
	}
}

输入为：

测试数据量(10000): 5011(3ms) 5011(18ms) 5011(1ms) 
测试数据量(100000): 50326(7ms) 50326(1580ms) 50326(1ms) 
测试数据量(1000000): 499548(91ms) 499548(115119ms) 499548(10ms) 

可见第3种算法最高效！！！