Java實現各種排序與查找

import java.io.;
import java.util.;
/**


排序與查找類
@author 凌碩
@serial 1.0
*/
public class SearchingList {
 private int[] list;
 private StringTokenizer st;
 private int number;
 public SearchingList() throws IOException{

 BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
 String line;
 System.out.print("請輸入元素總個數：");
 this.number=Integer.parseInt(in.readLine());
 this.list=new int[number+1];
 System.out.println("請輸入各元素，用空格隔開");
 line=in.readLine();
 if(!line.isEmpty())
     st=new StringTokenizer(line);
 for(int i=1;i<this.number+1&&st.hasMoreTokens();i++){
     this.list[i]=Integer.parseInt(st.nextToken());
 }
 System.out.println("原序列：");
 this.output(list);
 System.out.println();

}
 /**

簡單選擇排序
@author 凌碩
*/
public void simpleSelectSort(){
 int j,k,temp;
 int[] list=this.copyList();
 System.out.println("簡單選擇排序：");
 for(int i=1;i<this.number;i++){
 j=i;
 for(k=i+1;k<this.number+1;k++)
     if(list[k]<list[j])j=k;
 if(j!=i){
     temp=list[j];
     list[j]=list[i];
     list[i]=temp;
 }
 System.out.print("第"+i+"趟：");
 this.output(list);
 System.out.println();

 }
}
/**
折半插入排序
*/
public void biInsertionSort(){
 int j,low,high,mid;
 int[] list=this.copyList();
 System.out.println("折半插入排序：");
 for(int i=2;i<=this.number;i++){

 list[0]=list[i];
 low=1;
 high=i-1;
 while(low<=high){
     mid=(low+high)/2;
     if(list[0]<list[mid])
         high=mid-1;
     else
         low=mid+1;
 }
 for(j=i-1;j>=high+1;j--)
     list[j+1]=list[j];//右移

 list[high+1]=list[0];
 //輸出每一步的結果
 System.out.print("第"+(i-1)+"趟:");
 this.output(list);
 System.out.println();

}
}
/**

冒泡排序
@author 凌碩
*/
public void bubbleSort(){
 int temp,lastExchange,num = 1;
 int i=this.number;
 int[] list=this.copyList();
 System.out.println("冒泡排序：");
 while(i>1){
 lastExchange=1;
 for(int j=1;j<i;j++)
     if(list[j]>list[j+1]){
         temp=list[j+1];
         list[j+1]=list[j];
         list[j]=temp;//交換元素
         lastExchange=j;//記下進行交換的記錄位置
     }
 i=lastExchange;
 //輸出每一步的結果
 System.out.print("第"+num+"趟:");
 for(int k=1;k<this.number+1;k++)
     System.out.print(list[k]+" ");
 System.out.println();
 num++;

 }
}
/**
順序查找
@throws IOException
@throws NumberFormatException
*/
public void dirSearch() throws NumberFormatException, IOException{
 BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
 System.out.println("順序查找：請輸入所要查找的元素：");
 int e = Integer.parseInt(in.readLine());
 int k=1;
 while(k<=this.number&&this.list[k]!=e)k++;
 if(k<=this.number)System.out.println("在位置"+k+"找到元素"+e);
 else System.out.println("沒有找到元素"+e);
}
/**
折半查找
@throws IOException
@throws NumberFormatException
*/
public void binSearch() throws NumberFormatException, IOException{
 BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
 System.out.println("折半查找:請輸入所要查找的元素：");
 int e = Integer.parseInt(in.readLine());
 int low = 1; 
 int high = this.number;
 int mid,temp,t=0;
 int[] list=this.copyList();
 //排序
 for(int i1=1;i1<this.number;i1++){

 int j = i1;
 for(int k = i1+1;k<this.number+1;k++)
     if(list[k]<list[j])j=k;
 if(j!=i1){
     temp=list[j];
     list[j]=list[i1];
     list[i1]=temp;
 }

}
 //查找
 while(low <= high){

 t++;
    mid=(low + high)/2;
    if(e==list[mid]){
        System.out.println("在第"+t+"趟找到元素"+e);//找到
        return;}
    else if(e<list[mid])
     high=mid-1;//左半區
   else low=mid+1;//右半區
}
System.out.println("沒有找到元素"+e);


}
/*序列的副本/
private int[] copyList(){
 int[] inlist=new int[this.number+1];
 for(int i=1;i<this.number+1;i++){

 inlist[i]=this.list[i];

}
 return inlist;
}
/*輸出序列/
private void output(int[] list){
 for(int i=1;i<this.number+1;i++){

 System.out.print(list[i]+" ");

}
}
} </pre>