插入排序

插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。

例如有一个长度为N的无序数组，进行N-1次的插入即能完成排序；

第一次，数组第1个数认为是有序的数组，将数组第二个元素插入仅有1个有序的数组中；

第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中......

第N-1次，数组前N-1个元素组成有序的数组，将数组的第N个元素插入由N-1个元素构成的有序数组中，则完成了整个插入排序。

以下面5个无序的数据为例：

65 27 59 64 58 （文中仅细化了第四次插入过程）

第1次插入: 27 65 59 64 58

第2次插入: 27 59 65 64 58

第3次插入: 27 59 64 65 58

第4次插入: 27 58 59 64 65

int array6[] = { 3, 4, 2, 1, 5, 6, 9, 8, 7, 0 };

/**

* 2 2,3,4

*/

for (int i = 1; i < array6.length; i++) {

int j = i; // i = 1 ; j = 1

int temp = array6[i];

while (j > 0 && temp < array6[j - 1]) {

int a = array6[j];

array6[j] = array6[j - 1]; // array6[2] = array6[1];

array6[j - 1] = a;

j--; }

System.out.println("第" + i + "次移动后：");

for (int i1 = 0; i1 < array6.length; i1++) {

System.out.print("," + array6[i1]);

}

System.out.println();

array6[j] = temp;

}

System.out.println("array6 直接插入排序之后：");

for (int i = 0; i < array6.length; i++) {

System.out.println("array6[" + i + "] = " + array6[i]);

数组的查找

方法（折半查找）

折半查找可以提高效率，但是必须要保证我们的数组是有序的。
方法一
public int halfsearch1(int[] arr,int a){
    int start,max,mid;
    start = 0;
    max = arr.length - 1;
    mid = (start+max)/2;
    
    while(arr[mid] != a){
        if(a > arr[mid]){
            start = mid + 1;
            
        }else{
            max = mid - 1;
        }
        if(min > max){
            return -1;
        }
        mid = (max+start)/2;
    }
    return mid;
}

方法二
public int halfsearch2(int[] arr,int a){ 
int start = 0,max = arr.length-1,mid;
 while(start <= max){
 mid = (max + start)/2;
 if(a > arr[mid]){
 start = mid + 1;
 }else if(a < arr[mid]){
 max = mid - 1;
 }else{
 return mid;
 }
 }
 return -1; 
}

第四节 数组的排序和查找