首页 > 代码库 > 算法实验--线性时间

算法实验--线性时间

一、实验目的:

熟悉掌握分治算法设计技术。

二、实验要求:

1、按教材所授内容要求,完成“线性时间选择问题”算法。得到一个完整正确的程序。

2、问题规模:不少于2000

3、输出最终结果。

三、实验设备:

PC机一台

四、问题描述:

运用分治法的原理,对随机生成的数进行查找,找出其中第K大小的数,找出之后输出所找到的数。

五、算法分析:

 

 

 

 

 

 

 

 

                                       

 

                                      Yes

                            No

 

 

 

 

 

 

 

 

 

1.用到的函数:

  void swap(int& x,int& y);在进行查找时候用于基准元素两边的元素想交换。

  void getRand(int *a);随机生成2000-5000-5000的整数。

  int partition(int a[],int left,int right);

  int line_select(int a[],int p,int r,int k);

2.算法分析:

利用随机分治的思想,平均时间复杂度为On),最坏时间复杂度为On2

分治算法思路:模仿快速排序对输入数组A进行二分划分,使子数组A1的元素  <=A2中的元素,分点j由随机数产生,k<j,kA1的第k小元k>j, kA2的第k-j小元.线性时间选择 由快速排序分点为第一个点计算。

3.进度走向

main=getRand()=》输入I=>判断I=0=》否=line_select()=》退出

   是=》退出

 

六、代码:

#include <stdio.h>

#include<stdlib.h>

#include<time.h>

#define P 0

#define R 2000

#define N 2000

#define M 10000

void swap(int& x,int& y);

void getRand(int *a);

int partition(int a[],int left,int right);

int line_select(int a[],int p,int r,int k);

 

void main()

{ printf("-----------------");

int a[N];

int k;

getRand(a);

printf("2000个随机数(-5000 ~ 5000)已生成-----------------\n示例(前十个)\n");

for(int l=0;l<10;l++)

printf("%d ",a[l]);

printf("\n");

while(1){

printf("请输入K得到第K小的数(0退出): ");

scanf("%d",&k);

if(k==0){break;}

int i=line_select(a,P,R,k);

printf("%d小的数是: %d\n\n",k,i);

}

}

//实现整数xy的交换

void swap(int& x,int& y)

{

    int t;

    t=x;

    x=y;

    y=t;

}

//生成-5000-5000的随机整数

void getRand(int *a)

{

srand( (unsigned)time( NULL ) );  //初始化随机数

for(int i=0;i<N;i++)  

a[i]=5000-(int)rand()%M; 

}

}

//查询第k小的元素

int line_select(int a[],int p,int r,int k)

{

       if (p==r) return a[p];

       int i=partition(a,p,r);

       int j=i-p+1;

       if (k==j) return a[i];

       else if (k<j)

              return line_select(a,p,i-1,k);

       else

              return line_select(a,i+1,r,k-j);

}

int partition(int a[],int p,int r)

{

       int i=p;

       int j=r+1;

       int x=a[i];

       while (true)//循环查询,输入0是退出循环

       {

   while (a[++i]<x&&i<=r);

   while (a[--j]>x);

   if (i>j) break;

   swap(a[i],a[j]);

       }

       a[p]=a[j];

       a[j]=x;

       return j;

}

七、调试及运行:

1.输出第1400800120016002000小的数(以500为间隔)如图:

 

 

2.输出第1500100015002000小的数(以500为间隔)如图:

 

 

2.输出第1600120018002000小的数(以600为间隔)如图:

 

 

八、实验总结

通过对分治法实现限行时间选择的复习,对快速排序的方法和基本思想有了一定的更深入了解,以一个确定的基准元素a[p]对子数组a[p:r]进行划分,可以很快速的对一个数组排序,这次实验不仅使我复习了快速排序的精髓,也练习了曾经认为不可能线性时间找到数组中第i小的数的算法。

算法实验--线性时间