線性時間選擇算法

1、福州大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院計算機(jī)算法設(shè)計與分析上機(jī)實驗報告（1）專業(yè)和班級數(shù)學(xué)02班姓名詹小青成績學(xué)號031201206實驗名稱線性時間選擇算法實驗?zāi)康?通過實驗，至少掌握一種線性時間選擇算法實驗任務(wù) 設(shè)計一種線性時間選擇算法，證明算法的正確性并且分析它的時間復(fù)雜度。實驗步驟 1、算法設(shè)計思想（最壞情況線性時間做選擇）： 這種算法基本思想是保證每個數(shù)組的劃分都是一個好的劃分，以5為基，五數(shù)取分。利用它的思想，可以快速返回和最終中位數(shù)相差不超過2的數(shù)，這樣的劃分接近最優(yōu)，基本每次都二分了。 2、算法基本步驟： 算法SELECT通過執(zhí)行下列步驟來確定一個有n個元素的輸入數(shù)組中的第i個小的元素。1

2、）將輸入數(shù)組的n個元素劃分為n/5組，每組5個元素，且至多有一個組由剩下的n mod 5個元素組成；2）尋找n/5個組中每一組的中位數(shù)。（方法首先對每組中的元素進(jìn)行插入排序，然后從排序過的序列中選出中位數(shù)）；3）對第2步中找出的n/5個中位數(shù)，遞歸調(diào)用SELECT找出其中位數(shù)x。（如果有偶數(shù)個中位數(shù)，根據(jù)約定，x是下中位數(shù)。）4)利用修改過的PARTITION過程，按中位數(shù)的中位數(shù)x對輸入數(shù)組進(jìn)行劃分。讓k比劃分低區(qū)的元素多1，所以x是第k小的元素，并且有n-k個元素在劃分的高區(qū)；5)如果i=k，則返回x，否則，如果i<k，則在低區(qū)遞歸調(diào)用SELECT以找出第i小的元素，如果i>k

3、，則在高區(qū)找第（i-k）個最小元素。 3、時間復(fù)雜度分析： 圖中箭頭指向表示大的數(shù)值指向小的數(shù)值，所以根據(jù)圖可以看出，在x的右邊，每一個包含5個元素的組中至少有3個元素大于x，在x的左邊，每一組中至少有3個元素小于x（保證x分割一邊必定有元素存在）。 圖中顯示的中位數(shù)的中位數(shù)x的位置，每次選取x作為劃分的好處是能夠保證必定有一部分在x的一邊。所以算法最壞情況的遞歸公式可以寫成：，使用替換法可以得出。4、算法代碼：#include <iostream> #include <ctime> using namespace std; template <class Typ

4、e> void Swap(Type &x,Type &y); inline int Random(int x, int y); template <class Type> int Partition(Type a,int p,int r); template<class Type> int RandomizedPartition(Type a,int p,int r); template <class Type> Type RandomizedSelect(Type a,int p,int r,int k); int main() vo

5、id SelectionSort(int a);int s;int a2000;int b2000; for(int i=0; i<2000; i+) ai=bi=rand()%10000; cout<<ai<<" " cout<<endl;SelectionSort(b);for(int j=0;j<2000;j+)printf("a%d:%d ",j+1,bj);cout<<endl;printf("請輸入要求的第幾最小數(shù)：");scanf("%d",

6、&s); cout<<RandomizedSelect(a,0,1999,s)<<endl; template <class Type> void Swap(Type &x,Type &y) Type temp = x; x = y; y = temp; inline int Random(int x, int y) srand(unsigned)time(0); int ran_num = rand() % (y - x) + x; return ran_num; template <class Type> int Pa

7、rtition(Type a,int p,int r) int i = p,j = r + 1; Type x = ap; while(true) while(a+i<x && i<r); while(a-j>x); if(i>=j) break; Swap(ai,aj); ap = aj; aj = x; return j; template<class Type> int RandomizedPartition(Type a,int p,int r) int i = Random(p,r); Swap(ai,ap); return Par

8、tition(a,p,r); template <class Type> Type RandomizedSelect(Type a,int p,int r,int k) if(p = r) return ap; int i = RandomizedPartition(a,p,r); int j = i - p + 1; if(k <= j) return RandomizedSelect(a,p,i,k); else /由于已知道子數(shù)組ap:i中的元素均小于要找的第k小元素 /因此，要找的ap:r中第k小元素是ai+1:r中第k-j小元素。 return RandomizedSelect(a,i+1,r,k-j); void SelectionSort(int a) int min; for (int i = 0; i < 2000 - 1;