方法1：先对数组进行排序，然后遍历前K个数，此时时间复杂度为O(nlgn);
方法2：维护一个容量为K的最大堆（《算法导论》第6章），然后从第K+1个元素开始遍历，和堆中的最大元素比较，如果大于最大元素则忽略，如果小于最大元素则将次元素送入堆中，并将堆的最大元素删除，调整堆的结构;
方法3：使用快速排序的原理，选择出数组中第K大的元素，select(a[], k, low, high)
- 选取数组中a[high]为基准，将数组分割为A1和A2，A1中的元素都比a[high]小，A[2]中的元素都比a[high]大，将a[high]放到合适的位置；
- 如果k小于a[high]实际位置的index，则递归调用此函数select(a[], k, low, index - 1)；
- 如果k大于a[high]实际位置的index，则递归调用此函数selet(a[], k, index + 1, high)；
- 如果k等于a[hign]实际位置的index，则此时的index位置之前的数即为数组中最小的k个数；
/**
* Created by Administrator on 2014/12/8.
* 输入N个整数，输出最小的K个
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner; public class MinKArray {
/* 用二叉树表示一个堆 */
private class Heap {
private Node root;
private class Node {
int key;
Node left;
Node right;
Node(int key) {
this.key = key;
}
} /* 建立最大堆，将元素插入到堆的合适位置 */
public void put(int key) {
root = put(root, key);
} private Node put(Node x, int key) {
if (x == null)
return new Node(key);
int cmp = key - x.key;
if (cmp > 0) {
int tmp = x.key;
x.key = key;
key = tmp;
x.right = put(x.right, key);
} else if (cmp < 0) {
x.left = put(x.left, key);
}
return x;
} public void deleteMax() {
root = deleteMax(root);
} private Node deleteMax(Node x) {
if (x == null)
return null;
if ((x.left == null) && (x.right != null)) {
int tmp = x.key;
x.right.key = x.key;
x.key = tmp;
x.right = deleteMax(x.right);
} else if ((x.right == null) && (x.left != null)) {
int tmp = x.key;
x.left.key = x.key;
x.key = tmp;
x.left = deleteMax(x.left);
} else if ((x.left == null) && (x.right == null)) {
x = null;
} else {
int cmp = x.left.key - x.right.key;
if (cmp >= 0) {
int tmp = x.key;
x.key = x.left.key;
x.left.key = tmp;
x.left = deleteMax(x.left);
} else {
int tmp = x.key;
x.key = x.right.key;
x.right.key = tmp;
x.right = deleteMax(x.right);
}
}
return x;
} public void printHeap(Node x) {
if (x == null)
return;
System.out.print(x.key + " ");
printHeap(x.left);
printHeap(x.right);
}
} /* 使用一般的排序算法，然后顺序输出前K个元素 */
public int[] minKArray1(int[] a, int k) {
Arrays.sort(a);
for (int i = 0; i < k; i++) {
System.out.print(a[i] + " ");
}
return Arrays.copyOfRange(a, 0, k);
} /* 求出数组中第K大的元素，然后顺序遍历所有元素 */
public int[] minKArray2(int[] a, int k) {
minKArray2(a, k, 0, a.length - 1);
return a;
} /* 利用快速排序的原理，以a[high]为基准，将a[high]放到相应的位置
* 左边的都比它小，右边的都比它大 */
private void minKArray2(int[] a, int k, int low, int high) {
if (low <= high) {
int l = low, r = high - 1;
int x = a[high];
for (int i = low; i < high; i++) {
if (l <= r) {
if (a[l] > x) {
int tmp = a[r];
a[r] = a[l];
a[l] = tmp;
r--;
}
if (a[l] <= x) {
l++;
}
}
}
int tmp = a[l];
a[l] = a[high];
a[high] = tmp; if (l < k) {
minKArray2(a, k, l + 1, high);
} else if (l > k) {
minKArray2(a, k, low, l - 1);
} else {
for (int i = 0; i < k; i++) {
System.out.print(a[i] + " ");
}
}
}
} /* 维护一个容量为K的最大堆，《算法导论》第6章堆排序 */
public int[] minKArray3(int[] a, int k) {
Heap h = new Heap();
for (int i = 0; i < k; i++) {
h.put(a[i]);
}
for (int i = k; i < a.length; i++) {
if (a[i] >= h.root.key) {
continue;
} else {
h.put(a[i]);
h.deleteMax();
}
}
h.printHeap(h.root);
return a;
} public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
ArrayList<Integer> array = new ArrayList<Integer>();
while (scan.hasNext()) {
array.add(scan.nextInt());
}
int[] a = new int[array.size()];
for (int i = 0; i < a.length; i++) {
a[i] = array.get(i);
}
MinKArray mka = new MinKArray();
mka.minKArray1(a, 8);
System.out.println();
mka.minKArray2(a, 8);
System.out.println();
mka.minKArray3(a, 8);
System.out.println();
}
}