java算法：数组

java算法：数组

数组是最基本的数据结构。在java和大多数编程语言中都被定义为简单类型。数组的使用是开发有效算法的基础。

数组是相同类型数据的固定集合，它是连续存储的，通过下标来访问数组元素。由于它是与计算机的内存系统直接通讯，可以看成是最基本的数据结构。

例一：埃拉托色尼筛，打印出小于给定N的所有素数。

Java代码

publicclassPrimes{ publicstaticvoidmain(String[]args){ intN=Integer.parseInt(args[0]); boolean[]a=newboolean[N]; for(inti=2;i<N;i++){ a[i]=true; } for(inti=2;i<N;i++){ if(a[i]!=false){ for(intj=i;j*i<N;j++){ a[i*j]=false; } } } for(inti=2;i<N;i++){ if(i>N-100){ if(a[i]){ System.out.println(""+i); } } } } }

public class Primes {public static void main(String[] args) {int N = Integer.parseInt(args[0]);boolean [] a = new boolean[N];for(int i = 2; i < N ; i++){a[i] = true;}for(int i = 2; i < N ; i++){if(a[i] != false){for(int j = i; j * i < N; j++){a[i * j] = false;}}}for(int i = 2; i < N ; i++){if(i > N - 100){if(a [i]){System.out.println(" " + i);}}}}}

上述代码，计算一个布尔型的数组，如果i是素数，a[i]为true，否则，a[i]为false。首先，把数组中的所有元素置为true，然后把对应下标为非素数（是已知素数的倍数）的数组元素设为false。如果在所有较小素数的倍数都被设为false值后，a[i]的值仍为true，那么它肯定是一个素数。

对于其他对象而言，对数组的引用很有价值，因为它们可以把数组作为高级对象来有效地使用。

例二：健壮的数组分配

如果程序使用者敲入一个巨大的数作为命令行参数，它可能产生OutOfMemoryError异常错误，因此：

Java代码

boolean[]a; try{ a=newboolean[N]; }catch(OutOfMemoryExceptione){ System.out.println("Outofmemory."); }

boolean [] a;try{a = new boolean[N];}catch(OutOfMemoryException e){System.out.println("Out of memory.");}

数组不仅准确地反映在大多数计算机上访问内存数据的基本方法，而且在应用中获得了广泛的应用，如，数组直接对应着向量，是描述具有下标的对象列表的数学术语。

例三：掷硬币模拟

Java代码

publicclassCoinFlip{ staticbooleanheads(){ returnMath.random()<0.5; } publicstaticvoidmain(String[]args){ inti,j,cnt=0; intN=Integer.parseInt(args[0]); intM=Integer.parseInt(args[1]); int[]f=newint[N+1]; for(j=0;j<=N;j++){ f[j]=0; } for(i=0;i<M;i++,f[cnt]++){ for(cnt=0,j=0;j<=N;j++){ if(heads()){ cnt++; } } } for(j=0;j<=N;j++){ if(f[j]==0){ System.out.print("."); } for(i=0;i<f[j];i+=10){ System.out.print("*"); } System.out.println(""); } } }

public class CoinFlip {static boolean heads(){return Math.random() < 0.5;}public static void main(String[] args) {int i,j,cnt = 0;int N = Integer.parseInt(args[0]);int M = Integer.parseInt(args[1]);int  [] f = new int[N + 1];for (j = 0; j <= N; j++) {f[j]=0;}for (i = 0; i < M; i++, f[cnt]++) {for(cnt = 0, j = 0; j <= N; j++){if(heads()){cnt++ ;}}}for(j = 0; j <= N; j++){if(f[j] == 0){System.out.print(".");}for(i = 0; i < f[j]; i+= 10){System.out.print("*");}System.out.println("");}}}

从某种意义上说，当我们使用一个计算过的值来访问大小为N的数组时，只用一个操作就可以把N种可能性都考虑进去，效率上有了很大的提高。

例四：最近点计算

Java代码

publicclassClosePoints{ publicstaticvoidmain(String[]args){ intcnt=0; intN=Integer.parseInt(args[0]); doubled=Double.parseDouble(args[1]); Point[]a=newPoint[N]; for(inti=0;i<N;i++){ a[i]=newPoint(); } for(inti=0;i<N;i++){ for(intj=i+1;j<N;j++){ if(a[i].distance(a[j])<d){ cnt++; } } } System.out.println(cnt+"pairscloserthan"+d); } }

public class ClosePoints {public static void main(String[] args) { int cnt = 0; int N = Integer.parseInt(args[0]); double d = Double.parseDouble(args[1]); Point [] a = new Point[N]; for(int i = 0; i < N; i++){ a[i] = new Point(); } for(int i = 0; i < N; i++){ for(int j = i + 1; j < N; j++){ if(a[i].distance(a[j]) < d){ cnt++; } } } System.out.println(cnt + " pairs closer than " + d);}}

作为一个原型二次算法，它检查了N个数据项集合的所有数据对时，因此所花的时间与N平方成正比。

心有多大，舞台就有多大。