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 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谢谢！

原创文章，作者：Maggie-Hunter，如若转载，请注明出处：https://blog.ytso.com/14658.html