[算法] 中位数和第i个顺序统计量

基础算法

1. 最大值或最小值

单求最大或最小时间，但同时找到最大值和最小值并不需要，成对比较(一次比较当前两数大小，将记录最小值和当前小值比，记录最大值和当前大值比)可将4次比较减为3次，时间

2. 求第i个顺序统计量

使用快排的partition，但根据返回的q值的位置q-p+1与i比较，递归调用划分的一边继续求解（快排需要处理划分的两边）
用random partition思想期望时间，最坏情况
优化：
先分组再partition可实现最坏（算法导论9.3）

应用

中位数问题延伸：

中位数实际上是一组数中各变量与其距离绝对值之和最小的点。
例如输油管道问题、带权中位数问题

partition思想延伸：

用partition思想可以将许多算法时间上限由排序时间所限制但实际上并不需要对所有元素的两两相对位置进行排序的算法进行改进，将时间降为。
例如分数背包优化、求两个有序数组的中位数

分数背包优化

应用partition函数根据随机选择的某位置的物品的单位重量的价值将物品列表划分为三部分：：中的物品单位重量的价值大于划分点，中物品单位重量的价值等于划分点，中物品单位重量的价值小于等于划分点（不需要生成新的三个子集合，使用数组下标控制下述处理即可）。

1. 若 ，则不放入任何物品，递归求解物品集合和背包重量时的解决方案；

2. 若 ，则把中的物品全部放入背包，并尽可能放入中的物品；

​ a. 若，则在尽可能多得放入集合的物品后算法结束；

​ b. 若，则在集合的物品全部放入后，递归求解物品集合和背包重量时的解决方案。

与快速排序的排序主方法不同的是，此次我们并不需要对划分点左右两侧都递归调用求解，而只需要根据剩余容量进行判断单侧递归调用求解即可，时间复杂度。实现代码如下：

typedef struct item{
    int v;
    int w;
} item;

double calcVPW(item a){
    return a.v / (double)a.w;
}

void swapItem(item& a, item& b){
    item tmp = a;
    a = b;
    b = tmp;
    return;
}

int partition(vector<item>& A, int p, int r) {
    double x = calcVPW(A[r]);
    int i = p-1;
    for (int j = p; j < r; j++) {
        if (calcVPW(A[j]) > x) {
            i++;
            swapItem(A[i], A[j]);
        }
    }
    swapItem(A[i+1], A[r]);
    return i+1;
}

// 设背包总容量为W
double fracKnapsack (vector<item>& A, int W, int p, int r){
    int q = partition(A, p, r);
    double resValue = 0.0;
    int currentW = 0.0;
    int sumWL = 0.0;
    double sumVL = 0.0;
    for (int i = p; i < q; i++){
        sumWL += A[i].w;
        sumVL += A[i].v;
    }
    if(sumWL > W){
        return fracKnapsack(A, W, p, q-1);
    } else {
        resValue += sumVL;
        currentW += sumWL;
        if (currentW + A[q].w <= W) {
            currentW += A[q].w;
            resValue += A[q].v;
            return fracKnapsack(A, W - currentW, q+1, r);
        } else {
            int leftW = W - currentW;
            resValue += A[q].v / (double)A[q].w * leftW;
            return resValue;
        }
    }
}