输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
思路一： 利用parition函数，分割找到第k个位置，那么k位置之前的就是k个未排序的小数，参看快速排序；
import java.util.ArrayList; /*快速排序*/ public class 最小的k个数 { public static void main(String[] args) { // TODO Auto-generated method stub // int[] input = {4,5,1,6,2,7,3,8}; int[] input = {4,5,1,6,2,7,3,8}; ArrayList<Integer> ans = GetLeastNumbers_Solution(input, 4); for (int i = 0; i < ans.size(); i++) { System.out.print(ans.get(i)+" "); } } public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> answer = new ArrayList<>(); if (input==null||k>input.length||k<0) { return answer; } int index = partition(input,0,input.length-1); while (index!=k-1) { if (index>k-1) { index = partition(input, 0, index-1); }else { index = partition(input, index+1, input.length-1); } } // Arrays.sort(input); for (int i = 0; i < k; i++) { answer.add(input[i]); } return answer; } /*partition算法*/ private static int partition(int[] input, int low, int high) { // TODO Auto-generated method stub int pivot = input[low]; //注意这里的<号，不是小于等于号 while (low<high) { while (low<high&&input[high]>=pivot) { high--; } // swap(input, high, low); input[low]=input[high]; while (low<high&&input[low]<=pivot) { low++; } // swap(input, low, high); input[high]=input[low]; } input[low]=pivot; return low; } private static void swap(int[] input, int i,int j) { int temp = input[i]; input[i] = input[j]; input[j] = temp; } } 思路二： 创建一个容量为K的容器，把数组挨个放进来，如果容量满了，就把容器最大的数和要放入的那个数比较，容器里的更小，就继续遍历下一个数，容器的更大，就删除这个数，放入数组的数；这里容器使用大堆,排除最大的数，为logk；
第一步：创建一个k容量的大堆，从数组先放入前k个数；
第二步：挨个取出数组K以后的数和堆最大的数比较；堆里的大就和数组的数互换，然后调整堆；
n个数，复杂度为n*logk；参考 堆排序
import java.util.ArrayList; public class 最小的k个数2 { public static void main(String[] args) { // TODO Auto-generated method stub int[] input = {4,5,1,6,2,7,3,8}; int k = 0; ArrayList<Integer> ans = GetLeastNumbers_Solution(input,k); for (int i = 0; i < k; i++) { System.out.print(ans.get(i)+" "); } } public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> sort = new ArrayList<>(); if (k<=0||k>input.length||input==null) { return sort; } sort = heapsort(input,k); return sort; } private static ArrayList<Integer> heapsort(int[] input, int k) { // TODO Auto-generated method stub //创建一个大顶堆容器maxheap int maxheap[] = new int[k]; //初始化，填入数据； for (int i = 0; i < k; i++) { maxheap[i]= input[i]; } //maxheap数组构建成一个大顶堆 for (int i = (maxheap.length-1)/2; i >= 0 ; i--) {//这里是maxheap.length-1/2 heapadjust(maxheap,i,maxheap.length); } //把input数组剩下的数挨个遍历和大顶堆的最大数比较 for (int i = k; i < input.length; i++) { if (input[i]<maxheap[0]) { maxheap[0] =input[i];//大顶堆的数字比被遍历的大，则删除，放入被遍历的数字 heapadjust(maxheap, 0, maxheap.length); } } ArrayList<Integer> ans = new ArrayList<>(); for (int i = 0; i < maxheap.length; i++) { ans.add(maxheap[i]); } return ans; } /*从i位置，从下到上，从左到右调整*/ private static void heapadjust(int[] maxheap, int i, int length) { // TODO Auto-generated method stub int temp = maxheap[i]; for (int j = i*2; j < length; j*=2) { if (j+1<length&&maxheap[j]<maxheap[j+1]) { j++;//说明右边节点值大于左边节点值，让j+1定位到右边节点； } if (temp>=maxheap[j]) { break; } maxheap[i]=maxheap[j]; i=j; } maxheap[i] = temp; } }
