java - 有一个算法问题想请教，给定一亿个数，如何用最快的方法取出其中最大的三个数。

Question

最近有一个java大神，是蚂蚁支付宝的哦，问了我这么一个问题。我的回答是先将数组分解成两百个小数组或者更多，在开两百个thread进行排序，取最大，然后对这两百个数进行排序，取前三。其实我的思路根本就没有涉及到算法层面，也只是暴力破解。其实这不是最好的做法，因为这样会严重的浪费资源，然后他的回答是堆排序。我的问题是堆排序是怎样实现的，最好用代码体现出来。

Answer 1

왜 상위 3개를 정렬해야 하나요? 중간 결과를 저장하려면 세 개의 새로운 변수 공간을 열어보세요.

이 방법의 복잡도는 O(nk)이며, n은 전체 데이터 양, k는 얻어야 하는 데이터 개수입니다. 힙 정렬이든 퀵 정렬이든 순서는 O(nlogn)입니다. k가 log(2, 10 ** 8)보다 작을 때 여전히 이점이 있습니다. 너무 크면 삽입 정렬로 변질됩니다.

Answer 2

N(N>>10000)개의 정수가 있습니다. 그 중에서 가장 큰 K개 숫자를 찾으세요. (상위 k 알고리즘 문제라고 함) (1) 입력 데이터의 양이 많고 (2) 첫 번째 K만 있기 때문에 전체 입력 데이터를 저장하고 정렬하는 것은 매우 바람직하지 않습니다. 이 문제는 데이터 구조의 최소 힙을 사용하여 처리할 수 있습니다.

최소 힙, 리프가 아닌 각 노드의 값은 하위 노드의 값보다 클 수 없습니다. 이런 방식으로 K개의 노드를 포함하는 최소 힙을 사용하여 K개의 현재 최대값을 저장할 수 있습니다(물론 루트 노드는 그 중 최소값입니다). 데이터가 입력될 때마다 먼저 루트 노드와 비교할 수 있습니다. 루트 노드보다 크지 않으면 삭제하고, 그렇지 않으면 루트 노드 값을 새 값으로 바꿉니다. 그리고 최소 힙을 조정합니다.

K개의 데이터만 저장되므로 최소 힙의 시간 복잡도는 O(logK)로 조정되므로 TOp K 알고리즘(문제)의 시간 복잡도는 O(nlogK)가 됩니다.

Answer 3

검색해 보세요
http://www.cnblogs.com/skywang12345/p/3610187.html

증명 및 파생에 대해서는 알고리즘 소개를 참조하세요

그런데 굳이 쌓을 필요는 없고 결국 숫자 3개만 찾으면 되는데...

Answer 4

이건 일반적인 TopK 질문 아닌가요? Baidu에서 TopK를 검색해 보세요

Answer 5

topn의 답변은 이 3에서 따온 것입니다. . . 이렇게 적은 숫자

Answer 6

힙 정렬입니다

Answer 7

탑크솔루션

Answer 8

가장 빠르게 하고 싶다면 비트맵 정렬이 제가 본 것 중 가장 빠른 것 같아요.