在线客服
扫描二维码
下载博学谷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. }
总结
折半插入排序相对稳定,相对于直接插入排序,减少了比较次数;但是相对直接插入排序,移动次数不变。
以上就是折半插入排序的干货教程讲解,大家都弄懂了吗?
— 申请免费试学名额 —
在职想转行提升,担心学不会?根据个人情况规划学习路线,闯关式自适应学习模式保证学习效果
讲师一对一辅导,在线答疑解惑,指导就业!
相关推荐 更多
Static局部变量与全局变量的区别?编译后映射文件是否包含此类变量的地址?
全局变量(外部变量)的说明之前再冠以static 就构成了静 态的全局变量。全局变量本身就是静态存储方式, 静态全局变量当然也是静态存储方式。这两者在存储方式上并无不同。这两者的区别虽在于非静态全局变量的作用域是整 个源程序, 当一个源程序由多个源文件组成时,非静态的 全局变量在各个源文件中都是有效的。
13586
2019-06-04 11:57:17
电脑编程入门自学Java指南
随着Java近些年来的强劲发展,想要转行学习Java的初学者也越来越多了。然而,入门自学Java并不是一件轻松的事情。众所周知,万事开头难,尤其是没有编程语言基础的学习者,不仅仅需要付出更多的心血和汗水,还需要科学地制定学习规划,下面小编为大家准备了一份电脑编程入门自学Java指南,内容包括了Java的学习内容和路径,赶紧来一起看看吧!
5213
2019-12-30 15:15:34
程序员常用的JVM 配置参数汇总
JVM可以算是初级程序员进阶高级程序员必须要掌握的核心技能之一。另外,在许多面试过程中,JVM也是检验Java程序员能力水平的试金石。今天我们不谈Java底层实现的原理,而是为大家整理汇总了一些常见的,希望对大家编写代码有所帮助。
5145
2020-03-04 18:08:39
Java开发中Netty线程模型原理解析
Netty是Java领域有名的开源网络库,具有高性能和高扩展性的特点,很多流行的框架都是基于它来构建。netty 线程模型不是一成不变的,取决于用户的启动参数配置。通过设置不同的启动参数Netty ,可同时支持 Reactor 单线程模型、多线程模型。
4866
2021-05-13 10:28:26
Java架构师需要掌握哪些知识和职业技能?
成为Java架构师前是一名Java高级程序员,基础知识牢固对Java的了解全面而且深入。熟练使用各种框架,并知道实现的原理;Jvm虚拟机原理、调优操作,懂得jvm能让你写出性能更好的代码;池技术,对象池、连接池、线程池都要会;Java反射技术写框架的技术;Java各种集合对象的实现原理,了解这些可以让你在解决问题时选择合适的数据结构高效地解决问题写出代码。
3853
2022-06-09 15:20:38