首先，中位数问题可以归结为求 K=n/2的 第K小元素，并无明显区别。

第一种方法，用MaxHeap，大小为K的大顶堆，能够求出最小的K的元素，复杂度为O(n*logK). 当K较大时，复杂度会较高。其实只需要求出第K小，而不是全部前K的序列，可以有更优化的方式。(大顶堆的方法就不贴代码了)

第二种方法，采用partition能够进行一定程度的改进，开始我认为这种方式已经是O(n)，实际上如果partition选取的pivot导致每次partition都偏向一边，那么最坏情况是O(n^2). 先贴代码如下：

#include 
     
      #include 
      
       #include 
       
        using namespace std;int array[] = {
   1, 20, 10, 8, 9, 7, 5};const int size = sizeof(array) /  sizeof (*array);int partition(int *array, int left, int right) {    if (array == NULL) {        return -1;    }    int pos = right;    right--;    while (left <= right) {        while (left <= right && array[left] <= array[pos]) {            left++;        }        while (right > left && array[right] > array[pos]) {            right--;        }        if (left >= right) {            break;        }        swap(array[left], array[right]);    }    swap(array[left], array[pos]);    return left;        }int getMinKth(int *array, int size, int k) {    if (array == NULL) {        return -1;    }    int left = 0;    int right = size - 1;    int index = -1;    while (index != k) {        index = partition(array, left, right);        if (index < k) {            left = index + 1;        }        else if (index > k) {            right = index - 1;        }        else {            break;        }    }    cout << "Value of k " << k << ":" << array[index] << endl;    return array[index];}int main(int argc, char** argv) {    if (argc < 2) {        printf("Run cmd %s kth\n", basename(argv[0]));        return 0;    }    int k = atoi(argv[1]);    int value = getMinKth(array, size, k);    return 0;}
       
      
     

运行结果：

[getMinKth]$ ./getMinKth 0Value of k 0:1[getMinKth]$ ./getMinKth 1Value of k 1:5[getMinKth]$ ./getMinKth 2Value of k 2:7[getMinKth]$ ./getMinKth 3Value of k 3:8[getMinKth]$ ./getMinKth 4Value of k 4:9[getMinKth]$ ./getMinKth 5Value of k 5:10[getMinKth]$ ./getMinKth 6Value of k 6:20

第三种方法，是真的O(n)，方法是采用5个一组的数列，取出中间一个，然后再从中取出中间一个，使用这个数作为pivot。

这样，至少有1/2 * 3/5个数比pivot小，也有1/2 * 3/5个数比pivot大。所以，每次最坏情况是划分成3:7或者7:3. 

时间复杂度的证明方法：

T(n)<=T(n/5)+T(7/10*n)+O(n)<=c*n*(1+9/10+(9/10)^2....) 所以T(n)=O(n)

 写代码如下：

review时注：我觉得可以用上面的end比较的方式，先把pivot交换到最后，这样虽然多了一个swap，但是代码简洁很多，也不容易出错。

#include 
     
      #include 
      
       using namespace std;void printArr(int *arr, int first, int end) {    cout << "Array first " << first << "end " << end << ":";    for (int i=first; i<=end; ++i) {        cout << arr[i] << " ";    }    cout << endl;}int getMinKth(int *arr, int first, int end, int k);int partition(int *arr, int first, int end, int pivot) {    int ret = -1;    int tmp = -1;    while (first <= end) {        while (arr[first] <= pivot) {            if (arr[first] == pivot) {                ret = first;            }                first++;        }        while (arr[end] > pivot) {            end--;        }        if (first < end) {            tmp = arr[first];            arr[first] = arr[end];            arr[end] = tmp;            if (arr[first] == pivot) {                ret = first;            }                first++;            end--;        }    }    tmp = arr[end];    arr[end] = arr[ret];    arr[ret] = tmp;    return end;}int getPivot(int *arr, int first, int end) {    if (end - first + 1 <= 5) {        sort(arr+first, arr+end+1);        return arr[(first+end)/2];    }    int grp = (end - first + 5) / 5;    int *tmpArr = new int[grp];        for (int i=0; i
       
         end) {            tmpEnd = end;        }        tmpArr[i] = getPivot(arr, tmpFirst, tmpEnd);    }    int ret = getMinKth(tmpArr, 0, grp-1, (grp-1)/2);    delete []tmpArr;    return ret;}int getMinKth(int *arr, int first, int end, int k) {    if (first == end) {        return arr[first];    }    if (k < first || k > end) {        return -1;    }    int index = -1;    int pivot = -1;    while (index != k) {        pivot = getPivot(arr, first, end);        index = partition(arr, first, end, pivot);        if (index < k) {            first = index + 1;        }        else if (index > k) {            end = index - 1;        }        else {            break;        }    }    return arr[k];}int main(int argc, char **argv) {    int array[] = {
   2, 10, 3, 9, 20, 6, 1, 100};    if (argc <= 1) {        printf("%s kth\n", argv[0]);        return 1;    }    printArr(array, 0, 7);    int k = atoi(argv[1]);    int ret = getMinKth(array, 0, 7, k);    printf("The %dth val is %d\n", k, ret);    return 0;}
       
      
     

编译命令：

g++ -o getMinKthOn getMinKthOn.cpp

执行命令：

[getMinKthOn]$ ./getMinKthOn 0Array first 0end 7:2 10 3 9 20 6 1 100 The 0th val is 1[getMinKthOn]$ ./getMinKthOn 1Array first 0end 7:2 10 3 9 20 6 1 100 The 1th val is 2[getMinKthOn]$ ./getMinKthOn 2Array first 0end 7:2 10 3 9 20 6 1 100 The 2th val is 3[getMinKthOn]$ ./getMinKthOn 3Array first 0end 7:2 10 3 9 20 6 1 100 The 3th val is 6[getMinKthOn]$ ./getMinKthOn 4Array first 0end 7:2 10 3 9 20 6 1 100 The 4th val is 9[getMinKthOn]$ ./getMinKthOn 5Array first 0end 7:2 10 3 9 20 6 1 100 The 5th val is 10[getMinKthOn]$ ./getMinKthOn 6Array first 0end 7:2 10 3 9 20 6 1 100 The 6th val is 20[getMinKthOn]$ ./getMinKthOn 7Array first 0end 7:2 10 3 9 20 6 1 100 The 7th val is 100

代码写的有点罗嗦，中间也调试了好几次。

后面有时间的时候，可以慢慢改进。