算法定義

在統計學中，中值（又稱中位數）代表一個樣本、種群或概率分布中的一個數值，其可將數值集合劃分為相等的上下兩部分。對于有限的數集，可以通過把所有觀察值高低排序后找出正中間的一個作為中值。如果觀察值有偶數個，則中值不唯一，通常取最中間的兩個數值的平均數作為中值。

一個數集中最多有一半的數值小于中值，也最多有一半的數值大于中值。如果大于和小于中值的數值個數均少于一半，那麼數集中必有若干值等同于中值。

設連續隨機變量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);

?

?

?

轉載于:https://www.cnblogs.com/bluedream2009/archive/2011/04/28/2031260.html

總結

以上是生活随笔為你收集整理的【思维】中位数与顺序统计的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。