分治法線性時(shí)間選擇

1、計(jì)算機(jī)算法設(shè)計(jì)與分析實(shí) 驗(yàn) 報(bào) 告實(shí)驗(yàn)名稱：線性時(shí)間選擇問題實(shí)驗(yàn)地點(diǎn)：所使用的開發(fā)工具及環(huán)境：1、 實(shí)驗(yàn)?zāi)康模菏煜ふ莆辗种嗡惴ㄔO(shè)計(jì)技術(shù)二、實(shí)驗(yàn)內(nèi)容：1、按教材所授內(nèi)容要求，完成“線性時(shí)間選擇問題”算法。得到一個(gè)完整正確的程序。2、問題規(guī)模：不少于20003、輸出最終結(jié)果。3、 基本思想、原理和算法描述： 基本思想：將n個(gè)輸入元素劃分成 n/5個(gè)組，每組有5個(gè)元素，除最后一組可能不是5個(gè)元素之外用任意一種算法，將每組的元素排好序，并取出每組的中位數(shù)，共 n/5個(gè)。調(diào)用Select找出這 n/5個(gè)元素的中位數(shù)，如果 n/5是偶數(shù)就找兩個(gè)中位數(shù)中較大的一個(gè)。在這里我用的排序的方法是快速排序。算法描述

2、：template <class Type>Type Select(Type a,int p,int r,int k)int i;if(r-p<75)Qsort(a,p,r);return ap+k-1;/(r-p-4)/5相當(dāng)于n-5for(i=0; i<=(r-p-4)/5; i+)/將元素每5個(gè)分成一組，分別排序，并將該組中位數(shù)與ap+i交換位置/使所有中位數(shù)都排列在數(shù)組最左側(cè)，以便進(jìn)一步查找中位數(shù)的中位數(shù)Qsort(a,p+5*i,p+5*i+4);Swap(ap+5*i+2,ap+i);/找中位數(shù)的中位數(shù)Type x = Select(a,p,p+(r-p-4

3、)/5,(r-p-4)/10); i = Partition(a,p,r,x);int j = i-p+1;if(k<=j)return Select(a,p,i,k);elsereturn Select(a,i+1,r,k-j);4、 源程序清單：#include<stdio.h>#include<stdlib.h>#include<time.h>#include<windows.h>#include<iostream.h>template <class Type>void Swap(Type &x,Typ

4、e &y);inline int Random(int x, int y);template <class Type>void Qsort(Type a ,int p,int r);template <class Type>int Partition(Type a,int p,int r,Type x);template <class Type>Type Select(Type a,int p,int r,int k);void main()int a2000;srand(unsigned)time(NULL);for(int i=0; i<2

5、000; i+)ai = Random(0,2000);cout<<"a"<<i<<":"<<ai<<" "cout<<endl;cout<<"第800小元素是"<<Select(a,0,1999,800)<<endl;/重新排序，對比結(jié)果Qsort(a,0,1999);for( i=0; i<2000; i+)cout<<"a"<<i<<&quo

6、t;:"<<ai<<" "cout<<endl;template <class Type>void Swap(Type &x,Type &y)Type temp = x;x = y;y = temp;inline int Random(int x, int y) int ran_num = rand() % (y - x) + x; return ran_num;template <class Type>void Qsort(Type a ,int p,int r)if(p<r)Ty

7、pe x;int q=Partition(a,p,r,x);Qsort(a,p,q-1);Qsort(a,q+1,r);template <class Type>int Partition(Type a,int p,int r,Type x)int i = p;int j = r + 1; 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>Type Se

8、lect(Type a,int p,int r,int k)int i;if(r-p<75)Qsort(a,p,r);return ap+k-1;/(r-p-4)/5相當(dāng)于n-5for(i=0; i<=(r-p-4)/5; i+)/將元素每5個(gè)分成一組，分別排序，并將該組中位數(shù)與ap+i交換位置/使所有中位數(shù)都排列在數(shù)組最左側(cè)，以便進(jìn)一步查找中位數(shù)的中位數(shù)Qsort(a,p+5*i,p+5*i+4);Swap(ap+5*i+2,ap+i);/找中位數(shù)的中位數(shù)Type x = Select(a,p,p+(r-p-4)/5,(r-p-4)/10); i = Partition(a,p,r,x);int j = i-p+1;if(k<=j)return Select(a,p,i,k);elsereturn Select(a,i+1,r,k-j);5、 程序運(yùn)行結(jié)果（包括上機(jī)調(diào)試的情況、調(diào)試所遇到的問題是如何解決的，并對調(diào)試過程中的問題進(jìn)行分析，對執(zhí)行結(jié)果進(jìn)行分析。）： 在本次實(shí)驗(yàn)中遇到了一些問題。在寫select方法調(diào)用的時(shí)候調(diào)用不了，然后產(chǎn)