当前位置: 首页 > news >正文

插入排序和希尔排序

目录

  • 1.直接插入排序
  • 2.希尔排序

1.直接插入排序

基本思想:
把待排序的数据按其大小逐个插入到一个已经排好序的有序序列中,直到所有的数据插入完成为止。

当插入第i个元素时,前面的a[0],a[1],...,a[i-1]个数据已经排好序了,此时用a[i]a[i-1],a[i-2],...进行比较,找到插入位置就将a[i]插入,原来位置上的元素顺序后移

在这里插入图片描述

void InsertSort(int* a, int n)
{for (int i = 0; i < n-1; i++){int end = i;//记录已经有序的数据的最后一个数据的下标int tmp = a[end + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else//a[end]<tmp,说明前(i+1)个数已经有序了{break;}}a[end + 1] = tmp;}
}

在这里插入图片描述

元素集合月接近有序,直接插入排序算法的时间效率更高
时间复杂度:O(N^2)
稳定性:稳定

2.希尔排序

希尔排序是直接插入排序的优化

1.预排序
2.直接插入排序
基本思想:
先选定一个整数,把待排序文件中所有数据分成gap个组,所有距离为gap的数据分在同一个组里,并对每一组的数据进行排序。然后,取gap=gap/3+1,重复上述分组的操作。当gap=1时,所有数据在同一组的已经排好序了

void ShellSort(int* a, int n)
{int gap = n;while(gap > 1){//+1保证最后一个gap一定是1//gap》1是预排序//gap==1是插入排序gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

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

当gap>1时都是预排序,目的是让数组更接近有序。当gap==1时,数组已经接近有序了,这样就会很快
时间复杂度:O(N^1.3)(ps:时间复杂度是不固定的)
稳定性:不稳定

http://www.lryc.cn/news/361797.html

相关文章:

  • Java web应用性能分析之【java进程问题分析定位】
  • c#控件笔记
  • STM32-15-DMA
  • Go语言 几种常见的IO模型用法 和 netpoll与原生GoNet对比
  • 大米cms安装支付逻辑漏洞
  • 使用 zxing 生成二维码以及条形码
  • 发布 jar 包到 maven 中央仓库
  • AI智能体研发之路-模型篇(四):一文入门pytorch开发
  • 英语口语中though的用法(even though、as though)
  • 菜刀冰蝎哥斯拉流量通讯特征绕过检测反制感知
  • 前端 JS 经典:判断数组的准确方法
  • 【仓库设置问题】
  • 深度学习知识与心得
  • Qt for Android
  • HTTP 的三次握手
  • 【Text2SQL 论文】T5-SR:使用 T5 生成中间表示来得到 SQL
  • 【HarmonyOS】应用屏蔽截屏和录屏
  • [BUG历险记] ERROR: [SIM 211-100] CSim failed with errors
  • Redis中大Key与热Key的解决方案
  • MySQL 视图(2)
  • Leecode---技巧---颜色分类、下一个排列、寻找重复数
  • ERC-7401:嵌套 NFT 标准的全新篇章
  • 代码随想录算法训练营Day6| 242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和
  • 三十四、openlayers官网示例Dynamic clusters解析——动态的聚合图层
  • SpringBoot登录认证--衔接SpringBoot案例通关版
  • vue3状态管理,pinia的使用
  • 入门到实践,手把手教你用AI绘画!
  • 大模型应用框架-LangChain
  • 探索Linux中的强大文本处理工具——sed命令
  • 冯喜运:6.3黄金原油晚间最新行情及独家操作策略指导