temptest.java

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

package Array;

public class TempTest {
      //int size;
      int[] array;
      int index;
      
      public TempTest(int max){
    	  array=new int[max];
    	  index=0;
      }
      
      public void insert(int key){
    	  array[index++]=key;
      }
      
      public int  find(int key){
    	   int i=0;
    	   while(array[i]!=key){
    		  i++;
    		  if(i>=index)
    		    return -1;
    	   }
    	   return array[i];
      }
      public void sort(){
    	  quickSort(0,index-1);
      }
      
      private void quickSort(int left,int right){
    	    int rg=right-left+1;
    	    if(rg<=3)
    	    	miniSort(left,right);
    	    else{
    	    	int privote=midemOf3(left,right);
    	    	int newleft=partitionIt(left,right,privote);
    	    	quickSort(left,newleft-1);
    	    	quickSort(newleft+1,right);
    	    	
    	    }
    	  
      }
      
      public int partitionIt(int left,int right,int privote){
    	  int leftPv=left;
    	  int rightPv=right-1;
    	  while(true){
    		  while(array[++leftPv]<privote );
    		  while( array[--rightPv]>privote);
    		      if(leftPv>=rightPv)//two pointer cross,pritition made;
    		    	  break;
    		      else{
    		    	   swap(leftPv,rightPv);
    		      }
    	  }
    	  swap(leftPv,right-1);
    	  return leftPv;
      }
      
      private void swap(int ind1,int ind2){
    	    int temp=array[ind1];
    	    array[ind1]=array[ind2];
    	    array[ind2]=temp;
      }
      
      public void miniSort(int left,int right){
    	    int i=right-left+1;
    	    if(i<=1)
    	    	return;
    	    else if(i==2){
    	    	 if(array[left]>array[right])
    	    		 swap(left,right);
    	    }
    	    else if(i==3){
    	    	 if(array[left]>array[right])
    	    		 swap(left,right);
    	    	 if(array[left]>array[right-1])
    	    		 swap(left,right-1);
    	    	 if(array[left+1]>array[right])
    	    		 swap(left+1,right);
    	    }
      }
      
      public int midemOf3(int left,int right){
    	     int mid=(right-left)/2;
    	     if(array[left]>array[right])
	    		 swap(left,right);
	    	 if(array[left]>array[mid])
	    		 swap(left,mid);
	    	 if(array[mid]>array[right])
	    		 swap(mid,right);
	    	 swap(mid,right-1);
    	  return array[right-1];
      }
      
      public void display(){
		  System.out.println("==========================");
    	  for(int i=0;i<index;i++)
    		  System.out.println(i+": "+array[i]);
    	  System.out.println("==========================");
      }
	 
}

class app{
	  public static void main(String[] args){
		    TempTest arr=new TempTest(50);
		    for(int i=0;i<25;i++)
		    	arr.insert((int)(Math.random()*200));
		    arr.display();
		    arr.sort();
		    arr.display();
		    
	  }
}