1. 全栈程序员必看首页

折半插入排序(C语言)

全栈程序员-站长 • • 未分类 • 阅读 1

折半插入排序(C语言)折半插入排序 1 排序原理利用折半查找的方法来查找插入的位置 然后再直接将需要插入的数据插入该位置即可排序过程以从小到大排序为例 首先用 key 存储需要排序的数据第一步 折半查找 用 low mid high 划分两个区域 low mid 1 和 mid 1 high 第二步 判断 如果 key 值小于序列的中间值 mid 则代表 key 值应该插入左边的区域 low mid 1 然后对 low mid 1 再重复划分区域 直到 low gt high 为止第三步 插入 最后的插入位置应该是 hig


数据结构总目录



折半插入排序

在直接插入排序的基础上，由于在查找插入位置时，所查找的序列一定是有序序列，故可以利用折半二分查找算法来优化查找的效率

1. 图文解析

以从小到大排序为例，首先用key存储需要进行插入排序的数据
（1）划分区域：用low、mid、high划分两个区域【low，mid-1】和【mid+1，high】
在这里插入图片描述
（2）折半查找：若key小于中间值【mid】，则key值应插入左区域【low，mid-1】，反之应插入右区域【mid+1，high】
在这里插入图片描述
在这里插入图片描述
（3）插入数据：最后插入位置为high+1，只需将high之后位置的数据整体后移，然后将key赋值给【high+1】，即完成插入。
在这里插入图片描述











2. 源代码

#include  
     #define size 10 void BInsertSort(int *num, int len) { 
    int i, j, low, high, mid, key; for (i = 1; i < len; i++) { 
    // 判断当前数据是否需要进行插入 if (num[i - 1] > num[i]) { 
    // 获取需要插入的数据 key = num[i]; // 初始查找范围为 [0, i-1]（有序） low = 0; high = i - 1; // 进行折半二分算法查找插入的位置 while (low <= high) { 
    // 获取中间下标 mid = (low + high) / 2; if (key <= num[mid]) { 
    // 如果key小于中间值，则缩小查找范围到左子序列 high = mid - 1; } else { 
    // 如果key大于中间值，则缩小查找范围到右子序列 low = mid + 1; } } // 整体后移 for ( j = i - 1; j >= high + 1; j--) { 
    num[j + 1] = num[j]; } // 插入数据 num[high + 1] = key; } } } int main() { 
    int i, num[size] = { 
   578, 432, 1325, 384, 5432, 651, 3817, 564, 387, 5}; BInsertSort(num, size); for (i = 0; i < size; i++) { 
    printf("%d ", num[i]); } printf("\n"); return 0; }

3. 测试结果

在这里插入图片描述
在这里插入图片描述

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/200970.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月20日 上午10:13
下一篇 2026年3月20日 上午10:13


相关推荐

  • DeepSeek 从入门到实战：完整教程与部署指南 DeepSeek

    DeepSeek 从入门到实战：完整教程与部署指南

    DeepSeek 从入门到实战：完整教程与部署指南

    全栈程序员-站长的头像 全栈程序员-站长
    2026年3月16日
    2
  • int使用规则_single是什么数据类型

    int使用规则_single是什么数据类型

    int使用规则_single是什么数据类型先说结论吧，方便快速查询验证。总结区别int类型大小为8字节int8类型大小为1字节int16类型大小为2字节int32类型大小为4字节int64类型大小为8字节go语言中的int的大小是和操作系统位数相关的，如果是32位操作系统，int类型的大小就是4字节;如果是64位操作系统，int类型的大小就是8个字节取值范围int8:-128~127int16:-32768~32767int32:-2147483648~214

    全栈程序员-站长的头像 全栈程序员-站长
    2026年1月29日
    5
  • RabbitMQ延迟队列实现

    RabbitMQ延迟队列实现

    RabbitMQ延迟队列实现1 生产者生产一条延迟消息 根据延迟时间的不同 利用不同的 routing key 将消息路由到不同的延迟队列 每个队列都设置了不同的 TTL 属性 TTL TimeToLive 生存时间 并绑定到同一个死信交换机中 2 消息过期后 根据 routing key 的不同 又会被死信交换机路由到不同的死信队列中 消费者只需要监听对应的死信队列进行消费即可

    全栈程序员-站长的头像 全栈程序员-站长
    2026年3月16日
    2
  • TCP协议-TCP粘包问题

    TCP协议-TCP粘包问题

    TCP协议-TCP粘包问题一 前言我们知道 TCP 是一个面向字节流的传输层协议 流 意味着 TCP 所传输的数据是没有边界的 这不同于 UDP 协议提供的是面向消息的传输服务 其传输的数据是有边界的 TCP 的发送方无法保证对方每次收到的都是一个完整的数据包 于是就有了粘包 拆包问题的出现 粘包 拆包问题只发生在 TCP 协议中 二 什么是粘包 拆包 假设客户端向服务器连续发送了两个数据包 用 packet1 和 packet2 来表示 那么服务端收到的数据可以分为下面三种情况 第一种情况 接收端正常

    全栈程序员-站长的头像 全栈程序员-站长
    2026年3月18日
    2
  • Intellij IDEA 导入 eclipse web 项目详细操作[通俗易懂] idea

    Intellij IDEA 导入 eclipse web 项目详细操作[通俗易懂]

    IntellijIDEA导入eclipseweb项目详细操作第一步：准备工具我用的是IntelliJIDEA2017.1(64)这个版本的，在eclipse中找到我之前写skye_cnmy(非Maven),skye_client(Maven)的项目导入。第二步：在IntellijIDEAFile–&gt;New–&gt;ProjectfromExisting…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年4月15日
    57
  • structs与ajax结合的问题

    structs与ajax结合的问题

    structs与ajax结合的问题structs 与 ajax 结合的问题

    全栈程序员-站长的头像 全栈程序员-站长
    2026年3月16日
    2

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号