java高手请进——数组越界问题

Question

package CompareSort;
class CompareSort
{
public static void main(String args[])
{
for(int i=0;i<Sort.Array.length;i++)
Sort.Array[i]=(int)(Math.random()*100+0.5);
BottomUpSort bus=new BottomUpSort();
bus.bottomUp();
bus.output();
}
}
abstract class Sort
{
static int[]Array=new int[20];
abstract void output();
}
class BottomUpSort extends Sort
{
void merge(int p,int q,int r)
{
int[]arraytemp=new int[r+1];
int s,t,k;
s=q;
t=q+1;
k=p;
while((s<=q)&&(t<=r))
{
if(Sort.Array[s]<=Sort.Array[t])
{
  arraytemp[k]=Sort.Array[s];
  s++;
}
else
{
arraytemp[k]=Sort.Array[t];
t++;
}
k++;
}
if(s==q+1)
{
for(int m=k;m<=r;m++)
{
  arraytemp[m]=Sort.Array[t];
  t++;
}
}
else
{
for(int m=k;m<=r;m++)
{
arraytemp[m]=Sort.Array[s];
s++;
}
}
for(int m=p;m<=r;m++)
Sort.Array[m]=arraytemp[m];
}
void bottomUp()
{
int t=1;
int s,i;
while(t<Sort.Array.length)
{
s=t;
t=2*s;
i=0;
while(i+t<=Sort.Array.length)
{
merge(i,i+s-1,i+t-1);
i=i+t-1;
}
if(i+s<Sort.Array.length)merge(i,i+s-1,Sort.Array.length-1);
}
}
public void output()
{
for(int i=0;i<Sort.Array.length;i++)
System.out.println(Sort.Array[i]);
}
}

Answer 1

排版后的程序如下：
该程序的思路是，先合并2个有序，再合并2^2个有序数组，最后合并成一个按非降次序排序的数组。
package CompareSort; 
class CompareSort 
{ 
     public static void main(String args[]) 
     { 
          for(int i=0;i <Sort.Array.length;i++) 
          Sort.Array[i]=(int)(Math.random()*100+0.5); 
          BottomUpSort bus=new BottomUpSort(); 
          bus.bottomUp(); 
          bus.output(); 
     } 
} 
abstract class Sort 
{ 
         static int[]Array=new int[20]; 
         abstract void output(); 
} 
class BottomUpSort extends Sort 
{ 
         void merge(int p,int q,int r) 
         { 
            int[]arraytemp=new int[r+1]; 
            int s,t,k; 
            s=q; 
            t=q+1; 
            k=p; 
         while((s <=q)&&(t <=r)) 
         { 
            if(Sort.Array[s] <=Sort.Array[t]) 
            { 
               arraytemp[k]=Sort.Array[s]; 
               s++; 
            } 
            else 
           { 
              arraytemp[k]=Sort.Array[t]; 
              t++; 
           } 
           k++; 
        } 
          if(s==q+1) 
          { 
                 for(int m=k;m <=r;m++) 
                 { 
                     arraytemp[m]=Sort.Array[t]; 
                     t++; 
                 } 
          } 
          else 
          { 
                for(int m=k;m <=r;m++) 
                { 
                    arraytemp[m]=Sort.Array[s]; 
                    s++; 
                } 
          } 
          for(int m=p;m <=r;m++) 
          Sort.Array[m]=arraytemp[m]; 
        } 
void bottomUp() 
{ 
   int t=1; 
   int s,i; 
 while(t <Sort.Array.length) 
 { 
  s=t; 
  t=2*s; 
  i=0; 
  while(i+t <=Sort.Array.length) 
  { 
     merge(i,i+s-1,i+t-1); 
     i=i+t-1; 
  } 
  if(i+s <Sort.Array.length)merge(i,i+s-1,Sort.Array.length-1); 
 } 
} 
 public void output() 
 { 
   for(int i=0;i <Sort.Array.length;i++) 
   System.out.println(Sort.Array[i]); 
 } 
}

Answer 2

