找到无序数组中最小的k个数

找到无序数组中最小的k个数：
给定一个无序的整型数组arr，找到其中最小的k个数
如果数组arr长度为N，排序后自然可以得到最小的k个数，此时时间复杂度与排序的时间复杂度相同，均为O(NlogN)。本题要求读者实现时间复杂度为O(Nlogk)和O(N)的方法

O(Nlogk):

一直维护有k个数的大根堆，这个堆代表目前选出的k个最小的数，在堆里的k个元素中堆顶的元素是最小的k个数里最大的那个。接下来遍历整个数组，遍历的过程中看档期数是否比堆顶元素小，如果是，就把堆顶元素替换成档期的数，然后从堆顶的位置调整整个堆，让替换操作后堆的最大元素继续处在堆顶的位置；如果不是，则不进行任何操作，继续遍历下一个数；在遍历完成后，堆中的k个数就是所有数组中最小的k个数

public int[] getMinKNumsByHeap(int[] arr, int k){
    if(k<1 || k>arr.length){
        return arr;
    }
    int[] kHeap = new int[k];
    for(int i=0;i!=arr.length;i++){
        if(arr[i]<kHeap[0]){
            kHeap[0] = arr[i];
            heapify(kHeap, 0, k);
        }
    }
    return kHeap;
}

public void heapInsert(int[] arr, int value, int index){
    arr[index] = value;
    while(index!=0){
        int parent = (index-1)/2;
        if(arr[parent] < arr[index]){
            swap(arr, parent, index);
            index = parent;
        }else{
            break;
        }
    }
}

public void heapify(int[] arr, int index, int heapSize){
    int left = index * 2+1;
    int right = index * 2+2;
    int largest = index;
    while(left < heapSize){
        if(arr[left] > arr[index]){
            largest = left;
        }
        if(right < heapSize && arr[right] > arr[largest]){
            largest = right;
        }
        if(largest!=index){
            swap(arr, largest, index);
        }else{
            break;
        }
        index = largest;
        left = index * 2+1;
        right = index * 2+2;
    }
}

public void swap(int[] arr, int index1, int index2){
    int tmp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = tmp;
}

O(N)：BFPRT算法：

在时间复杂度O(n)内，从无序的数组中找到第k小的数，显而易见的是，如果我们找到了第k小的数，那么想求arr中最小的k个数，就算再遍历一遍数组的而工作量而已。
假设BFPRT算法的函数是int select(int[] arr, k)，该函数的功能为在arr中找到第k小的数，然后返回该数，select(arr, k)过程如下：

1. 将arr中的n个元素划分成n/5组，每组5个元素，如果最后的组不够5个元素，那么最后剩下的元素为一组(n%5个元素)。
2. 对每个组进行插入排序，只针对每个组最多五个元素之间的组内排序，组与组之间并不排序，排序后找到每个组的中位数，如果组的元素个数为偶数，则规定找到下中位数
3. 步骤2中一共会找到n/5个中位数，让这些中位数组成一个新的数组，记为mArr，递归调用select(mArr, mArr.length/2),意义是找到mArr这个数组中的中位数，即mArr中第mArr.length/2小的数
4. 假设步骤3中递归调用select(mArr, mArr.length/2)后，返回的数为x，根据这个x划分整个arr数组（partition过程），划分的过程为：在arr中，比x小的数都在x的左边，大于x的数都在x的右边，x在中间。假设划分完成后，x在arr中的位置记为i：
5. 如果i==k，说明x为整个数组中第k小的数，直接返回
   如果i< k,说明x处在第k小的数的左边，则应该在x的右边寻找第k小的数，所以递归调用select函数， 在左半区寻找第k小的数。
   如果i>k,说明x处在第k小的数的右边，应该在x的左边寻找第k小的数，所以递归调用select函数，在右半区寻找第(i-k小的数)

public int[] getMinKNumsByBFPRT(int[] arr, int k){
    if(k<1 || k > arr.length){
        return arr;
    }

    //找到第k小的数
    int minKth = getMinKthByBFPRT(arr, k);
    int[] res = new int[k];
    int index = 0;
    //把所有小于minKth的数放入res中
    for(int i=0;i!=arr.length;i++){
        if(arr[i]<minKth){
            res[index++] = arr[i];
        }
    }
    //如果不够，则说明要填充这个数
    for(; index!=res.length;index++){
        res[index] = minKth;
    }
    return res;
}

public int getMinKthByBFPRT(int[] arr, int K){
    //为了不修改原数组，在拷贝数组上操作
    int[] copyArr = copyArray(arr);
    return select(copyArr, 0, copyArr.length-1, K-1);
}

//拷贝数组
public int[] copyArray(int[] arr){
    int[] res = new int[arr.length];
    for(int i=0;i!=res.length;i++){
        res[i] = arr[i];
    }
    return res;
}

//核心筛选函数
public int select(int[] arr, int begin, int end, int i){
    if(begin == end){
        return arr[begin];
    }
    //找到中间数字
    int pivot = medianOfMedians(arr, begin, end);
    //以这个数字为枢轴，对大于他和小于他的数进行左右分开，也就是说，枢轴会被放置到它应该在的位置上
    int[] pivotRange = partition(arr, begin, end ,pivot);
    //如果这个枢轴就是要找的数，直接返回
    if(i>=pivotRange[0] && i<=pivotRange[1]){
        return arr[i];
    }else if(i<pivotRange[0]){ //如果i小于这个枢轴索引，说明i对应的数应该在前面，则继续筛选
        return select(arr, begin, pivotRange[0]-1, i);
    }else{  //如果i大于这个枢轴索引，说明i对应的数应该在后面，则继续筛选
        return select(arr, pivotRange[1]+1, end, i);
    }
}


public int medianOfMedians(int[] arr, int begin, int end){
    //把整个数组5个5个分为一组
    int num = end - begin + 1;
    int offset = num % 5 ==0?0:1;
    //mArr是所有小区间中中间数组成的新数组
    int[] mArr = new int[num/5+offset];
    for(int i=0;i<mArr.length;i++){
        int beginI = begin+i*5;
        int endI = beginI + 4;
        //mArr[i]是这个小区间内排序后的中间数
        mArr[i] = getMedian(arr, beginI, Math.min(end, endI));
    }
    //继续进行筛选，最终找出的是整个数组中最中间的数（但是却不用把整个数组进行排序）
    return select(mArr, 0, mArr.length-1, mArr.length / 2);
}

//对数组进行划分，即找到枢轴值的位置，并且让该值左边都是小于他，右边都是大于他
public int[] partition(int[] arr, int begin, int end, int pivotValue){
    int small = begin-1;
    int cur = begin;
    int big = end +1;
    while(cur!=big){
        if(arr[cur] < pivotValue){
            swap(arr, ++small, cur++);
        }else if(arr[cur] > pivotValue){
            swap(arr, cur, --big);
        }else{
            cur++;
        }
    }
    int[] range = new int[2];
    range[0] = small + 1;
    range[1] = big - 1;
    return range;
}

//对arr进行插入排序，然后找到最中间的数，返回
public int getMedian(int[] arr, int begin, int end){
    insertionSort(arr, begin, end);
    int sum = end + begin;
    int mid = (sum/2) + (sum % 2);
    return arr[mid];
}

public void insertionSort(int[] arr, int begin, int end){
    for(int i=begin+1; i!=end+1; i++){
        for(int j=i;j!=begin;j--){
            if(arr[j-1]>arr[j]){
                swap(arr, j-1, j);
            }else{
                break;
            }
        }
    }
}

public void swap(int[] arr, int index1, int index2){
    int tmp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = tmp;
}