《算法导论》读书笔记6(中位数和顺序统计学)

这一章《中位数和顺序统计学》很短，也是本书第二部分的最后一章

 

写几段代码吧。

 

求数组最小值

 

	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) 次比较肯定能解决。 当然可以更少一些。

 

	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 小的数， 但这样复杂度会和排序一样

 

可以有更好的方法：

 

	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 在快速排序中遇到过

 

	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;
	}

 

不忙， 写个测试先。

 

	@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 将其修改为求比较次数

 

 

	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 这个分支

 

上面的方法即可简化成求平均比较次数

 

	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算法复杂度是线性的 

 

当然也可以使用算法笔记2中的工具进行绘制, 看其复杂度

 

 

和2(n-1)相符!