上次说了冒泡和选择排序，这次关于排序再说一下插入排序

插入排序 

插入排序的主要思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

通俗理解为用需要确定位置的元素和它前面的元素进行比较，找到比该元素小的，将该元素放在比它小的元素的下一位。

int[] array ={10,7,9,9,20,14};
for(int i=1;i<array.length;i++){
    //将需要确定位置的元素先保存一次
    int key = array[i];
    //用需要确定位置的元素和它前面进行比较，找到比该元素小的就可以停了
    //记录找到的比该元素小的元素的下标
    int index = -1;
    for (int j = i-1;j>=0;j--){
        if (array[j]<=key){
            index = j;
            break;
        }
    }
    //挪动位置 从i-1到index+1 主要目的是将index+1位置空出来
    for (int k = i - 1;k >= index+1;k--){
        array[k+1] = array[k];
    }
    //将key放入index+1
    array[index+1] =key;
}
for (int q:array){
    System.out.print(q+" ");
}

 

二分查找

二分查找是折半查找，要求需要查找的数据源必须是有序的。

int[] a={1,2,7,9,13,20};
int start = 0;//范围的起始下标
int end =a.length-1;//范围的结束下标
int index = -1;//记录查找查好结果 也是记录下标
int key = 7;//要查找的数字
while(start <= end){
    //中间元素的小标
    int middle =(start+end)/2;
    if(a[middle]==key){
        index=middle;
        break;
    }else if(a[middle]<key){
        //要找的数字比中间元素大；所以在右边 start变化
        start = middle+1;
    }else if (a[middle]>key){
        //要找的数字比中间元素小；所以在左边 end变化
        end = middle-1;
    }
}

熟悉二分查找后，关于插入排序，我们可以进一步的加快插入排序的效率，将插入排序和二分查找相结合，得到二分插入排序

int[] array ={10,7,9,9,20,14};
for(int i=1;i<array.length;i++){
    //将需要确定位置的元素先保存一次
    int key = array[i];
    //用需要确定位置的元素和它前面进行比较，找到比该元素小的就可以停了
    //记录找到的比该元素小的元素的下标
    int index = -1;
   //二分插入排序 范围0到i-1
    int start = 0;
    int end = i-1;
    while(start <= end){
        int middle = (start+end)/2;
        if (array[middle]==key){
            index = middle;
            break;
        }else if (array[middle]>key){
            end = end-1;
        }else if (array[middle]<key){
            start = middle +1;
        }
    }
    /**///挪动位置 从i-1到index+1 主要目的是将index+1位置空出来
  if (index == -1){
      //说明前面没有和k相等的元素；key就应该放在start处
      index = start;
  }
  for (int k =i-1;k >= index;k--){
      array[k+1]= array[k];
  }
  array[index] = key;
}
for (int q:array){
    System.out.print(q+" ");
}

最后

以上就是落寞水壶最近收集整理的关于插入排序和二分寻找插入排序 二分查找的全部内容，更多相关插入排序和二分寻找插入排序 二分查找内容请搜索靠谱客的其他文章。