概述
上次说了冒泡和选择排序,这次关于排序再说一下插入排序
插入排序
插入排序的主要思想是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
通俗理解为用需要确定位置的元素和它前面的元素进行比较,找到比该元素小的,将该元素放在比它小的元素的下一位。
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+" "); }
最后
以上就是落寞水壶为你收集整理的插入排序和二分寻找插入排序 二分查找的全部内容,希望文章能够帮你解决插入排序和二分寻找插入排序 二分查找所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复