import java.util.*;
public class Test{
  public int[] insertSort(int[] array){ //對整型數組a進行插入排序，在a[0]處設置監視哨
  	//先將序列中的第一個元素看成是一個有序的子序列
  	int j;
  	int[] a=new int[array.length];
  	copy(array,a);
  	for(int i=2;i<a.length;i++){
  		if(a[i]<a[i-1]){//需要將a[i]插入有序子表中
  		  a[0]=a[i];    //復制為哨兵
  		  a[i]=a[i-1];
  		  for( j=i-2;a[0]<a[j];j--)
  		     a[j+1]=a[j];    //記錄后移
  		  a[j+1]=a[0];       //插入到正確位置
  		}
  		
  	}
  	return a;
    
  }
  
  public int[] bubbleSort(int[] array){  //冒泡排序
  	int[] a=new int[array.length];
  	int temp,j;
  	copy(array,a);
  	for(j=a.length-1;j>1;j--){  	
  	  for(int i=1;i<a.length-1;i++){
  		if(a[i]>a[i+1]){
  			temp=a[i];
  			a[i]=a[i+1];
  			a[i+1]=temp;
  	    }
  	  }
  	}
  	return a;  
  } 
 
  public void copy(int[] array,int[] a){
    for(int i=0;i<array.length;i++)
 	   a[i]=array[i];
  }
     
    	
  public static void main(String args[]){
    Test t=new Test();
    Random r=new Random();
    int size=1000;//數組個數      
    int randomArray[]=new int[size];   //定義一個隨機數組
    int sortedArray[]=new int[size];     //定義一個排序數組
    
    //生成一個隨機數組
    for(int i=1;i<size;i++)
      randomArray[i]=r.nextInt()%1000;   //再隨機數組中存入10個隨機數
    //打印隨機數組
    System.out.println("The random array is:");    
    for(int i=1;i<size;i++)
       System.out.print(randomArray[i]+" ");
    System.out.println();
    
    //用插入排序法排序
    sortedArray=t.insertSort(randomArray);
    System.out.println("Use inserSort,the sorted array is:");       
    for(int i=1;i<size;i++)
       System.out.print(sortedArray[i]+" ");
    System.out.println(); 
    
    
    //用插入排序法排序
    sortedArray=t.bubbleSort(randomArray);
    System.out.println("Use bubbleSort,the sorted array is:");       
    for(int i=1;i<size;i++)
       System.out.print(sortedArray[i]+" ");
    System.out.println(); 
  }
}