剑指OfferJZ29：最小的k个数-java版

jz29:给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组 Java的Arrays类中的sort()方法对数组进行排序：

Arrays.sort(int[] a) 对一个数组的所有元素按从小到大进行排序 Arrays.sort(int[] a, int fromIndex, int toIndex)

对数组部分元素排序，也就是对数组a的下标从fromIndex到toIndex-1的元素排序 版本1：

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    public ArrayList GetLeastNumbers_Solution(int [] input, int k) {
         ArrayList output=new ArrayList();
        if(k>input.length){
            //k>数组input的长度时返回一个空数组
            return output;
        }
        //Arrays.sort(int[] a)对一个数组的所有元素按从小到大进行排序
        Arrays.sort(input);
        for(int i=0;i input.length || k == 0) {
            //返回空对象
            return new ArrayList();
        }

        int[] a = new int[k];//1.用数组模拟k个节点的大顶堆（堆通常是一个可以被看作一棵完全二叉树的数组）
//        for(int i=0;i= 0; i--) {
            //维护大顶堆：非叶子结点和它的最大的孩子节点比较，孩子节点大，就互换位置（将大的数往上层换）
            initiate(i, a, k);
        }
        //3.遍历剩下的len-k个数据
        //如果当前位置数据小于堆顶元素root，用该数据替换root，然后维护堆让它成为一个大顶堆
        for (int i = k; i a[3]=6
                a[index]=a[in];//换值//a[3]=8
                index=in;//换下标，
            }else{
                break;
            }
        }
        a[index]=temp;//a[7]=6
    }
}