实验2查找第K小元素的问题

1、 实验2 查找第K小元素的问题一 源代码如下：下列程序中1.void SelSort(int * a, int low, int high)为对一个数组进行简单选择排序的函数；2.int select(int * A, int low, int high, int k,int times,int &t)是查找第K小元素的函数，其中查找的结果存于t，参数times为估计执行比较次数的目的而设置并返回；3.为方便进行简单的分析，为方便演示，设阈值为6。#include <iostream> #include <cmath> using namespace std;

2、void SelSort(int * a, int low, int high) int t; for(int i=low;i<high;i+) for(int j=i+1;j<=high;j+) if(ai>aj) t=ai;ai=aj;aj=t; int select(int * A, int low, int high, int k,int times,int &t) int p = high-low+1; if (p < 6) SelSort(A, low, high);times=p*(p-1)/2; /简单选择排序的比较次数 t=Ak-1;retur

3、n times; int q = p / 5; int * M = new int q; for (int i = 0; i < q; i+) SelSort(A, i*5, i*5+4); Mi = Ai*5+2; times+=q*10;/每5个元素一组排序估计10次，共有q组； int mm; times=times+select(M, 0, q-1, int(ceil(q/2.0),times,mm); /求中项 int * A1 = new int p; int * A2 = new int p; int * A3 = new int p; int count1 = 0, co

4、unt2 = 0, count3 = 0; for (int i = low; i <= high; i+) if (Ai < mm) A1count1+ = Ai; else if (Ai = mm) A2count2+ = Ai; else A3count3+ = Ai; times+=p;/分3组则有p次，这里p=n次； if (count1 >= k) times=times+select(A1, 0, count1-1, k,times,t); else if (count1+count2 >= k) t = mm;times+=1; / else if (c

5、ount1+count2 < k) times=times+ select(A3, 0, count3-1, k-count1-count2,times,t); / delete M; delete A1; delete A2; delete A3; return times; int main(void) int t;int times=0; int g = 60, 22223, 111700, 1110, 5766, 9995, 557, 441, 24448, 8837; cout << "数据如下：n" for (int i = 0; i <

6、10; i+) cout << gi << " " cout << endl; for (int i = 0; i < 10; i+) times=0; cout << "的第"<<i+1<<"小元素是："times= select(g, 0, 9, i+1,times,t);cout<<t<<" 其执行比较估计次数为： "<<times<<endl; int e = 18, 333, 7,

7、 1, 537, 9, 35, 101, 25, 87; cout << "数据如下：n" for (int i = 0; i <10; i+) cout << ei << " " cout << endl; for (int i = 0; i < 10; i+) times=0; cout << "的第"<<i+1<<"小元素是："times= select(e, 0, 9, i+1,times,t);cout<

8、<t<<" 其执行比较估计次数为： "<<times<<endl; int f = 8, 33, 75, 1, 537, 9999, 305, 1, 5, 87; cout << "数据如下：n" for (int i = 0; i <10; i+) cout << fi << " " cout << endl; for (int i = 0; i < 10; i+) times=0; cout << "的第&q

9、uot;<<i+1<<"小元素是："times= select(f, 0, 9, i+1,times,t);cout<<t<<" 其执行比较估计次数为： "<<times<<endl; int c = 8, 33, 17, 51, 57, 49, 35, 11, 25, 37, 14, 3, 2, 13, 52, 12, 6, 29, 32, 54, 5, 16, 22, 23, 7; cout << "数据如下：n" for (int i = 0;

10、i <25; i+) cout << ci << " " cout << endl; for (int i = 0; i < 25; i+) times=0; cout << "的第"<<i+1<<"小元素是："times= select(c, 0, 24, i+1,times,t);cout<<t<<" 其执行比较估计次数为："<<times<<endl; int d = 18, 3

11、33, 7, 1, 537, 9, 35, 101, 25, 87, 94, 23, 27, 19, 62, 11, 8, 29, 32, 504, 5, 176, 212, 93, 47; cout << "数据如下：n" for (int i = 0; i <25; i+) cout << di << " " cout << endl; for (int i = 0; i < 25; i+) times=0; cout << "的第"<<i+1&l

12、t;<"小元素是："times= select(d, 0, 24, i+1,times,t);cout<<t<<" 其执行比较估计次数为："<<times<<endl; int a = 8,33,17,51,57,49,35,11,25,37,14,3,2,13,52,12,6,29,32,54,5,16,22,23,7,62,53,4,8,781,12,49,51,52,3,54,55,56,61,2,67,78,90,122,133,10,1024,1025,1026,1027,2000,2700

13、; cout << "数据如下：n" for (int i = 0; i < 52; i+) cout << ai << " " cout << endl; for (int i = 0; i < 52; i+) times=0; cout << "的第"<<i+1<<"小元素是："times= select(a, 0, 51, i+1,times,t);cout<<t<<" 其执行比较

14、估计次数为："<<times<<endl; int b = 1,21,3,4,5,6,7,8,9,10,14,13,2,13,52,12,6,29,32,54,35,16,22,23,67,62,53,4,8,71,12,9,51,2,3,154,545,66,61,2,670,78,90,1202,133,10,1024,105,106,102,200,20;cout << "数据如下：n" for (int i = 0; i < 52; i+) cout << bi << " &quo

15、t; cout << endl; for (int i = 0; i < 52; i+) times=0; cout << "的第"<<i+1<<"小元素是："times= select(b, 0, 51, i+1,times,t);cout<<t<<" 其执行比较估计次数为："<<times<<endl; return 0; 二相关分析明确程序思路：如果数组A中元素的个数小于一个阈值，那么采用直接的方法寻找第k小元素。否则，将n个元

16、素划分成n/5组，每组5个元素，如果n不是5的倍数，则排除剩余的元素。 对每组元素排序，并取出它们的中项(即第3个元素)。 n/5个中项的中项，我们记为mm。依据mm将数组A划分为三个子数组：A1a|a<mm、A2a|a=mm、A3=a|a>mm。判断第k小元素可能在哪一个子数组中出现：如果在A2 中出现，则已经找到；否在，在A1或A3上进行递归。1. 研究同一个输入A1n时在k=1,2,n时的复杂度，保存数据，并绘图(横坐标k，纵坐标T(n)，分析T(n)随着k的变化规律。有以下三个数组，n=10，数据不尽相同：g10 = 60, 22223, 111700, 1110, 576

17、6, 9995, 557, 441, 24448, 8837；e10 = 18, 333, 7, 1, 537, 9, 35, 101, 25, 87；f10 = 8, 33, 75, 1, 537, 9999, 305, 1, 5, 87；当我们对其分别求第K小元素时，其结果和相应的执行比较次数T（n）如下图所示：绘图(横坐标k，纵坐标T(n)，如下研究同一个输入A1n时在k=1,2,n时的复杂度，对图中可见求：A.如g10 = 60, 22223, 111700, 1110, 5766, 9995, 557, 441, 24448, 8837中第5小元素即5766时，复杂度最小，这是由于“

18、中项的中项”即为5766，不再需要递归调用。对于数组：e10 = 18, 333, 7, 1, 537, 9, 35, 101, 25, 87；f10 = 8, 33, 75, 1, 537, 9999, 305, 1, 5, 87同理。B.通过曲线可以更加深刻地理解，采用分而治之的思想求第K小元素的过程是以中间元素为基准抛弃部分元素，不断减小问题规模。重新产生2组输入A1n ，重复工作，对比：n不变但输入的数据变化时，图像变化规律无变化。如图中三个数组g10,e10,f10，图像走势一致。甚至g10和f10的比较次数是完全吻合的。2. n增加，重复工作，分析： c = 8, 33, 17, 51, 57, 49, 35, 11, 25, 37, 14, 3, 2, 13, 52, 12, 6, 29, 32, 54, 5, 16, 22, 23, 7;d = 18, 333, 7, 1, 537, 9, 35, 101, 25, 87, 94, 23, 27, 19, 62, 11, 8, 29, 32, 504, 5, 176, 212, 93, 47;当我们对其分别求第K小元素时，其结果和相应的执行比较次数