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

}本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-03/114633.htm