这一章《中位数和顺序统计学》很短，也是本书第二部分的最后一章
写几段代码吧。
求数组最小值
Java代码
int minimum(int[] a) {
int min = a[0];
for (int i = 1; i < a.length; i++) {
if (min > a[i]) {
min = a[i];
}
}
return min;
}
这个不用写测试，就当没写过。 这个方法需要做 n-1 次比较
同时找出最大值，最小值
如果用上面的方法，那么这个问题使用 2(n-1) 次比较肯定能解决。 当然可以更少一些。
Java代码
int[] minAndMax(int[] a) {
int i = 1;
int min = a[0];
int max = a[0];
if ((a.length & 1) == 0) { // 偶数
i = 2;
max = a[1];
}
if (min > max) {
// swap
int t = min;
min = max;
max = t;
}
// 下面从 i 开始，直到结束，共有偶数个数, 每次处理两个
for (; i < a.length; i += 2) {
int m = a[i];
int n = a[i + 1];
if (m > n) {
// swap
int t = m;
m = n;
n = t;
}
// now m <= n
if (min > m) {
min = m;
}
if (max < n) {
max = n;
}
}
int[] b = { min, max };
return b;
}
现在 每次循环 进行3 次比较， 共进行 3((n - 1) / 2) 次比较, 加上循环前的一次比较，共进行 3(n / 2) 次比较
选择第 i 小的数
我们可以进行一次排序，然后再输出第 i 小的数， 但这样复杂度会和排序一样
可以有更好的方法：
Java代码
int randSelect(int[] ary, int left, int right, int index) { // 从[left, right] 中找出第 index 小的数
if (left > right || index > right - left) {
throw new IllegalArgumentException();
}
if (left == right) {
return ary[left]; // 此时 index == 0
}
int mid = partition(ary, left, right); // 对数组进行一次划分，[left, mid - 1] [mid] [mid + 1, right]
int len = mid - left;
if (index == len) { // 刚好
return ary[mid];
} else if (index < len) { // 要找的数在左区间
return randSelect(ary, left, mid - 1, index);
} else { // 要找的数在右区间， 当然此时要找第 index - len - 1小的数，因为要扣除左区间以及mid
return randSelect(ary, mid + 1, right, index - len - 1);
}
}
其中 partition 在快速排序中遇到过
Java代码
int partition(int[] a, int low, int high) {
int x = a[low];
int m = low;
for (int i = low + 1; i <= high; i++) {
if (a[i] < x) {
swap(a, ++m, i);
}
}
swap(a, low, m);
return m;
}
void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
不忙， 写个测试先。
Java代码
@Test
public void testRandSelect() {
Random rand = new Random();
for (int i = 0; i < 100; i++) {
int[] a = genRandAry(i + 1);
int[] b = Arrays.copyOf(a, a.length); // 因为 randSelect会对数组a进行重排，所以先copy一份
int k = rand.nextInt(a.length); // 我们要从a中选出第 k 小的数
int m = randSelect(a, 0, a.length - 1, k);
Arrays.sort(b); // 再对b进行排序
assertEquals(b[k], m); // 此时 m 就应该和 b[k] 一样
}
}
可以看到，运行是通过的：）
下面我们看分析其复杂度。
首先重构 randSelect 将其修改为求比较次数
Java代码
int randSelect2(int[] ary, int left, int right, int index) {
if (left > right || index > right - left) {
throw new IllegalArgumentException();
}
if (left == right) {
return 0; // modified
//return ary[left];
}
int times = right - left; // 下面的partition要作 right - left 次比较, 见快速排序（笔记4)
int mid = partition(ary, left, right);
int len = mid - left;
if (index == len) {
return times;
//return ary[mid];
} else if (index < len) {
return times + randSelect(ary, left, mid - 1, index); // modified
} else {
return times + randSelect(ary, mid + 1, right, index - len - 1); // modified
}
}
然后对上面的方法进行简化
1. 参数检查不需要
2. left == right 测试 ---> n == 0
3. 把left 和 right 等表示成 n 相关, 并去掉 a， index
3. 在一般情况下，partition 分得很平均, 并且我们假设代码路径都只经过 index < len 这个分支
上面的方法即可简化成求平均比较次数
Java代码
int randSelect2(int n) {
if (n == 0) {
return 0;
}
int times = n - 1; // partition比较次数
return times + randSelect2(n / 2); // 每次分割后n 减半
}
写成递归式就是 T(n) = T(n / 2) + (n - 1)
上面这个写成数列就是： (n - 1) + (n - 1) / 2 + (n - 1) / 4 + (n - 1) / 8 + ...
即 (n - 1)( 1 + 1/2 + 1/4 + 1/8 + ..) ---> 差不多的 2(n-1)
所以randSelect算法复杂度是线性的