【思维】中位数与顺序统计 - BlueDream
算法定义
在统计学中，中值（又称中位数）代表一个样本、种群或概率分布中的一个数值，其可将数值集合划分为相等的上下两部分。对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中值。如果观察值有偶数个，则中值不唯一，通常取最中间的两个数值的平均数作为中值。
一个数集中最多有一半的数值小于中值，也最多有一半的数值大于中值。如果大于和小于中值的数值个数均少于一半，那麽数集中必有若干值等同于中值。
设连续随机变量X的分布函数为F(X)，那么满足条件P(X≤m)=F(m)=1/2的数称为X或分布F的中位数。
对于一组有限个数的数据来说，它们的中位数是这样的一种数：这群数据里的一半的数据比它大，而另外一半数据比它小。 计算有限个数的数据的中位数的方法是：把所有的同类数据按照大小的顺序排列。如果数据的个数是奇数，则中间那个数据就是这群数据的中位数；如果数据的个数是偶数，则中间那2个数据的算术平均值就是这群数据的中位数。中位数统计学的函数符号为MEDIAN。
算法描述
针对中位数，我们可以抽象的定义一个选择问题，描述如下：
输入：一个包含n个不同数的集合A和一个数i, i <= i <= n
输出:恰大于A中i-1个元素的那个元素
白话描述: 写一个函数，输入一个数组和索引。返回第索引大的数字。如[1,5,6,3] 中第2(i=2)大的元素为3.
针对这个需求。最直观的想法是找一个比较好的排序算法如堆排序等，用n(lgn)的复杂度排好序然后用线性的复杂度选择元素。那么是否还有更优复杂度的算法呢？显然是有的。
这里的算法整个思路和前面讲的 随机版快速排序的思路是一致的。平均复杂度为O(n)的线性复杂度
源码描述
function RandomSelect(arr, start, end, i) {if (start == end) return arr[start];
// 随机选择一个分割下标
var q = RandomPartition(arr, start, end);
var k = q - start + 1;
// 如果所需要的值的大小位置正好等于K下标。那么直接返回
if (i == k) {
return arr[q];
// 如果小于K那么表示所需的元素在前一半分割元素堆里。那么直接在start~q-1的堆里去找第i个大小元素即可
} else if (i < k) {
return RandomSelect(arr, start, q-1, i);
// 如果大于K那么表示所需的元素在后一半分割元素堆里。那么已经排除了K个元素。所以应该找第i-k大的元素
} else {
return RandomSelect(arr, q+1, end, i-k);
}
}
function swap(arr, a, b) {
if (a == b) return;
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
// 数组分割
function Partition(arr, start, end) {
var pivot = arr[end]; // 将数组最后一个元素作为主元
var i = start - 1; // 指定一个指针
for (var j = start; j < end; j++) {
if (arr[j] <= pivot) { // 如果当前元素小于主元
i = i + 1;
swap(arr, i, j);
}
}
swap(arr, i + 1, end);
return (i + 1);
}
// 随机交换主元后再Partition
function RandomPartition(arr, start, end) {
var i = Math.floor(Math.random() * (end - start + 1) + start);
swap(arr, end, i);
return Partition(arr, start, end);
}
var arr = [1,3,6,8,4], len = arr.length-1;
var re = RandomSelect(arr, 0, len, 2);
alert(re);
本文链接：http://www.cnblogs.com/bluedream2009/archive/2011/04/28/2031260.html，转载请注明。
文章来源：
Author：BlueDream
link：http://www.cnblogs.com/bluedream2009/archive/2011/04/28/2031260.html