前言

這一篇文章就上上一篇博文算法的進一步優化了！
這里我們就利用中位數來進行線性時間的選擇算法！

中位數就是指將數據按大小順序排列起來，形成一個數列，居于數列中間位置的那個數據就是中位數。

算法思路

（1）將輸入的n個數劃分成 ?n5? 個組，當然最后一組的數目可能是小于5的！
（2）用任意的排序方法對他們進行排序，并取出一共 ?n5? 個中位數。
（3）找出該 ?n5? 個中位數中的中位數。（如果 ?n5? 是偶數則取相對大的那個數）
（4）將全部的數劃分為兩個部分，小于基準的在左邊，大于等于基準的放右邊。

我們用小圓點表示元素，得到如下圖：

說明：
圖中中間白色圈表示各組數據的中位數，最中間灰色表示中位數的中位數！ 箭頭是從較小的數指向較大的數！

故我們可以使用該數作為劃分的基準（比上一個隨機基準的方法會好很多）！

圖中

3?A1=3?(n?5)10
當n≥75時，3A1大于等于 14n。所以按此基準劃分所得的左右2個子數組的長度都至少縮短 14。

代碼描述

int Select(int a[],int p,int r,int k) { if(r-p<75) { //這里對數組 a[p->r] 進行排序 return a[p+k-1]; } //(r-p-4)/5相當于n-5 for(int i=0; i<=(r-p-4)/5; i++) { //這里將元素每5個分成一組，分別排序，并將該組中位數與a[p+i]交換位置 //使所有中位數都排列在數組最左側，以便進一步查找中位數的中位數 } int x = Select(a,p,p+(r-p-4)/5,(r-p-4)/10); //找中位數的中位數 int i = Partition(a,p,r,x); //以x為基準對數組a進行劃分 int j = i-p+1; if(k<=j) { return Select(a,p,i,k); } else { return Select(a,i+1,r,k-j); } }

總結

以上是生活随笔為你收集整理的递归与分治策略之利用中位数线性时间选择的全部內容，希望文章能夠幫你解決所遇到的問題。

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