java堆排序解决topk问题,Java 实现 堆排序 快速排序 以及 TopK问题(一)

问题是 从大小为N的无序数组里面取K个最大值

最早想到的办法是冒泡K轮，但是后来思考到，堆排序和快速排序，可以更好的实现取K个最大值。

堆排序Java实现

public class Main {

public static void main(String[] args) {

int[] arr={5,62,81,63,13,43,34,5,8,9,6,44};

int k=5;

heapBuild(arr,arr.length); //建树

for(int x=0;x

System.out.print(arr[0]+" ");

swap(arr,0,arr.length-1-x); //交换第一个值和最后一个值(将根和最后一个叶子交换)

Fix(arr,0,arr.length-1-x);//递归修正

}

}

private static void heapBuild(int[] arr,int len) {

for(int i=len/2-1;i>=0;i--){//从后遍历所有度大于一的节点

Fix(arr,i,len); //修正该子树

}

}

private static void Fix(int[] arr, int i,int len) { //

int left=i*2;

int right=i*2+1;

int max=i;

if (left < len && arr[left] > arr[i]) {

max = left;

}

if (right < len && arr[right] > arr[max]) {

max = right;

}

if(i!=max){

swap(arr,max,i);

Fix(arr,max,len);

}

}

private static void swap(int[] arr, int a, int b) { //交换赋值

int temp=arr[a];

arr[a]=arr[b];

arr[b]=temp;

}

}

输出为 81 63 62 44 43

堆排序实现取topK,复杂度为O(klogn)