ordarray.java

数据结构 包括数组(Array包) 和二叉树(Tree) 链表(Linelist包) 等等

package Array;

//=================================================================
public class OrdArray {
	private Person[] array;
	private int index;
	
	/**
	 * @param max
	 */
	//==================================================================
	public OrdArray(int max){
		array=new Person[max];
		index=0;
	}
	
	//=================================================================
	public int getSize(){
		return index;
	}
	
	public Person getUnit(int ind){
		return array[ind];
	}
	
	public void insertUnit(Person in){
		 array[index]=in;
		 index++;
	}
	
//=======================================================================	
	
	public int findArray(int Key){//使用二分查找法查找元属，
		                          //条件为数组必须为有序数组
		int lowerBound=0;
		int uperBound=index-1;
		int cutin;
		int result=0;
		boolean flag=true;
		//int findedCount=0;
		while(flag){
			cutin=(uperBound+lowerBound)/2;
			
			//测试用========================
		    // findedCount++;
		    // System.out.println("第"+findedCount+"次查找 cuntin为"
		    		//+cutin+"范围是 :"+uperBound+"到"+
		    		//lowerBound);//查找次数计算
		     //测试用===========================
		     
			if(array[cutin]==null){
				result=-1;
		     break;
		     }
			if(array[cutin].getSn()==Key){
				 flag=false;
				result=cutin;   //found
			    
			}
			else if(lowerBound>uperBound){
				flag=false;
				result=array.length+1;   //no found return the max for arr
			}
			else{
				 if(array[cutin].getSn()<Key)
					 lowerBound=cutin+1;
				 else
					 uperBound=cutin-1;
				 
			}//end else divide rang
				
		} //end while
		
			
		return result;
		
	}//end find
//======================================================================
	public int find(int key){
		int result=array.length+1;
		for(int i=0;i<index;i++){
			 if(array[i].getSn()==key)
				 result=i;
		}
		return result;
		
	}
//======================================================================
	public void insertArrayNomal(int sn,String firstName,String lastName){
		    array[index]=new Person(sn,firstName,lastName);
		    index++;
	}
//====================================================================
	
	
    public void insertArrayInOrder(int sn,String firstName,String lastName){
    	 if(this.findArray(sn)==-1 )
    	       array[index]=new Person(sn,firstName,lastName);
    	 else{
    		 int i,j;
    		  for( i=0;i<index;i++){//通过这个循环找刚好比sn小的数的下标
    			  if(array[i].getSn()>sn)
    				  break;
    		  }
    		  for(j=index;j>i;j--)
    			  //把元素向数组尾部移动
    			  array[j]=array[j-1];
    			     //这里有两个作用 
    			     //1:移动比sn大的元素，给插入sn留下空间 这个情况下循环结束j=i  
    			     // 2: 如果 sn比数组里的所有都大, 插入的位置
    			     //就是j=index 也就是 数组尾部
    		      array[j]=new Person(sn,firstName,lastName);
    	 }
    		 
    	 index++;
    	
    }
//===================================================================
    
    
     
     public boolean deleteArray(int key){
    	 int searchtag=this.findArray(key);
    	 if(searchtag==array.length+1)
    		 searchtag=this.find(key);
    	 
    	   System.out.println(searchtag);
    	   
    	   if(this.findArray(key)==array.length+1 && 
    		  this.find(key)==array.length+1){
    		   return false;
    	   }
    	   else{
    		   for(int i=searchtag;i<index;i++)
    			   //找到要删除值的下标=i,从元素i开始把东西往i收缩
    			  array[i]=array[i+1];
    		   index--;
    		   return true;
    	   }
    		   
     }
 //=======================================================================
        public void swap(int a,int b){
        	 Person temp;
        	 temp=array[a];
        	 array[a]=array[b];
        	 array[b]=temp;
        }
     
 //=======================================================================
       
     public void display(){
    	 for(int i=0;i<index;i++){
    		 System.out.println(array[i].getSn()+":  "+array[i].getName());
    	 }
     }

	//=====================================================================
	 //把数组里的元素分成两个区，一个区的数据总是比分界线大，一个总是比分界线小
	 //使用两个指针 ，然后交换 找到的元素 以privot为分界线
	 public int partitionIt(int left,int right,int privot){
		 
		 int leftPv=left-1;//左指针
		 int  rightPv=right;//右指针
		 while(true){
			 while(leftPv<right && array[++leftPv].getSn()<privot);
			 //左指针向右行进，直到遇到比 分界线privot大的停住
			 while(rightPv>left && array[--rightPv].getSn()>privot);
			 //右指针向左行进，直到遇到比分界线小的停住
			 if(leftPv>=rightPv)//两指针相遇，分区形成
				 break;
			 else{
				 swap(leftPv,rightPv);
			 }
			
			 
		 }
	System.out.println("cursor: "+array[leftPv].getSn()+" "
		+"right of arr "+array[right].getSn());
	System.out.println("leftPv: "+leftPv+" "+"rightPv: "+rightPv+" ");
	
		 swap(leftPv,right);
//因为使用数组最右边的元素作为分界线，所以leftPv总是会落在分界线上
		 //指向原来数组最右	元素，这时要交换leftPv和right重置分界线	 
		 
		 return leftPv;
	 }


//=================================================================
    ////////////////////////////////////////////
   ////////////  快速排序法！ //////////////////
   //////////////////////////////////////////
   public void  quickSort(int left,int right){
	    if((right-left)<=0)
	    	return;//只有一个元素，已经排好序了
	    else
	    {  
	    	int privot= array[right].getSn();//取数组最右边的元素为分界线
	       int partition =partitionIt(left,right,privot);
	       //把数组按分界线分区
	    	quickSort(left,partition-1);
	    	//在左边的分区子数组调用自己
	    	quickSort(partition+1,right);
	    	//在右边分区子数组调用自己
	    }
	    
	   
   }
}


////////////////////////////////////////////////////////////////////
//==================================================================
 class Person{
	 private String firstName;
	 private String lastName;
	 private int sn;
	 public Person(){
		 
	 }
	 public Person(int sn,String firstName,String LastName){
		 this.firstName=firstName;
		 this.lastName=LastName;
		 this.sn=sn;
	 }
	 public String getName(){
		 String name=firstName+"."+lastName;
		 return (name);
	 }
	 public int getSn(){
		 return sn;
	 }
	 
 }