c 求n个数的中位数-ag真人游戏

/*
 * 求n个数的中位数 - c   - by chimomo
 *
 * 对于一组有有限个数的数据来说，它们的中位数是这样的一种数：这群数据里的一半的数据比它大，而另外一半数据比它小。
 * 计算有限个数的数据的中位数的方法是：把所有的同类数据按照大小的顺序排列。
 * 如果数据的个数是奇数，则中间那个数据就是这群数据的中位数；
 * 如果数据的个数是偶数，则中间那2个数据的算术平均值就是这群数据的中位数。
 */
#include 
#include 
#include 
#include 
using namespace std;
int quicksortonce(int a[], int low, int high) {
    // 将首元素作为枢轴。
    int pivot = a[low];
    int i = low, j = high;
    while (i < j) {
        // 从右到左，寻找首个小于pivot的元素。
        while (a[j] >= pivot && i < j) {
            j--;
        }
        // 执行到此，j已指向从右端起首个小于或等于pivot的元素。
        // 执行替换。
        a[i] = a[j];
        // 从左到右，寻找首个大于pivot的元素。
        while (a[i] <= pivot && i < j) {
            i  ;
        }
        // 执行到此，i已指向从左端起首个大于或等于pivot的元素。
        // 执行替换。
        a[j] = a[i];
    }
    // 退出while循环，执行至此，必定是i=j的情况。
    // i（或j）指向的即是枢轴的位置，定位该趟排序的枢轴并将该位置返回。
    a[i] = pivot;
    return i;
}
void quicksort(int a[], int low, int high) {
    if (low >= high) {
        return;
    }
    int pivot = quicksortonce(a, low, high);
    // 对枢轴的左端进行排序。
    quicksort(a, low, pivot - 1);
    // 对枢轴的右端进行排序。
    quicksort(a, pivot   1, high);
}
int evaluatemedian(int a[], int n) {
    quicksort(a, 0, n - 1);
    if (n % 2 != 0) {
        return a[n / 2];
    } else {
        return (a[n / 2]   a[n / 2 - 1]) / 2;
    }
}
int main() {
    int a[9] = {-5, 345, 88, 203, 554, 1, 89, 909, 1001};
    cout << evaluatemedian(a, 9) << endl;
    return 0;
}
// output:
/*
203
*/