解决TOP-K问题：快速选择排序算法

1. 思想 Quick select算法通常用来在未排序的数组中寻找第k小/第k大的元素。 Quick select和Quick sort类似，核心是partition。

1. 什么是partition？

从数组中选一个数据作为pivot，根据每个数组的元素与该pivot的大小将整个数组分为两部分： 左半部分，都比pivot大，右半部分，都比pivot小 。

2. 用分治思路实现排序

pivotIndex 是pivot在数组的下标

pivotIndex大于k，说明array[pivotIndex]左边的元素都大于k，只递归array[0, pivotIndex-1]第k大的元素即可；

pivotIndex小于k，说明第k大的元素在array[pivotIndex]的右边，只递归array[pivotIndex +1, n]第k-pivotIndex大的元素即可；

代码：

@Test
    public void main() {
        int[] arr = {3,6,2,8,0,7,10};
        int k = 5;
        quickSelectSort(arr, 0, arr.length-1, k);
        for (int i=0; i<k; i++) {
            System.out.println(arr[i]);
        }
    }

    public void quickSelectSort(int[] arr, int low, int high, int k) {
       int  index = quickSort(arr, low, high);
       if (k == index-low+1) {

       } else if (k < index-low+1) {
           quickSelectSort(arr, low, index-1, k);
       } else if (k > index-low+1) {
           quickSelectSort(arr, index+1, high, k-(index-low+1));
       }
    }

    public int quickSort(int[] arr, int i, int j) {
        int temp = arr[i];
        while (i < j) {
            while (temp <= arr[j] && i<j) {
                j--;
            }
            arr[i] = arr[j];
            while (temp >= arr[i] && i<j) {
                i++;
            }
            arr[j] = arr[i];
        }
       arr[i] = temp;
        return i;
    }

与Quick sort不同的是，Quick select只考虑所寻找的目标所在的那一部分子数组，而非像Quick sort一样分别再对两边进行分 割。正是因为如此，Quick select将平均时间复杂度从O(nlogn)降到了O(n)。