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+"】不在数组内。";
}
}