《算法导论的Java实现》 10 中位数和顺序统计学

Blog地址《算法导论的Java实现》 10 中位数和顺序统计学10 中位数和顺序统计学10.1 最大元素和最小元素
伪代码：MINIMUM(A)
1  min ← A[1]
2  for i ← 2 to length[A]
3         do if min > A[i]
4                then min ← A[i]
5  return min
Java代码：import java.util.Comparator;public class Minimum { public static <T> T minimum(T[] t, Comparator<? super T> comparator) {
T min = t[0];
for (int i = 1; i < t.length; i++)
if (comparator.compare(min, t[i]) > 0)
min = t[i];
return min;
} public static void main(String[] args) {
Integer[] ints = new Integer[] { 31, 41, 59, 26, 41, 58 };
Integer min = minimum(ints, new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o1.intValue() - o2.intValue();
}
});
System.out.println(min);
}
}
输出：
26code后感
这可能是《算法导论》里面最简单的程序之一。但是《算法导论》一书的最大特点就是，算法本身不难，或者说，像我现在这样的工作：把伪代码用某种具体语言去实现一遍，是非常容易的事儿。
但是算法的分析，却绝不简单。比如，要证明MINIMUM算法是最优的；再比如，去分析伪代码的第4行，赋值次数的期望值，都是不太容易的事儿。对于普通的程序员来说，也许未必就一定要掌握这些，只要记住一些结论也就可以了————第4行被执行的期望值是Θ（lg n）。
10.2 以线性期望时间做选择
伪代码：RANDOMIZED-SELECT(A, p, r, i)
1  if p = r
2      then return A[p]
3  q ← RANDOMIZED-PARTITION(A, p, r)
4  k ← q - p + 1
5  if i = k          ▹ the pivot value is the answer
6      then return A[q]
7  elseif i < k
8      then return RANDOMIZED-SELECT(A, p, q - 1, i)
9  else return RANDOMIZED-SELECT(A, q + 1, r, i - k)
Java代码：import java.util.Comparator;
import java.util.Random;public class RandomizedSelect { public static <T> int partition(T[] a, Comparator<? super T> c, int p, int r) {
T t = a[r - 1];
int i = p - 1;
for (int j = p; j < r - 1; j++) {
if (c.compare(a[j], t) <= 0) {
i++;
T tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
} T tmp = a[i + 1];
a[i + 1] = a[r - 1];
a[r - 1] = tmp;
return i + 1;
} public static <T> int randomizedPartition(T[] a, Comparator<? super T> c,
int p, int r) {
int i = new Random().nextInt(r - p) + p;
T tmp = a[i];
a[i] = a[r - 1];
a[r - 1] = tmp;
return partition(a, c, p, r);
} public static <T> T randomizedSelect(T[] t,
Comparator<? super T> comparator, int p, int r, int i) {
if (p == r)
return t[p];
int q = randomizedPartition(t, comparator, p, r);
int k = q - p + 1;
if (i <= k)
return randomizedSelect(t, comparator, p, q, i);
else
return randomizedSelect(t, comparator, q + 1, r, i - k);
} public static <T> T randomizedSelect(T[] t,
Comparator<? super T> comparator, int i) {
return randomizedSelect(t, comparator, 0, t.length, i);
} public static void main(String[] args) {
Integer[] ints = new Integer[] { 31, 41, 59, 26, 41, 58 };
Integer positiong = randomizedSelect(ints, new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o1.intValue() - o2.intValue();
}
}, 3);
System.out.println(positiong); }
}
输出：
41
code后感
我有点晕： 快速排序的随机化版本的函数RANDOMIZED-PARTITION居然可以用在这里。用线性时间得到数组里面的最大或者最小值，实在是一个小学生都会做的事儿————一个一个比较就可以了。
但是，用线性时间得到数组第N大的值，就不那么容易了。《算法导论》里面说，“一般选择性问题看起来要比寻求最小元问题跟难些。但是令人惊奇的是，两个问题的渐近时间是一样的：都是Θ（n）”。
这真的很令人惊奇，可以想象一下，让一个小学生去从10个数字里面选出第3小的那个。他会怎么做呢？小学生也许会先找到最小的，再找到次小的，最后找到第3小的那个。
如果这样，那么算法复杂度肯定是n的二次方了。
RANDOMIZED-SELECT的神奇之处在于它的渐近时间居然是Θ（n）！