《算法导论》学习笔记之Chapter9中位数和顺序统计量

第9章 中位数和顺序统计量

先定义：在一个由n个元素组成的集合中，第i个顺序统计量是该集合中第i小的元素。一个中位数是它所属集合的“中点元素”。当n是奇数时，中位数是唯一的，位于i=n/2处。当n为偶数时，中位数有两个，分别位于i = n/2和i=n/2+1处。不考虑n的奇偶性，中位数总是出现在i=(n+1)/2向下取整处，也叫下中位数，和i=(n+2)/2向上取整处，也叫上中位数。本书默认下中位数。

本章讨论的是：从n个互异的元素构成的集合中选择第i个顺序统计量的问题。

如果不学习其他方法，仅使用前面介绍的算法，可以考虑使用归并排序或堆排序的算法，在O(nlogn)时间内完成查找。下面会介绍一个更快的方法。

求最大值最小值问题：

单词求最大值或最小值，会进行θ(n)次的比较，如果同时求出最大值最小值，简单来说可能需要2n-2次比较。但是，稍微改变一下：提前记录已知的最大值和最小值，每次选择一对数据进行比较，较大的与最大值比较，较小的与最小值比较，这样每次进行3次比较，总体会进行3(n/2)向下取整次比较，效率提升不少。

该问题中：如何设定已知的最大值和最小值取决n的奇偶性：n为奇数时，取第一个元素作为最大值最小值，后面元素成对比较；n为偶数时，对前两个元素进行比较，大的作为最大值，小的作为最小值，之后与n为奇数时相同的比较过程。若n为奇数，总比较次数为3(n/2)向下取整次；n为偶数，总比较次数为3(n-2)/2+1，共3n/2-2次比较。所以，不管哪一种情况，总的比较次数最多是3(n/2)向下取整次。

基于快速排序算法的线性时间选择算法：

相同点是：均采用递归划分数据；

区别是：快速排序处理划分的两边，期望运行时间是θ(nlogn)；

               选择算法只处理划分的一边,期望运行时间是线性时间θ(n)；

下面介绍一个期望运行时间（注意：是期望，不是最坏运行时间）是线性时间的选择算法，代码实现如下：

// 基于快排的线性时间选择算法，选择数组中第i小的元素
	public static int RandomizedSelect(int[] a, int p, int r, int i) {
		if (p == r) {
			return a[p];
		}
		// q的左侧是比q小的，右侧是比q大的
		int q = RandomPartition(a, p, r);
		// k坐标表示的该元素是在数组中排行第k的数据；
		int k = q - p + 1;
		if (i == k) {
			return a[q];
		} else if (i < k) {
			return RandomizedSelect(a, p, q - 1, i);
		} else {
			return RandomizedSelect(a, q + 1, r, i - k);
		}
	}

上述算法最坏情况运行时间是θ(n.^2)，但是因为是随机化的，所以不存在一个特定的情况导致最坏情况发生，该算法有线性的期望运行时间θ(n)。

下面是一个最坏情况是线性时间的选择算法：

该算法的原理图如下：

左侧算法原理代码实现如下：

private static int select(int[] a, int l, int r, int k) {
		if (r - l < 75) {
			insertSort(a, l, r); // 当数组个数较小时，用快速排序进行排序
			return a[l + k - 1];
		}
		int group = (r - l + 5) / 5;//对数组进行分组，每组5个元素。其中加5操类似于向上取整
		for (int i = 0; i < group; i++) {//该循环结束之后会导致数组中的前group个数被所有子数组的中位数替代
			int left = l + 5 * i;
			int right = (l + i * 5 + 4) > r ? r : l + i * 5 + 4; // 如果超出右边界就用右边界赋值
			insertSort(a, left, right);//对每组进行插入排序
                        int mid = (left + right) / 2;//找到中间坐标
			swap(a, l + i, mid); // 将各组中位数与前i个交换
		}
		int pivot = select(a, l, l + group - 1, (group + 1) / 2); // 找出中位数的中位数
		int p = partition(a, l, r, pivot); // 用中位数的中位数作为主元的位置
		int leftNum = p - l; // leftNum用来记录主元位置的前边的元素个数
		if (k == leftNum + 1)
			return a[p];
		else if (k <= leftNum)
			return select(a, l, p - 1, k);
		else // 若k在主元位子的后边，则要从主元位置的后边数起，即第（k - leftNum - 1）个
			return select(a, p + 1, r, k - leftNum - 1);
	}

	// 适用于线性时间选择的partition方法
	private static int partition(int[] a, int l, int r, int pivot) { 
		int i = l;
		int j = r;
		while (true) {
			while (a[i] <= pivot && i < r)
				++i; // i一直向后移动，直到出现a[i]>pivot
			while (a[j] > pivot)
				--j; // j一直向前移动，直到出现a[j]<pivot
			if (i >= j)
				break;
			swap(a, i, j);
		}
		a[l] = a[j];
		a[j] = pivot;
		return j;
	}

	private static void insertSort(int[] a, int low, int high) { // 插入排序
		for (int i = low + 1; i <= high; i++) {
			int key = a[i];
			int j = i - 1;
			while (j >= low && a[j] > key) {
				a[j + 1] = a[j];
				j--;
			}
			a[j + 1] = key;
		}
	}

与比较排序一样，上述选择算法也是通过元素之间的比较来确定彼此之间的次序的，但是不同的是，上述选择算法在没有排序的情况下就已经解决了选择问题，所以运行时间并不受Ω(nlogn)的限制，而是线性运行时间。且与第8章介绍的线性运行时间不同的是，对输入并没有任何限制。

备注：后面的代码参考别人的博客内容，链接如下：http://blog.csdn.net/notfamous/article/details/23261341