在线客服
扫描二维码
下载博学谷APP扫描二维码
关注博学谷微信公众号
相信大家都了解折半插入排序的定义,即对插入排序算法的一种改进,所谓排序算法过程,就是不断的依次将元素插入前面已排好序的序列中。本文将从插入排序思想介绍、算法说明、折半插入排序的代码实现这些方面讲解折半插入排序讲解 ,感兴趣的小伙伴就接着看下去吧!
插入排序思想介绍
折半插入排序与直接插入排序算法原理相同。只是,在向已排序的数据中插入数据时,采用来折半查找(二分查找)。先取已经排序的序列的中间元素,与待插入的数据进行比较,如果中间元素的值大于待插入的数据,那么待插入的数据属于数组的前半部分,否则属于后半部分。依次类推,不断缩小范围,确定要插入的位置。
算法说明:
待排序数据: 2 , 1 , 6 , 7 , 4
取第一个元素作为有序表,剩余的元素作为无序表
其中有序表: 2 ;无序表: 1 , 6 , 7 , 4
第一次比较,从无序表中取出第一个数 1 ,与中间值 2 比较, 1<2 , 1 插到 2 的前面,得到
有序表: 1 , 2 ;无序表: 6 , 7 , 4
第二次比较,从无序表中取出第一个数 6 ,与中间值 1 比较, 6>1 ,要放在 1 的后面,再与后半区(有序表: 2 )的中间值 2 比较, 6>2 , 6 插入到2 的后面,得到
有序表: 1 , 2 , 6 ;无序表: 7 , 4
第三次比较,从无序表中取出第一个数 7 ,与中间值 2 比较, 7>2 , 7 放在 2 后面,再与后半区(有序表: 6 )的中间值 6 比较, 7>6 , 7 放在 6 后面,得到
有序表: 1 , 2 , 6 , 7 ;无序表: 4
第四次比较,从无序表中取出第一个数 4 ,与中间值 2 比较, 4>2 , 4 放在 2 后面,再与后半区(有序表 :6,7 )的中间值 6 比较, 4<6 , 4 放在 6 前面,最终得到:
1 , 2 , 4 , 6 , 7
折半插入排序的代码实现
1.private void binaryInsertSort(int arr[]){
2.
3. int low = 0;
4. int high = 0;
5. int m = 0;// 中间位置
6. for(int i = 1; i < arr.length; i++){
7. low = 0;
8. high = i-1;
9. while(low <= high){
10. m = (low+high)/2;
11. if(arr[m] > arr[i])
12. high = m - 1;
13. else
14. low = m + 1;
15. }
16. // 统一移动元素,将待排序元素插入到指定位置
17. temp = arr[i];
18. for(int j=i; j > high+1; j--){
19. arr[j] = arr[j-1];
20. }
21. arr[high+1] = temp;
22. }
23. }
总结
折半插入排序相对稳定,相对于直接插入排序,减少了比较次数;但是相对直接插入排序,移动次数不变。
以上就是折半插入排序的干货教程讲解,大家都弄懂了吗?
— 申请免费试学名额 —
在职想转行提升,担心学不会?根据个人情况规划学习路线,闯关式自适应学习模式保证学习效果
讲师一对一辅导,在线答疑解惑,指导就业!
相关推荐 更多
Java基础 Jvm如何加载类?如何分配空间?
Java基础 Jvm如何加载类?如何分配空间?指的是将 class 文件的二进制数据读入到运行时数据区(JVM在内存中划分的)中,并在方法区内创建一个 class 对象JVM 运行起来时就给内存划分空间,这块空间就称为运行时数据区。
7935
2019-06-03 15:41:22
Java网络编程入门教程
网络编程在两个或两个以上的设备之间传输数据。程序员把数据发送到指定的位置或者接收到指定的数据,这是狭义的网络编程范畴。在发送和接收数据时,大部分的程序设计语言都设计了专门的API实现这些功能,程序员调用即可,基础的网络编程和打电话一样简单。
5680
2019-12-04 14:53:50
如何管理Spring Bean的生命周期?具体步骤解析
如何管理Spring Bean的生命周期?回答这个问题之前,我们可以先来看看Bean的定义,Bean是一个被实例化,组装,并通过Spring IOC容器所管理的对象。换句话说,那些组成应用程序的主体以及由Spring IOC容器所管理的对象就是bean。另外,在Spring中bean默认都是单例的。想要管理Spring Bean的生命周期,大概要按照以下步骤去做:
5718
2020-01-14 10:43:38
JavaWeb开发XML学习笔记整理
JavaWeb开发能力是Java程序员的必备基础能力,因此掌握它十分重要。今天本文要和大家分享的是JavaWeb开发中有关XML学习笔记的整理。主要内容包括了XML的概念、XML的语法、约束和解析。感兴趣的朋友就一起来看看吧!
5355
2020-04-03 00:40:49
Java原子操作之CAS原子指令学习
Java原子操作之CAS,CAS(Compare and Swap),即比较并替换,是用于实现多线程同步的原子指令。
2584
2022-07-01 13:57:43
热门文章
- 前端是什么
- 前端开发的工作职责
- 前端开发需要会什么?先掌握这三大核心关键技术
- 前端开发的工作方向有哪些?
- 简历加分-4步写出HR想要的简历
- 程序员如何突击面试?两大招带你拿下面试官
- 程序员面试技巧
- 架构师的厉害之处竟然是这……
- 架构师书籍推荐
- 懂了这些,才能成为架构师 查看更多
扫描二维码,了解更多信息
