我是靠谱客的博主 落寞水壶,最近开发中收集的这篇文章主要介绍插入排序和二分寻找插入排序 二分查找,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

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

插入排序 

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

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

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+" ");
}

最后

以上就是落寞水壶为你收集整理的插入排序和二分寻找插入排序 二分查找的全部内容,希望文章能够帮你解决插入排序和二分寻找插入排序 二分查找所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(70)

评论列表共有 0 条评论

立即
投稿
返回
顶部