根据楼楼参加笔试或者面试的经验而言，寻找最大的K个数这个问题，被问到已经不只两三次了，所以楼楼决定认认真真地把这个问题写一下，解法思想参照《编程之美》一书。
题目简介
有很多无序的数，我们姑且假定他们各不相等，怎么选出其中最大的K个数呢？
相关知识点
排序
题目解答解法一：直接排序
这个解法是第一反应，假设有N个数，我们使用一个N个长度的数组将其存储下来，并且使用排序算法将其从大到小依次排列。排序完成后，输出前K个数。如果N不小，但是也不大，比如几千什么的，可以采用快速排序或者堆排序来完成。 代码：
; int findMaxN(int *pArray, int len);*b){return *(int *)b – *(int *)a;}int main() {int a[] = {9, 8, 7, 6, 5, 4, 3, 11, 12, 13, 1, 28};int K = 5;int len = sizeof(a) / sizeof(int);//利用快速排序法进行排序qsort(a, len, sizeof(int), comp);for (int i = 0; i < K; i++){cout << a[i] << ” “;}system(“pause”);}
复杂度分析： 堆排序或者快速排序平均的复杂度为。 延伸：qsort()用法：
qsort(*))
第一个参数：待排序数组首地址 第二个参数：数组中待排序元素数量 第三个参数： 各元素的占用空间大小 第四个参数：指向函数的指针，用于确定排序的顺序。 以下为compare函数原型
compare( (void *) & elem1, (void *) & elem2 );
Compare 函数的返回值 描述
小于 0 elem1将被排在elem2前面
等于0 elem1 等于 elem2
大于0 elem1将被排在elem2后面
解法二：部分排序法
简单分析一下，我们就能发现解法一的一个明显不足之处，那就是我们将所有的元素都进行了排序，而题目要求只是寻找最大的K个数，也就是说我们只要将最大的K个数排好序就好了，没必要将剩下的N-K个数也进行排序。
在这里，我们可以使用快速排序来完成这个部分排序的功能。在快速排序中，每一轮都需要选定一个pivot，每一轮排序完成后，比pivot大的数都排在它前（后）面，而比pivot小的数都排在它的后（前）面。假设前面的序列为Sa，后面的序列为Sb，Sa的长度为n. 当时，我们直接输出Sa的前K个元素就好了； 当时，我们直接输出Sa这个序列； 当个元素和Sa一起输出就好了。
看代码：
; int kBig(int *pArray, int low, int high, int K);int partion(int *pArray, int low, int high);int main() {int a[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17, 20};for (int i = 0; i <= kBig(a, 0, sizeof(a)/sizeof(int), 2); i++){cout << a[i] << ” “;}system(“pause”);} //对前K大的数进行排序，并返回第K大数的下标int kBig(int *pArray, int low, int high, int K){int index, n;if (low < high){//对数组进行划分，并返回划分的位置index = partion(pArray, low, high);n = index – low + 1;//Sa的个数if (n == K)//如果恰好是K个的话，那么返回下标就可以了{return index;}if (n < K)//如果Sa的个数不够的话，那么再从Sb中找K-n个{return kBig(pArray, index + 1, high, K – n);}if (n > K)//如果Sa的个数大于K的话，那么就从Sa里面返回K个{return kBig(pArray, low, index, K);}}}//快速排序的划分函数并返回pivot的坐标int partion(int *pArray, int low, int high){int i = low; int j = low;int pivot = pArray[low];for (; i < high, j < high;j++){if (pArray[j] > pivot){i++;swap(pArray[i], pArray[j]);}}swap(pArray[i], pArray[low]);return i;}
复杂度分析： 很显然，相对解法一而言，解法二的复杂度为。
解法三：堆排序法
就楼楼的面试经验来看，如果这个问题你能答到堆排序算法的话，这时候面试官就基本满意了。这是他们想问的点，因为在他们问题里会不断地强调这个N是如何之大，内存受到限制之类的。比如如果N都是几百万的话，那用这么大的数组来存储，这就是非常不明智地做法了。用堆就可以完美解决存储问题。
; void buildMinHeap(int *pArray, int K);void adjustHeap(int *pArray, int rootIndex, int heapSize);int main() {int a[] = {9, 8, 7, 6, 5, 4, 3, 11, 12, 13, 1, 28};int K = 5 ;//建一个K个元素大小的最小堆buildMinHeap(a, K);//从第K个元素开始扫描，看有没有比根节点更大的节点，若有则替换，并更新堆；若没有比根节点大则扫描下一个元素，直到数组结束for (int i = K; i < sizeof(a) / sizeof(int); i++){if (a[i] > a[0]){swap(a[i], a[0]);adjustHeap(a, 0, K);}}//打印出前K大的数，，没有排序。for (int i = 0; i < K; i++){cout << a[i] << ” “;}system(“pause”);} //建一个K个元素大小的最小堆void buildMinHeap(int *pArray, int K){for (int i = (K – 2) / 2; i >= 0; i–){adjustHeap (pArray, i, K);}}void adjustHeap (int *pArray, int rootIndex, int heapSize){int minIndex = rootIndex;//左孩子节点int leftIndex = 2 * rootIndex + 1;//右孩子节点int rightIndex = 2 * (rootIndex + 1);//如果左孩子比根节点和右孩子节点小的话，则左孩子和根节点进行交换if ((leftIndex < heapSize) && (rightIndex < heapSize) && (pArray[leftIndex] < pArray[rightIndex]) && (pArray[leftIndex] < pArray[rootIndex])){minIndex = leftIndex;}if ((leftIndex < heapSize) && (rightIndex >= heapSize) && (pArray[leftIndex] < pArray[rootIndex])){minIndex = leftIndex;}if ((rightIndex < heapSize) && (pArray[rightIndex] < pArray[leftIndex]) && (pArray[rightIndex] < pArray[rootIndex])){minIndex = rightIndex;}if (minIndex != rootIndex){//如果左孩子或者右孩子比根节点小的话，那么就交换，并且重新调整以minIndex为根节点的子树swap(pArray[rootIndex], pArray[minIndex]);adjustHeap(pArray, minIndex, heapSize);}}最有效的资本是我们的信誉，它24小时不停为我们工作。
