实验一 分治与递归—用分治法实现元素选择 java算法

  提高题二:用分治法实现元素选择

一、实验要求与目的

1、了解分治法的基本思想,掌握递归程序编写方法;

2、使用分治法编程,求解线形序列中第k小元素。

二、实验内容

1、  给定线形序列集中n个元素和一个整数k1kn,输出这n个元素中第k小元素的值及其位置。

2、  简述该算法的原理、步骤。对该算法与直接排序查找进行比较。

3、  编写并调试程序。

测试要求:元素个数不少于100;分三种情况:k=1k=nk=中位数。

三、源代码

importjava.util.*;

import java.io.*;

 

 

public class SF_XianxingXuanze

{

       public static void main(String[] args)

       {

              Scanner read=new Scanner(System.in);

              Random r=new Random();//产生小于100 的数据

              for (; ; )

              {

                     int a[]=null,b[]=null,k=0,i=0,n=0,d=0,s=0;

                     System.out.println("请输入元素个数:");

                     n=read.nextInt();

                     a=new int[n];

                     b=new int[n];

                     for (i=0;i<n ;i++ )

                     {

                            a[i]=r.nextInt(100);

                     }

                     for (i=0;i<n ;i++ )

                     {

                            System.out.print(a[i]+"\t");

                            if ((i+1)%10==0)

                            {

                                   System.out.println();

                            }

 

                     }

                     System.out.println();

                     for (i=0,d=0;d<n ;d++ )//将数组a的值赋给数组b

                     {

                            b[d]=a[i];

                            i++;

                     }

                     quickSort(a,0,i-1);//调用快速排序进行排序

                     System.out.println("排序后");

                     for (i=0;i<n ;i++ )//输出排好序的数组a,每行10个数据

                     {

                            System.out.print(a[i]+"\t");

                            if ((i+1)%10==0)

                            {

                                   System.out.println();

                            }

                     }

 

 

 

                     System.out.println();

                     System.out.println("请输入第k小元素:");

                     k=read.nextInt();

                     for(d=0;d<n;d++) //从数组b中找出第k小的数在原数组中的位置

                     {

                            if(b[d]==a[k-1])          //从数组b中找出第k小的数在原数组中的位置

                            s=d+1;

                     }

                     System.out.println("******排序后的位置******");

                     System.out.println(""+k+"小元素为:"+a[k-1]);

                     System.out.println("******排序前的位置******");

                     System.out.println(""+k+"小元素位置:"+"\t"+s);

                    

              }

             

       }

       public static void quickSort(int a[],intp,int r){

              int q=0;

              if (p<r)

              {

                     q=partition(a,p,r);

                     quickSort(a,p,q-1);

                     quickSort(a,q+1,r);

              }

       }

 

       public static int partition(int a[],intp,int r){

              int z=p,x=r+1;

              int y=a[p];

              int t;

              while (true)

              {

                     while(a[++z]<y&&z<r);//空循环,不符合条件时向下执行

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

                     if(z>=x)break;

                     t=a[z];

                     a[z]=a[x];

                     a[x]=t;

              }

              a[p]=a[x];

实验一 分治与递归—用分治法实现元素选择 java算法

              a[x]=y;

              return x;

       }

}

 

结果:

 本文转自 梦朝思夕 51CTO博客,原文链接:http://blog.51cto.com/qiangmzsx/818749




上一篇:5.记录类型使用合集


下一篇:EBS Form 级联使用