100w个数字，找出最小的10个数字

思想：维护一个10个数字的有序目标数组（从大到小），依次遍历这100w个数字，数字和目标数组进行比较，若数组未存满，那么直接存入数组，若已经存满，那么从大到小，和目标数组中的元素进行比较，替换比该数字小的的元素

数字使用链表存储：

public class Data {

	private int data;
	private Data next;

	public Data(int data) {
		super();
		this.data = data;
	}

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public Data getNext() {
		return next;
	}

	public void setNext(Data next) {
		this.next = next;
	}

	@Override
	public String toString() {
		return "Data [data=" + data + "]";
	}

}

主程序代码（包括排序代码和生成数字代码）：

public class FindMin {

	static Data result = new Data(-1);
	static int capity = 0;
	static final int NUMBER = 10;

	public static void main(String[] args) {
		final int count = 1000000;
		int[] data = produceData(count);
		long begin = System.currentTimeMillis();
		init();
		findMinTen(data);
		long end = System.currentTimeMillis();
		System.out.println("找到最小10个数为：");
		while (result.getNext() != null) {
			System.out.print(result.getData() + ",");
			result = result.getNext();
		}
		System.out.println("耗时为：" + (end - begin));
	}

	private static void init() {
		Data header = result;
		for (int index = 0; index < NUMBER; index++) {
			header.setNext(new Data(-1));
			header = header.getNext();
		}
	}

	private static void findMinTen(int[] data) {
		for (int d : data) {
			putData(d);
		}
	}

	private static void putData(int d) {
		Data header = result;
		Data point = header;
		while (header.getNext() != null) {
			if (header.getData() == -1) {
				header.setData(d);
				capity++;
				return;
			} else if (header.getData() >= d) {
				point = header;
				header = header.getNext();
			} else {
				break;
			}
		}
		if (header == point) {
			return;
		}

		if (capity < NUMBER) {
			// 未满插入新元素
			Data data = new Data(d);
			if (header == point) {
				data.setNext(header.getNext());
				point.setNext(data);
			} else {
				point.setNext(data);
				data.setNext(header);
			}
			// 插入新元素，刪除空元素
			while (header.getNext() != null) {
				if (header.getData() == -1) {
					point.setNext(header.getNext());
					break;
				} else {
					point = header;
					header = header.getNext();
				}
			}
			capity++;
		} else if (point.getData() > d) {
			point.setData(d);
		}
	}

	private static int[] produceData(int count) {
		int[] data = new int[count];
		int index = 0;
		do {
			data[index++] = (int) (Math.random() * count);
		} while (index < count);
		return data;
	}

}

转载于:https://my.oschina.net/tiger/blog/634497