Java排序查找算法——二分法與遞歸的應用實例

問題描述：

對數組元素進行查找與排序，利用二分法與遞歸實現。

完整實例1：

public class SortDemo
{
  public static void main(String[] args)
  {
      int[] arr={10,2,300,41,15,6};
      for(int a:arr)
      {
        System.out.print("["+a+"]");   
      }
    // new SortDemo().insertSort(arr);
    new SortDemo().binaryInsertSort(arr);
      System.out.println();
      for(int a:arr)
      {
        System.out.print("["+a+"]");   
      }
  } 
   
  //二分法排序
  public void binaryInsertSort(int[] a)
  {
      for(int i=1;i<a.length;i++)
      {
        int temp=a[i];
        int low=0;
        int high=i-1;
        while(low<=high)
        {
            int mid = (low+high)/2;
            if(a[mid]<temp)
            {
                low=mid+1;
            }
            else
            {
                high=mid-1;
            }
        }
        for(int j=i-1;j>=low;j--)
        {
            a[j+1]=a[j];
        }
        a[low]=temp;
      }
  }
   
  //插入排序
  public void insertSort(int[] a)
  {
      int i;//參與比較的元素的前一個元素的坐標
      int key;//當前參與比較的元素
      for(int j=1;j<a.length;j++)
      {
        key=a[j];
        i=j-1;
        while(i>=0&&a[i]>key)
        {
            a[i+1]=a[i];//右移一位
            i--;//i前移
        }
        a[i+1]=key;
      }
  }
}

完整實例2：

//二分查找法
import java.util.*;
public class BinarySearchDemo
{
  public static void main(String[] args)
  {
        int[] arr={10,2,300,41,15,6};
        Arrays.sort(arr);//對數組進行自然排序
        //System.out.println(new BinarySearchDemo().method1(arr,41));   
        System.out.println(new BinarySearchDemo().method2(arr.length-1,0,arr,41));   
  }
  //遞歸實現二分查找
  public String method2(int b,int s,int[] a,int g)
  {
      int m;        //查找部分中中間值坐標
      if(s<b)
      {
        m=(b+s)/2;
        if(a[m]==g)
        {
            return "您查找的【"+g+"】為在數組中大小排第【"+(m+1)+"】位。";
        }
        else if(a[m]>g)//如果中間值比目標值大，比較左半部分，
        { 
            b=m-1;//查找部分中最高位坐標變為中間值的前一個
            return method2(b,s,a,g);
        }
                  else  //如果中間值比目標值小，則比較右半部分
        {
              s=m+1;//查找部分的最低位變為中間值的後一個
              return method2(b,s,a,g);
        }
      }
      return "您查找的【"+g+"】不在數組內。"; 
  }
   
  //參數是數組和目標值
  public String method1(int[] a,int g)
  {
      Arrays.sort(a);//對數組進行自然排序
      int b=a.length-1;//查找部分中最高位坐標
      int s=0;        //查找部分中最低位坐標
      int m;        //查找部分中中間值坐標
      while(b>=s)
      {
        m=(b+s)/2;
        if(a[m]==g)
        {
             
            return "您查找的【"+g+"】為在數組中大小排第【"+(m+1)+"】位。";
        }
        else if(a[m]>g)//如果中間值比目標值大，比較左半部分，
        { 
            b=m-1;//查找部分中最高位坐標變為中間值的前一個
        }
        else  //如果中間值比目標值小，則比較右半部分
        {
              s=m+1;//查找部分的最低位變為中間值的後一個
        }
      }
      return "您查找的【"+g+"】不在數組內。";
  }
   
}