问题： 查找出一给定数组中第k大的数。例如[3,2,7,1,8,9,6,5,4]，第1大的数是9，第2大的数是8……
思考：1. 直接从大到小排序，排好序后，第k大的数就是arr[k-1]。
2. 只需找到第k大的数，不必把所有的数排好序。我们借助快速排序中partition过程，一般情况下，在把所有数都排好序前，就可以找到第k大的数。我们依据的逻辑是，经过一次partition后，数组被pivot分成左右两部分：S左、S右。当S左的元素个数|S左|等于k-1时，pivot即是所找的数；当|S左|小于k-1，所找的数位于S右中；当|S左|>k-1，所找的数位于S左中。显然，后两种情况都会使搜索空间缩小。
算法的时间复杂度为：O(N)--详情参考算法导论。
#include<iostream>using namespace std;int Partition(int a[], int i, int j){ int tmp = a[j]; int index =i; if (i < j) { for (int k=i;k<j;k++){ if(a[k] >= tmp){ swap(a[index++],a[k]); } } swap(a[index],a[j]); return index; }}int Search(int a[], int i, int j, int k){ int m = Partition(a, i, j); if (k==m-i+1) return a[m]; else if (k<m-i+1) { return Search(a, i, m-1,k ); } //后半段 else { return Search(a, m+1, j, k-(m-i+1)); }}int main(){ int a[7] = { 8,7,6,1,2,3,4 }; int k = 3; cout << Search(a,2, 6, k);}
上述问题对应于寻找前K大个数。上述方法对应的数据量比较小，如果N很大，100亿？甚至更多，这个时候数据不能够全部放入内存，所以要求尽可能少遍历数据。不妨设N>K,考虑前K个数中的最大K个数的一个退化的情况：所有K个数就是最大的K个数。如果考虑第K+1个数X呢？如果X比最大的K个数中的最小的数Y小，则最大的K个数保持不变。如果X比最大的K个数中个最小的数Y大，则最大的K个数要除去Y，加入X。如果用一个数组来保存前K大的数，每加入一个数X，就扫描一遍数组。得到数组中最小的数Y，用X代替Y或者保持不变。这种方法消耗的时间O(N*K)
进一步，可以用容量为K的最小堆来存储最大的K个数。最小堆的堆顶元素就是K个数中最小的一个。每次考虑一个数X，如果X比堆顶元素Y小，则保持最小堆不变，因为这个元素比最大的K个数小。如果X
比堆顶元素Y大，那么用X替换原来的堆顶元素Y，X可能破坏原来的最小堆结构（每个结点比它的父节点大），需要更新堆来维持堆的性质。更新堆时间复杂度为O（log2K).总的算法复杂度为O(N*log2k)
1 #include <iostream>
2 using namespace std;
3 //调整堆
4 void HeapAdjust(int a[],int i,int size)
5 {
6 int left = 2 * i + 1;
7 int right = 2 * i + 2;
8 int min = i;
9 if (left < size&&a[left] < a[min])
10 min = left;
11 if (right < size&&a[right] < a[min])
12 min = right;
13 if (min != i)
14 {
15 int temp = a[min];
16 a[min] = a[i];
17 a[i] = temp;
18 HeapAdjust(a,min,size); //避免调整之后以min为父节点的子树不是堆
19 }
20 }
21 //建立堆
22 void HeapBuild(int a[],int size)
23 {
24 for (int i = size / 2 - 1; i >= 0; i--)
25 HeapAdjust(a,i,size);
26 }
27 //k为需要查找的最大元素个数，size为数组大小，kMax存储k个元素的最小堆
28 void FindMax(int Array[], int k, int size, int kMax[])
29 {
30 for (int i = 0; i < k; i++)
31 kMax[i] = Array[i];
32 HeapBuild(kMax,k);
33 for (int j = k; j < size; j++)
34 {
35 if (Array[j] <= kMax[0]) continue;
36 kMax[0] = Array[j];
37 HeapAdjust(kMax,0,k);
38 }
39 }
40 int main()
41 {
42 int a[] = {10,23,17,8,52,35,7,1,28};
43 int k = 4;
44 int KMax[4] = {0};
45 FindMax(a,k,9,KMax);
46 for (int i = 0; i < k; i++)
47 cout << KMax[i] << endl;
48 }