排序算法：求 长度为 n的 数组中，最大的 m个数

排序:数组 length=m，从其中中取出最大的 n 数字，n<=m

 

 

import java.util.Random;
import java.util.TreeSet;

/** 
 * 排序算法:数组 length=m，从其中中取出最大的 n 数字，n<=m
 * 思路：用 TreeSet 存放结果，可以自动排序，先取前100个放到 TreeSet，然后遍历其余的，如果大于 TreeSet 中最小的，则删除 TreeSet 中最小的值，并将新值放到 TreeSet 中，
 */
public class TopMax {
	/** 
	* 如果数字不在 treeset 里，则加入，并返回 true。 
	* 如果数字在 treeset 里，则不加入，并返回 false。 
	* @param ts 
	* @param newData 
	* @return 
	*/
	private static boolean doTop(TreeSet<Integer> ts, int newData) {
		if (ts.contains(newData)) {
			return false;
		}
		ts.remove(ts.first());
		ts.add(newData);
		return true;
	}

	private static void test(int numberCount, int topNum) {
		System.out.println("Sort begin...");

		long current = System.currentTimeMillis();

		int min = 0;

		int maxNumber = numberCount;
		Random random = new Random();
		random.setSeed(System.currentTimeMillis());
		TreeSet<Integer> ts = new TreeSet<Integer>();

		for (int i = 0; i < topNum; ++i) {
			int newData = random.nextInt(maxNumber);
			ts.add(newData);
		}
		min = ts.first();
		for (int i = topNum; i < numberCount; ++i) {
			int newData = random.nextInt(maxNumber);
			if (newData > min) {
				if (doTop(ts, newData)) {
					min = ts.first();
				}
			}
		}
		System.out.println(numberCount + " top " + topNum + " within " + (System.currentTimeMillis() - current) + " millseconds");
		System.out.println(ts);
		System.out.println("Sort end");
	}

	public static void main(String[] args) {
		test(100000000, 100);
	}
}