此系列是我用kotlin二刷leetcode写的总结，会总结用各个方法做的题目以及心得，主要是剑指offer专栏的题目
快速排序
第一题:剑指offer40 最小的k个数，输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
方法总结：此题采用了快排切分的方法，通过递归调用partition找到当前选中元素的正确位置，如果等于目标数字则返回
细节：
1.传入quickSearch的是k-1，因为partition返回的是目标的数组索引，而需要的是包括返回索引的数字，所以要判断索引等于k-1则当前返回的res索引以及其之前的数字才是想要的数组
2.partition返回r不返回l，因为r之前的数字一定都是小于等于目标的，所要求的小于等于目标的数组，所以要返回r，使条件成立
3.注意kotlin函数传入的参数默认是val,指针无法被修改，所以要自定义var变量来承载参数进行变更
代码：
fun getLeastNumbers(arr: IntArray, k: Int): IntArray {
if(k==0|| arr.isEmpty())return intArrayOf()
return quickSearch(arr,0,arr.size-1,k-1)
}
fun quickSearch(arr: IntArray,lo:Int,hi:Int,k:Int):IntArray{
val res=partition(arr,lo,hi)
if(res==k)return arr.take(res+1).toIntArray()
return if(res>k)quickSearch(arr,lo,res-1,k)else quickSearch(arr,res+1,hi,k)
}
fun partition(arr: IntArray,start:Int,end:Int):Int{
val num=arr[start]
var l=start
var r=end+1
while(true) {
while (++l <= end && arr[l] < num);
while (--r >= start && arr[r] > num);
if(l>=r)break
swap(arr,l,r)
}
swap(arr,r,start)
return r
}
fun swap(arr:IntArray,left:Int,right:Int){
val temp=arr[left]
arr[left]=arr[right]
arr[right]=temp
}
