// 数组A中的每一个元素都有两个属性,分别为x和w,x表示数值,w表示权重。 GET-WEIGHTED-MEDIAN1(A, n) sort A[1 : n] by key x s = 0 for i = 1 to n s = s + A[i].w if s >= 0.5 return A[i].x return NIL
// PARTITION-WEIGHTED返回两个值,一个是划分后这个数的下标q,一个是A[p : q]中所有数的权值之和。 PARTITION-WEIGHTED(A, p, r) s = 0 x = A[r].x // the pivot i = p – 1 // highest index into the low side for j = p to r – 1 // process each element other than the pivot if A[j].x < x // does this element belong on the low side? i = i + 1 // index of a new slot in the low side exchange A[i] with A[j] // put this element there exchange A[i + 1] with A[r] // pivot goes just to the right of the low side return i + 1, s + A[i + 1].w
RANDOMIZED-PARTITION-WEIGHTED(A, p, r) i = RANDOM(p, r) exchange A[r] with A[i] return PARTITION-WEIGHTED(A, p, r)
// 目标是求出最小的数x,使得小于等于x的所有权值之和大于等于0.5. MEDIAN-WEIGHT(A, n) pw = 0.5 p = 1 r = n while p < r q, nw = RANDOMIZED-PARTITION(A, p, r) if nw >= pw r = q else pw = pw - nw p = q + 1 return A[p].x
SELECT'(A, n, i) if 2 * i >= n return SELECT(A, 1, n, i) if n % 2 == 1 INSERT(A, +∞) n += 1 m = n / 2 for i = 1 to m if A[i] > A[i + m] exchange A[i] with A[i + m] combine A[i] and A[i + m] SELECT'(A[1 : m], m, i) let B[1 : i + i] be new array for j = 1 to i B[j] = A[i] B[j + i] = the number that A[i] combine return SELECT(B, 1, i + i, i)