Java实现各种排序与查找

     <pre class="brush:java; toolbar: true; auto-links: false;">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>    <br />