数据结构 ----- 折半插入排序

这篇具有很好参考价值的文章主要介绍了数据结构 ----- 折半插入排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

​​​​

折半插入排序

活动地址:CSDN21天学习挑战赛

一、折半插入排序

1.1 概念

折半插入排序(Binary Insertion Sort)是对插入排序算法的一种改进。所谓插入排序,就是不断的依次将元素插入前面已排好序的序列中。

1.2 查找过程
  • 折半插入排序的基本思想跟直接插入排序基本一致,都是通过将元素一个个插入有序序列进行排序;
  • 折半插入排序跟直接插入排序的区别在于寻找插入位置的方法,直接插入排序是由后往前一个个进行对比寻找合适的插入位置,而折半插入排序则是利用折半查找的思路寻找合适的插入位置;
  • 因为折半插入排序是直接插入排序的优化版本,所以单纯看每一趟排序的结果跟直接插入排序的结果是一样的;

数据结构 ----- 折半插入排序

图 1.1
1.3 代码演示
1.3.1
  • 建立一个数组,并将待排序元素传入数组;
  • 建立一个排序方法,方法内传入所建立的数组;

数据结构 ----- 折半插入排序

图 1.2
1.3.2
  • 跟直接插入排序一样,从第二个元素开始依次插入已排序的序列中,直到所有元素都处于有序区;( 第一个元素默认在有序区,做对第一个元素的插入操作没有意义
  • 建立三个变量并初始化;
  • 一个变量存储最小坐标,一个变量存储当前最大坐标,一个变量存储中间值坐标;
  • 建立一个辅助变量,用于存储当前插入元素;

数据结构 ----- 折半插入排序

图 1.3
1.3.3
  • 在 for 循环内部再建立一个循环,功能是用于查找插入位置;
  • 给中间值赋初值,即最小坐标和最大坐标的和的一半;
  • 然后拿待插入元素跟每次循环的中间元素的值进行对比,如果小于等于中间值就代表插入位置在中间坐标右边到最大坐标的范围内, 如果小于中间元素的值则代表在最小坐标到中间坐标的范围内;
  • 最后跳出循环后对最大坐标进行自增 1 ,此时的最大坐标代表的是插入位置;

数据结构 ----- 折半插入排序

图 1.4
##### 1.3.4 >* 确定好位置后将插入位置开始的所有元素进行后移一位,为插入元素腾出空间; >* 最后将待插入元素插入相应位置即排序结束;

数据结构 ----- 折半插入排序

图 1.5
1.4 代码测试
  1. 在每一趟排序进行输出;
  2. 对获得的排序进行确认;
  3. 结论:代码可用无误;

数据结构 ----- 折半插入排序文章来源地址https://www.toymoban.com/news/detail-485687.html

图 1.6
1.5 代码分享
public class test {

    public static void main(String[] args){
       int[] arr = { 98 , 53 , 12 , 8 , 64 , 75 , 14 , 61};
        halfsort( arr );
        for (int j : arr) {
            System.out.print(j + " ");
        }
    }

    public static  void halfsort( int[] arr ) {
        for (int i = 1; i < arr.length; i++) {
            int mid;
            int low = 0 , high = i - 1;
            int temp = arr[i];
            while ( low <= high ){
                mid = ( low + high ) >>> 1;
                if ( arr[mid] <= temp ){
                    low = mid + 1;
                }else {
                    high = mid - 1;
                }
            }
            high++;
            for (int j = i; j > high ; j--) {
                arr[j] = arr[j - 1];
            }
            arr[high] = temp;
        }
    }
}

到了这里,关于数据结构 ----- 折半插入排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构 — 排序 — 插入排序】

    1.1.1排序的概念 排序: 所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性: 假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且

    2024年02月05日
    浏览(40)
  • 【数据结构】排序之插入排序

    在生活中处处可见排序,当我们打开京东或者其它购物平台时,搜索物品,它会有一定的排序。 这次就来分享的博客与排序有关。 正文开始。 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序

    2024年02月03日
    浏览(28)
  • 【数据结构—数据—插入排序】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、插入排序 1.1基本思想: 1.2直接插入排序: 1.3直接插入排序的代码实现 二、希尔排序( 缩小增量排序 ) 2.1算法讲解 2.2希尔排序的代码实现 总结 世上有两种耀眼的光芒,一种是正在升

    2024年02月02日
    浏览(33)
  • 【数据结构】常见排序算法——常见排序介绍、插入排序、直接插入排序、希尔排序

      在计算机科学中,排序是将一组数据按照指定的顺序排列的过程。排序算法由于执行效率的不同可以分为多种不同的算法。   通常情况下,排序算法可以分为两类,即 内部排序和外部排序 。内部排序是指数据全部加载到内存中进行排序,适用于数据量较小的情况,而

    2024年02月08日
    浏览(63)
  • 【数据结构】排序(1) ——插入排序 & 希尔排序

                              目录 一. 直接插入排序  基本思想  代码实现  时间和空间复杂度  稳定性 二. 希尔排序  基本思想  代码实现      时间和空间复杂度  稳定性             把待排序的记录按其关键码值的大小依次插入到一个已经排好序的有序序列中,直到

    2024年02月07日
    浏览(46)
  • 数据结构——插入排序与希尔排序

    🌇个人主页:_麦麦_ 📚今日名言:喜你成疾,药石无医。——《玫瑰与鹿》         在本篇文章,我们将为小伙伴们进行排序概念的基本讲解并具体讲解其中的两种基础排序: 插入排序和希尔排序 ,希望小伙伴们能够从中有所收获!!! 1.1排序的概念 排序 :所谓排序,

    2023年04月09日
    浏览(39)
  • 数据结构进阶篇 之 【插入排序】详细讲解(直接插入排序,希尔排序)

    千万不要因为一件事不会做而失去信心,你又不是只有这一件事不会,你还有很多呢 1.1 基本思想 1.2 实现原理 1.3 代码实现 1.4 直接插入排序的特性总结 2.1 基本思想 2.2 实现原理 2.3 代码实现 2.4希尔排序的特性总结 –❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–

    2024年04月12日
    浏览(74)
  • 【数据结构】排序:插入排序与希尔排序详解

    本章开始就要分享一些常用的排序方法,我们的日常生活中很多地方都要使用排序,比如电商平台可以按照你的需求进行排序,或者是你想了解大学的综合排名时    我们之前也学到过一些简单的排序比如冒泡排序,虽然他在时间复杂度上可以说是依托答辩,但是作为排序算

    2024年02月13日
    浏览(43)
  • 【数据结构】排序之插入排序和选择排序

    🔥 博客主页: 小王又困了 📚 系列专栏: 数据结构 🌟 人之为学,不日近则日退 ❤️ 感谢大家点赞👍收藏⭐评论 ✍️ 目录 一、排序的概念及其分类 📒1.1排序的概念 📒1.2排序的分类 二、插入排序 📒2.1直接插入排序 🎀2.1.1直接插入排序的思想 🎀2.1.2排序步骤  🎀2

    2024年02月08日
    浏览(33)
  • 数据结构与算法:插入排序&希尔排序

    假设现在你有一个有序的数组,你要把一个数据插入到数组中,保证插入后依然有序,要怎么做? 对于人来说,这个问题就像是在整理扑克牌,瞄一眼就知道应该插入什么位置。但是对于程序来说,就需要一一对比,直到找到一个位置 左边比它大,右边比它小 ,就算找到了

    2024年01月17日
    浏览(58)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包