插入排序

简介: 在待排序的元素中,假设前n-1个元素已有序,现将第n个元素插入到前面已经排好的序列中,使得前n个元素有序。按照此法对所有元素进行插入,直到整个序列有序。  但我们并不能确定待排元素中究竟哪一部分是有序的,所以我们一开始只能认为第一个元素是有序的,依次将其后面的元素插入到这个有序序列中来,直到整个序列有序为止。

步骤:


1.从第一个元素开始,该元素可以认为已经被排序

2.取下一个元素tem,从已排序的元素序列从后往前扫描

3.如果该元素大于tem,则将该元素移到下一位

4.重复步骤3,直到找到已排序元素中小于等于tem的元素

5.tem插入到该元素的后面,如果已排序所有元素都大于tem,则将tem插入到下标为0的位置

6.重复步骤2~5

思路:

 在待排序的元素中,假设前n-1个元素已有序,现将第n个元素插入到前面已经排好的序列中,使得前n个元素有序。按照此法对所有元素进行插入,直到整个序列有序。

 但我们并不能确定待排元素中究竟哪一部分是有序的,所以我们一开始只能认为第一个元素是有序的,依次将其后面的元素插入到这个有序序列中来,直到整个序列有序为止

void InsertSort(int* arr, int n)
{
  for (int i = 0; i < n - 1; ++i)
  {
    //记录有序序列最后一个元素的下标
    int end = i;
    //待插入的元素
    int tem = arr[end + 1];
    //单趟排
    while (end >= 0)
    {
      //比插入的数大就向后移
      if (tem < arr[end])
      {
        arr[end + 1] = arr[end];
        end--;
      }
      //比插入的数小,跳出循环
      else
      {
        break;
      }
    }
    //tem放到比插入的数小的数的后面
    arr[end  + 1] = tem;
    //代码执行到此位置有两种情况:
    //1.待插入元素找到应插入位置(break跳出循环到此)
    //2.待插入元素比当前有序序列中的所有元素都小(while循环结束后到此)
  }
}
相关文章
kail中卸载方法:apt-get remove和dpkg
kail中卸载方法:apt-get remove和dpkg
812 0
|
6月前
|
网络协议 安全 网络安全
雷池WAF+emby+ddnsgo搭建个人影音库,实现远程安全访问流媒体
雷池WAF+emby+ddnsgo搭建个人影音库,实现远程安全访问流媒体
465 5
|
4月前
|
缓存 PyTorch 算法框架/工具
离线推理精度问题分析
传统模型迁移到昇腾设备上出现了精度问题,介绍精度问题的定位方法和解决方案,重点介绍了精度问题的定位定界方法。
离线推理精度问题分析
|
9月前
|
人工智能 Serverless API
AI时代下的数据信息提取 | 多模态数据信息提取
多模态数据信息提取方案利用先进的大模型技术,支持文本、图像、音频和视频等多种格式文件的信息抽取。该方案通过函数计算FC构建Web服务,接收用户请求并调用视觉和文本模型进行处理,最终返回结果。部署过程简单易上手,适合新手操作,且提供详细的文档和截图指导。用户可通过在线WebUI或API接口实现信息提取,满足不同场景需求。此外,该方案支持批处理模式下的离线作业,大幅提高大规模数据处理效率,降低业务落地成本达50%。
|
机器学习/深度学习 数据可视化 数据挖掘
【视频】结构方程模型SEM分析心理学营销数据路径图可视化|数据分享
【视频】结构方程模型SEM分析心理学营销数据路径图可视化|数据分享
|
前端开发 JavaScript UED
使用JavaScript实现表单验证
使用JavaScript实现表单验证
|
SQL 存储 分布式计算
Hive【基础知识 02-2】【Hive CLI 命令行工具使用】【详细举例-包含测试脚本文件】
【4月更文挑战第7天】Hive【基础知识 02-2】【Hive CLI 命令行工具使用】【详细举例-包含测试脚本文件】
404 0
|
XML 存储 小程序
基于SpringBoot+Redis的前后端分离外卖项目-苍穹外卖微信小程序端(十四)
基于SpringBoot+Redis的前后端分离外卖项目-苍穹外卖微信小程序端(十四)
|
程序员
解决报错Exception encountered during context initialization
程序员不是在去生产bug的路上,那就是在去解决bug的路上。
268 1