编程之美找寻最大的K个数

解法一是最基本的排序算法，本文略过。

解法四依赖最大堆这个数据结构，多用于海量数据处理，本文略过。

重点实现了解法二和解法三。

解法二的思想是利用快排的以O(n)的时间得到某个数组中任意元素序号p,有A[i] <= A[x], r<=i<=p， A[j] > A[p], p<j<=r， 然后再配合二分查找，可以得到O（n*lgK）的算法。该算法比解法三要容易理解，但是在实际做的过程中，发现最大的问题在于边界条件的处理，即应注意数组下标和元素个数是两个不同的概念，两者混淆的话很容易把自己绕进去，另外从完备性的角度考虑还应考虑异常处理，如果数组中所有元素为同一数值，那么该解法会导致死循环，该如何处理？

解法三则从数值的角度采用了二分搜索。是一种不同的思路，相比较解法二，我认为这种方法是实现难度最低的。效率同样也是O（n*lgK）

// FindMaxK.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include <stdlib.h>void swap(int A[], int i, int j){int t = *(A + i);*(A + i) = *(A + j);*(A + j) = t; }int partition(int A[], int r, int q){if(r < q){int t = r + rand() % (q - r) + 1;swap(A, t, r);int j = r;for(int i = r + 1; i <= q; i++){if(A[i] <= A[r]){j++;swap(A, i, j);}}swap(A, r, j);return j - r;}return -1;}void FindMaxK1(int A[], int r, int q, int k){int p = partition(A, r, q);if( p > k ){FindMaxK1(A, r, p,k);}else if( p < k ){FindMaxK1(A, p + 1, q,k - p );}}int count(int A[], int len, float v){int count = 0;for(int i = 0; i < len; i++){if(A[i] >= v)count++;}return count;}int FindMax2(int A[], int len, int k){if(len <= 0)return -1;float min = A[0];float max = A[0];for(int i = 0; i < len; i++){if(A[i] > max)max = A[i];if(A[i] < min)min = A[i];}float delta = 0.5;while ( max - min > delta ){float mid = min + (max - min) / 2;if(count(A, len, mid) > k){min = mid;}else{max = mid;}}for(int i = 0; i < len; i++){if(A[i] >= min && A[i] <= max)return A[i];}}enum {len = 6};void Test(){int A[] = {4,3,1,7,5,2};int k = 3;FindMaxK1(A, 0, len - 1, k);for(int i = 0; i < len; i++){printf("%d ", A[i]);}int v = FindMax2(A, len, k);printf("%d ", v);}int _tmain(int argc, _TCHAR* argv[]){Test();return 0;}