Java实现各种排序与查找详解编程语言

import java.io.*;

import java.util.*;


1.排序与查找类

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();

    }


2. 简单选择排序

    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();

        }

    }


3.折半插入排序

    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();

        }

    }


4.冒泡排序

    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++;

        }

    }


5.顺序查找

    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);

    }


6.折半查找

    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]+” “);

        }

    }

}

转载请注明来源网站:blog.ytso.com谢谢！