题解 | #最小的K个数#

无语 第二次写快排惹、、、基本思想差不多摸清楚了，但谁能想到测试用例里面还有空的input。最讨厌的就是处理这种越界的情况 每次都搞得一头雾水。 不过这题可以帮助我训练各种排序算法 还挺好的 不要忘记了呦 快排和堆排~

import java.util.*;
public class Solution {
    public void swap(int[] arr,int left,int right)
    {
        int temp=arr[left];
        arr[left]=arr[right];
        arr[right]=temp;
    }
    public int partition(int left,int right,int[] arr)
    {
     
        int pivot=arr[right];
        int pointer=left;
        for(int i=left;i<right;i++)
        {
            if(arr[i]<pivot)
            {
                swap(arr,i,pointer);
                pointer++;
            }
        }
        swap(arr,pointer,right);
        return pointer;
    }
    public void   quicksort(int low,int high,int[] arr)
    {
        if(low>=high)
        {
            return;
        }
        int pivot=partition(low,high,arr);
        quicksort(low,pivot-1,arr);
        quicksort(pivot+1,high,arr);    
    }
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if(input.length==0)
        {
            return list;
        }
        int high=input.length-1,low=0;
        int temp=input[high];
        int point=low;
  
            int pivot=partition(low,high,input);
            quicksort(low,high,input);
   
            for(int i=0;i<k;i++)
            {
                list.add(input[i]);
            }
        
        return list;
    }
  
}