1.已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
思路1：数组若是基本有序的话，最好是插入排序，时间复杂度为O(NK),N为数组长度，K是需要移动的数的最远距离不超过K。
参考多个数组排序一节
思路2：另外堆排序也可以用，选择堆起始大小为k的最小堆排序算法，
每个元素的移动
距离不超过K，表示前K个数中一定有最小值，
所以堆顶为最小值，堆顶放到a0处，a[k]放到最小堆的堆顶，继续建堆，知道剩下最后k个元素，此时随着每次堆顶的弹出，堆的大小k–. 时间复杂度O（nlogk），空间复杂度O（k）.理论上说也可以实现原地排序的。
2.在n个数中找出最大的k个数。
思路1：
最简单的方法是对大小为k的数组进行n-k次求min计算（或者对大小为n的数组进行k次求max计算）最后能够找出最大k个数。复杂度是O(nk)。
思路2：
建立小根堆，大根堆
（1）
小根堆：
维护一个大小为k的小根堆，从头到尾扫描n个数，如果当前数比堆顶大，替换堆顶，这样扫描到最后堆中保存的是最大的k个数。复杂度是O(nlogk)
（2）
大根堆：
维护一个大小为n的大根堆，每次弹出堆顶元素，共弹出k次。复杂度O(klogn)
3.
快速选择BFPRT
借用快速排序中思想，在快排中每次用一个轴将数组划分为左右两部分，轴左边的数都小于轴，轴右边的数都大于轴，轴所在的位置和排好序后的位置相同。这里只要找到第k大的数作为轴进行划分，那么就找到了最大的k个数。期望复杂度是：O(n)
