最小的K个数

这个题的思路就是先对数组排序，再取前k个数即可。（插入排序，冒泡排序，选择排序，快排，堆排均可）
1.利用Arrays.sort()进行排序
再进行一次遍历存入前k个数，得最后结果，时间复杂度：O（nlogn），Arrays的sort排序，空间复杂度：O(1)
import java.util.ArrayList;
import java.util.*;

public class Solution {
public ArrayList<integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<integer> res=new ArrayList<>();
if(input.length==0)//数组为空
return res;
Arrays.sort(input);
for(int i=0;i<k;i++)
{
res.add(input[i]);
}
return res;
}
}
2.快排
平均时间复杂度：O（nlogn）,最坏复杂度：O（n2），空间复杂度：O(1)
import java.util.ArrayList;
import java.util.*;</integer></integer>

public class Solution {
public ArrayList<integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<integer> res=new ArrayList<>();
if(input.length==0)//数组为空
return res;
quick(input,0,input.length-1);
for(int i=0;i<k;i++)
{
res.add(input[i]);
}
return res;
}
public void quick(int []input,int low,int high){
if(low<high){
int mid=quickSort(input,low,high);
quick(input,low,mid-1);//对左边进行快排
quick(input,mid+1,high);//对右边进行快排
}
}
public int quickSort(int []input,int low,int high){//一趟排序结束后会以基准元素为界，左边比其大，右边比其小
int temp=input[low];//基准元素
while(low<high){
while(low<high&&input[high]>=temp)//找到比基准元素小的元素
high--;
input[low]=input[high];
while(low<high&&input[low]<=temp){////找到比基准元素大的元素
low++;
}
input[high]=input[low];
}
input[low]=temp;
return low;
}
}
3.堆排序：
堆中元素为k个，先以input数组的前k个数建立大根堆，然后再用大根堆的最大值与后面的元素进行比较，如果比其小，就互换元素，对大根堆进行调整。时间复杂度：O（nlogn），空间复杂度：O（1）
import java.util.ArrayList;
import java.util.*;</integer></integer>

public class Solution {
public ArrayList<integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<integer> res=new ArrayList<>();
if(input.length==0)//数组为空
return res;
BuildMaxHeap(input,k);
for(int i=k;i<input.length;i++){
if(input[i]<input[0]){//如果元素比大根堆的最大值小更新大根堆
int temp=input[i];
input[i]=input[0];
input[0]=temp;
HeapAdjust(input,0,k-1);
}
}
for(int i=0;i<k;i++)
{
res.add(input[i]);
}
return res;
}
public void BuildMaxHeap(int []input,int k){//建立大根堆,其中大根堆的长度为k
for(int i=k/2-1;i>=0;i--){
HeapAdjust(input,i,k-1);
}
}
public void HeapAdjust(int []input,int k,int len){
int temp=input[k];//存放根结点
for(int i=2k+1;i<=len;i=2i+1){
if(i<len&&input[i]<input[i+1])//取子结点较大的那一个
i++;
if(temp>input[i])//父结点比子结点的值大，结束筛选
break;
else{
input[k]=input[i];//将input[i]结点的值调整到父结点
k=i;//更新父结点的坐标
}
}
input[k]=temp;
}
}</integer></integer>