Medians and Order Statistics (次序统计) -

kuchaguangjie

浏览: 444109 次
性别:
来自: 深圳

最近访客更多访客>>

haeng

freecutelei

xuhuanfeng

超神不坑

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

Medians and Order Statistics (次序统计)

博客分类：

algorithm

prototype 算法 XHTML

Medians and Order Statistics

------
概述

Order Statistics:
      次序统计，即找出 n 个数中排在第 i 位的那个数，记为 ith

Medians:
      中位数，排在中间的数，

------
Medians 的取值

假设所有的数都不相同，则：
      n = odd 时，只有1个中间数，i = (n+1)/2,
      n = even 时，有2个中间数，i = n/2 和 i = n/2 + 1,

      可以合并为：
            i =
                  lower((n + 1)/2),
                  upper((n + 1)/2),
            对于 odd 2者相同，对于 even 2者不同，

------
最大 & 最小值

通过 n-1 次比较可以找出最大或最小值，
如果要同时找2者，则可以合并一下，让比较次数小于 2*(n-1),因为如果一个数比另1个数小，则该数必定不是最大值，反之亦然，

------
次序查找 - 每次分割2组实现

概述：
      通过分隔函数实现查找，

效率：
      时间复杂度：预期效率是 O(n)
      空间复杂度： O(n)

思路：
      基于 quicksort 改造，但每次只取其中的一半，从而效率降低到 O(n),

分隔函数的逻辑：
      * 取分隔值，
      * 如果分隔值就是目标值，则 ok
      * 否则将数组分隔为左右2个，
      * 判断目标数在哪个数组内，保留那个数组，对其循环调用分隔函数
      *

时间复杂度证明：
      略，看 <算法导论> chp9.2

------
次序查找 - 每组5个分割实现

较为复杂，最差情况下时间复杂度为 O(n)，

参考：<算法导论> chp9.3

------
例子：

(顺序号查找 - 每次分割2组实现)

* js(order_statistic.js)

var arr_order_statistic = [ 78, 13, 6, 177, 26, 90, 288, 45, 62, 83 ];

/**
 * <p>
 * order statistic , 找出排序为 i 的值
 * </p>
 * <b>思路：</b><br />
 * 基于 quicksort 改造，但每次只取其中的一半，从而效率降低到 O(n),<br />
 * 
 * <pre>
 * 分隔函数的逻辑：
 * 	取分隔值，
 * 	如果分隔值就是目标值，则 ok
 * 	否则 将数组分隔为 左右2个，
 * 	判断目标数在哪个数组内，保留那个数组，对其循环调用分隔函数
 * </pre>
 * 
 * <b>时间复杂度：</b>O(n)<br />
 * <b>空间复杂度：</b>O(n)<br />
 * 
 * @author kuchaguangjie
 * @date 2011年1月3日
 * @return
 */
function OrderStatistic(inputArr) {
	this.inputArr = inputArr;
}
/**
 * 单次分隔
 * 
 * @param arr
 * @param i
 *            在 arr 中的排序，从 0 开始
 * @return 存有目标值的子数组 或 目标值
 */
OrderStatistic.prototype.partitionSingle = function(arr, i) {
	if (arr.length <= 1) { // length == 1 的情况，length == 0 应该在上层函数中排除掉，
		return new OrderStaticResult(true, undefined, undefined, arr[0]);
	}
	var partLeftArr = [];
	var partRightArr = [];
	var partMiddle = arr[arr.length - 1]; // 最后1个元素，用作分隔值
	for ( var x = 0; x < arr.length - 1; x++) {
		if (arr[x] <= partMiddle) {
			partLeftArr[partLeftArr.length] = arr[x];
		} else {
			partRightArr[partRightArr.length] = arr[x];
		}
	}
	if (partLeftArr.length == i) { // 分隔值 即是 目标值
		return new OrderStaticResult(true, undefined, undefined, partMiddle);
	} else if (partLeftArr.length > i) { // 目标值 在 左子数组
		return new OrderStaticResult(false, partLeftArr, i);
	} else { // 目标值 在 右子数组
		i -= (partLeftArr.length + 1); // 调整 i
		return new OrderStaticResult(false, partRightArr, i);
	}
};
/**
 * 分隔函数，直到找到目标值为之
 * 
 * @param i
 * @return
 */
OrderStatistic.prototype.partition = function(i) {
	var arr = this.inputArr;
	var osr;
	while (true) {
		osr = this.partitionSingle(arr, i);
		if (osr.ok) {
			return osr.v;
		} else {
			arr = osr.subArr;
			i = osr.i;
		}
	}
};
/**
 * 根据 排序号 找到数
 * 
 * @param order
 *            排序号，从 1 开始
 * @return
 */
OrderStatistic.prototype.getByOrder = function(order) {
	if (this.inputArr.length == 0 || this.inputArr.length < order) {
		alert('输入有误！');
	} else {
		var i = order - 1; // index 从 0 开始，而顺序号是从 1 开始，这里做调整
		return this.partition(i);
	}
};

/**
 * 单次 分隔计算 后的返回值
 * 
 * @param ok
 *            boolean 值，表示 是否已找到
 * @param subArr
 *            目标值所在的子数组，当 ok = false 时，采用此数组
 * @param i
 *            目标值在的子数组中的排序，从 0 开始，当 ok = false 时，采用此值
 * @param v
 *            目标值，当 ok = true 时，才用此值
 * @return
 */
function OrderStaticResult(ok, subArr, i, v) {
	this.ok = ok;
	this.subArr = subArr;
	this.i = i;
	this.v = v;
}

* html

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<script type="text/javascript" src="js/order_statistic.js"></script>
</head>
<body>
<input type="button" value="order statistic" onclick="var i = 6;alert(arr_order_statistic + ' 中，\n排在第'+ i +'位的是： '+ new OrderStatistic(arr_order_statistic).getByOrder(i));" />
</body>
</html>

*

------

分享到：

ubuntu 下安装 tomcat | counting sort

2011-01-03 14:36
浏览 2836
评论(0)
分类:编程语言
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

Medians and Order Statistics (次序统计)

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

Medians and Order Statistics (次序统计)

评论

发表评论

相关推荐

c - linkedlist

c - word counter (binary-tree)

random select

sparse data structure - matrix

max sub_sequence - c

binary search - c

bit_array - simple use

linkedlist - java 简单实现

queue (用 java 简单实现)

counting sort

quick sort

priority queue

heap sort

merge sort

insertion sort

z 字型 读取 矩阵

排序算法：求 长度为 n的 数组中，最大的 m个数

已排序数组 a，求其元素的绝对值 共有多少个不同的值

binary search

An Introduction to Algorithm 2nd 's contents

最近访客更多访客>>

z 字型读取矩阵

排序算法：求长度为 n的数组中，最大的 m个数

已排序数组 a，求其元素的绝对值共有多少个不同的值