TopK问题

经典的TopK问题：
从array[1,n]这N个数中，找出最大的k个数。

一，冒泡排序

我们所能想到的最经典的办法就是冒泡排序，将n个数排序之后，取出最大的k个。

代码展示：

public class Solution {
    public static void main(String[] args) {
        int[] a={3,4,8,12,3,2,9,0,5,7};
        System.out.println("排序前数组为：");
        for(int k:a){
            System.out.print(k+" ");
        }
        for(int i =0;i < a.length;i++){
            for(int j = i + 1;j < a.length;j++){
                if(a[i] < a[j]){
                    int t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                }
            }
        }
        System.out.printf("\n");
        System.out.println("排序后数组：");
        for(int k:a){
            System.out.print(k+" ");
        }
    }
}

运行结果：
时间复杂度：O（n^2）
分析：明明只需要Topk，我们却将全局都排序了，以至时间复杂度非常高。那就提出了一个问题：能不能只找到前k大的数，不需要排序呢？
这就引出了第二个优化方法。

二，堆排序
思路：只需要找到TopK，不排序。
即在一个数组中，先找到前K个元素，用其形成一个小堆，接着，从第k+1个元素开始扫描，和堆顶元素相比较，如果被扫描的元素大于堆顶，则替换堆顶元素，并调整堆，以保证堆内的k个元素总是最大的k个元素。

import java.util.Arrays;

public class aaa {
    public static void Swap(int []array,int a,int b){
        int t = array[a];
        array[a] = array[b];
        array[b] = t;
    }
    public static void shiftDownSmall(int[] array,int index,int size){
        int left = 2*index + 1;
        while(left < size){
            int min = left;
            int right = left + 1;
            if(right<size){
                if(array[left] > array[right]){
                    min = right;
                }
            }
            if(array[index] <= array[min]){
                break;
            }
            Swap(array,min,index);
            index = min;
            left = 2*index + 1;
        }
    }
    public static void createHeap(int[] array,int size){
        for(int i =( size - 1 ) / 2;i >= 0;i--){
            shiftDownSmall(array,i,size);
        }
    }
String[] args) {
        int[] a = {1,4,23,6,7,2,69,13,2,0,8};

        int k = 5;
        int[] b = new int[a.length];
        for(int i = 0;i < k;i++){
            b[i]=a[i];
        }
        createHeap(b,k);
        for(int i=k;i < a.length;i++){
            if(b[0] < a[i]){
                b[0] = a[i];
                createHeap(b,k);
            }
        }

        System.out.println(Arrays.toString(b));

    }
}

运行结果：[7, 8, 23, 69, 13, 0, 0, 0, 0, 0, 0]
时间复杂度：O(n*lg(n))

分析：堆，是求TopK的经典算法。