排版后的程序如下： 
该程序的思路是，先合并2个有序，再合并2^2个有序数组，最后合并成一个按非降次序排序的数组。 
package CompareSort; 
class CompareSort 
{ 
    public static void main(String args[]) 
    { 
          for(int i=0;i <Sort.Array.length;i++) 
          Sort.Array[i]=(int)(Math.random()*100+0.5); 
          BottomUpSort bus=new BottomUpSort(); 
          bus.bottomUp(); 
          bus.output(); 
    } 
} 
abstract class Sort 
{ 
        static int[]Array=new int[20]; 
        abstract void output(); 
} 
class BottomUpSort extends Sort 
{ 
        void merge(int p,int q,int r) 
        { 
            int[]arraytemp=new int[r+1]; 
            int s,t,k; 
            s=q; 
            t=q+1; 
            k=p; 
        while((s <=q)&&(t <=r)) 
        { 
            if(Sort.Array[s] <=Sort.Array[t]) 
            { 
              arraytemp[k]=Sort.Array[s]; 
              s++; 
            } 
            else 
          { 
              arraytemp[k]=Sort.Array[t]; 
              t++; 
          } 
          k++; 
        } 
          if(s==q+1) 
          { 
                for(int m=k;m <=r;m++) 
                { 
                    arraytemp[m]=Sort.Array[t]; 
                    t++; 
                } 
          } 
          else 
          { 
                for(int m=k;m <=r;m++) 
                { 
                    arraytemp[m]=Sort.Array[s]; 
                    s++; 
                } 
          } 
          for(int m=p;m <=r;m++) 
          Sort.Array[m]=arraytemp[m]; 
        } 
void bottomUp() 
{ 
  int t=1; 
  int s,i; 
while(t <Sort.Array.length) 
{ 
  s=t; 
  t=2*s; 
  i=0; 
  while(i+t <=Sort.Array.length) 
  { 
    merge(i,i+s-1,i+t-1); 
    i=i+t-1; 
  } 
  if(i+s <Sort.Array.length) {
     merge(i,i+s-1,Sort.Array.length-1); 
  }
} 
} 
public void output() 
{ 
  for(int i=0;i <Sort.Array.length;i++) 
  System.out.println(Sort.Array[i]); 
} 
}

Answer 3

整了一晚上，终于搞出来了......和大家分享一下～～package CompareSort;
class CompareSort
{
public static void main(String args[])
{
long startTime,endTime;
for(int i=0;i<Sort.Array1.length;i++)
{
  Sort.Array1[i]=(int)(Math.random()*100000+0.5);
  Sort.Array2[i]=Sort.Array1[i];
}
System.out.println("随机产生的数组如下：");
for(int i=0;i<Sort.Array1.length;i++)
System.out.print(Sort.Array1[i]+"\t");
System.out.println();
BottomUpSort bus=new BottomUpSort();
startTime=System.nanoTime();
bus.bottomUp();
endTime=System.nanoTime();
Sort.costTime=endTime-startTime;
bus.output();
System.out.println();
QuickSort qs=new QuickSort();
startTime=System.nanoTime();
qs.quick(Sort.Array2,0,Sort.Array2.length-1);
endTime=System.nanoTime();
Sort.costTime=endTime-startTime;
qs.output();
}
}
abstract class Sort
{
static long costTime;
static int[]Array1=new int[20];
static int[]Array2=new int[20];
abstract void output();
}
class BottomUpSort extends Sort
{
void merge(int p,int q,int r)
{
int[]arraytemp=new int[r+1];
int s,t,k;
s=p;
t=q+1;
k=p;
while((s<=q)&&(t<=r))
{
if(Sort.Array1[s]<=Sort.Array1[t])
{
  arraytemp[k]=Sort.Array1[s];
  s++;
}
else
{
arraytemp[k]=Sort.Array1[t];
t++;
}
k++;
}
if(s==q+1)
{
for(int m=k;m<=r;m++)
{
  arraytemp[m]=Sort.Array1[t];
  t++;
}
}
else
{
for(int m=k;m<=r;m++)
{
arraytemp[m]=Sort.Array1[s];
s++;
}
}
for(int m=p;m<=r;m++)
Sort.Array1[m]=arraytemp[m];
}
void bottomUp()
{
int t=1;
int s,i;
while(t<Sort.Array1.length-1)
{
s=t;
t=2*s;
i=0;
while(i+t<=Sort.Array1.length-1)
{
merge(i,i+s-1,i+t-1);
i=i+t;
}
if(i+s<Sort.Array1.length-1)merge(i,i+s-1,Sort.Array1.length-1);
}
}
public void output()
{
System.out.println("自底向上合并排序：");
for(int i=0;i<Sort.Array1.length;i++)
System.out.print(Sort.Array1[i]+"\t");
System.out.println("\n执行自底向上合并排序所需的时间为："+Sort.costTime+" ns");
}
}
class QuickSort
{
int w;
void split(int[]a,int low,int high)
{
int i=low;
int x=a[low];
for(int j=low+1;j<=high;j++)
{
if(a[j]<x)
{
i++;
if(i!=j)
{
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
int temp;
temp=a[low];
a[low]=a[i];
a[i]=temp;
w=i;
}
void quick(int []a,int low,int high)
{
if(low<high)
{
split(a,low,high);
quick(a,low,w-1);
quick(a,w+1,high);
}
}
public void output()
{
System.out.println("快速排序：");
for(int i=0;i<Sort.Array2.length;i++)
System.out.print(Sort.Array2[i]+"\t");
System.out.println("\n执行快速排序所需的时间为："+Sort.costTime+" ns");
}
}