（笔记）数组 插入式排序法 有序查找二分法

插入式排序法 数组排序法的一种

将数组分为有序和无序两部分

每次将来无序部分第一个数同有序部分进行比较，插入到有序部分的合适的位置，

一个长度为i的数组，初始有序部分为数组第一个元素，无序部分为其余的元素。

class InserSort{
	public void  sort(int arr[])
	{
		for(int i=1;i<arr.length ;i++)  //排序次数 第一位默认是有序的故i=1
		{
			int insertVal=arr[i];       //取得要插入有序列表中的数字
			int index=i-1;              //有序列表中的最后一个
			while(index>=0&&insertVal<arr[index]) //从有序表中最后一个数开始向前比较
			{
				arr[index+1]=arr[index];      //该表有序列表数字的位置
				index--;
			}
			arr[index+1]=insertVal;        //插入合适位置
		}
	}
}

查找 二分查找

对于一组数列 先将其排序为有序数列后进行查找，运用到的递归的思想

public class Demo1 {   //有序查找 二分法

	public static void main(String[] args) {
		// TODO Auto-generated method stub
    int arr[]={2,4,6,7,8,9,10};       //实例数组
    BinaryFind bf = new BinaryFind();
    bf.find(0, arr.length-1, 10, arr);
	}

}
class BinaryFind
{
	public void find(int leftIndex,int rightIndex,int  val, int[] arr)
	{
		int midIndex=(rightIndex+leftIndex)/2;
		int midVal=arr[midIndex];
		if(rightIndex>=leftIndex){              //判断递归查询是否停止
		if(midVal>val){
			find(leftIndex,midIndex-1,val,arr); //这句话重新调用find方法传入参数进行栈的开辟
		}else  if  (midVal<val)                 //继续进行if else if 判断。
		{
			find(midIndex+1,rightIndex,val,arr);//同上 重新调用方法传参数判断
		}else if(midVal==val)                   //若相等 输出下标
		{
			System.out.println("找到下标"+midIndex); 	
		}
	}
		}
}

其中 rightIndex同leftIndex判断是为了防止递归成为死归，else if 中的find指令重新调用public void find（）方法开辟信栈传入参数进行判断