首页 > 图灵资讯 > 技术篇>正文

【图灵干货】折半插入排序讲解

2021-12-30 15:11:21

  我们相信大家已经熟悉了折半插入排序的定义,也就是对插入排序算法的一种改进,所谓排序算法,就是不停地将元素按顺序插入先前排列的顺序。这篇文章将从介绍插入排序的思想,算法说明,折半插入排序代码实现以上方面讲解折半插入排序讲解,感兴趣的小伙伴就继续看下去!

半折式插入排序解释

  插入分类介绍思想。

  折叠半插入排序与直接插入排序算法的原理相同。不过,当将数据插入到已排序的数据时,使用来对半查询进行二分查找。首先将已排序序列的中间元素与要插入的数据相比较,如果中间元素的值比要大,那么这个待插入的数据属于数组的前一半,否则它就属于后半部分。连续模拟,不断缩小距离,确定想要插入的位置。

算法说明:

  待排序数据: 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. }

  总结

  折半插入排序相对稳定,相对于直接插入排序,减少了比较次数;但是相对直接插入排序,移动次数不变。

  以上就是折半插入排序的干货教程讲解,大家都弄懂了吗?

上一篇 Struts2入门框架基础教程
下一篇 组合模式深度解析

文章素材均来源于网络,如有侵权,请联系管理员删除。