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

C++ STL sort函数的底层实现

C++ STL sort函数的底层实现

sort函数的底层用到的是内省式排序以及插入排序,内省排序首先从快速排序开始,当递归深度超过一定深度(深度为排序元素数量的对数值)后转为堆排序。

先来回顾一下以上提到的3中排序方法:

  1. 快速排序:先选一个基准值(一般为首值),将比它大的数置于其右侧,将比它小的数置于它左侧,那么这个基准值所在的位置定是整个数组的有序位。然后递归该基准左右两子数组。算法复杂度为nlogn;
  2. 堆排序:将数组建立成大顶堆,重复从堆顶取出数值最大的结点(把根结点和最后一个结点交换,把交换后的最后一个结点移出堆,移出的这个数值为未排序数组的最后),并让残余的堆维持大顶堆的性质。时间复杂度为nlogn;
  3. 插入排序:对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。时间复杂度为n2;

其中先讲下快排和堆排,快排的平均复杂度为nlogn,但是它的复杂度是根据基准值来决定的,基准值选择的不好,最坏的复杂度会达到n2,而堆排序的复杂度是一定的为n*logn,那为什么不直接使用堆排序呢,是因为在将堆顶值与最后一个结点值交换并移除最后一个值后,在重新建堆的过程中,交换到堆顶的值显然比每个结点要小,但还是要经过对比判断,这个判断其实是多余的,因此这是它相比快排较慢的原因。

于是,内省式排序结合了快排和堆排的特点,当快速排序到大一定深度(2logn)时,采用堆排序,以维持n*logn的复杂度。

在sort函数中,内省排序过程中子数组长度小于16时,采用的是插入排序,因为当数组长度较短时,就是数组已经大致排序过了,对大致有序的数组(即逆序对不多了)用插入排序的算法复杂度会很小,可以想象成理牌的过程。

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

相关文章:

  • ICP算法和优化问题详细公式推导
  • 【安全狗】linux免费服务器防护软件安全狗详细安装教程
  • 【iOS】自定义字体
  • WPF实战学习笔记06-设置待办事项界面
  • 推荐几个不错的免费配色工具网站
  • gitee page发布的静态网站,无法播放目录中的mp4视频
  • opencv-26 图像几何变换04- 重映射-函数 cv2.remap()
  • SkyWalking链路追踪中span全解
  • 【前端知识】React 基础巩固(三十一)——Redux的简介
  • 拦截Bean使用之前各个时机的Spring组件
  • RT thread 之 Nand flash 读写过程分析
  • 独立站最全出单营销指南,新手卖家赶紧学起来吧!
  • Git移除commit过的大文件
  • 再见 Spring Boot 1.X ,Spring Boot 2.X 走向舞台中心
  • Jsonp劫持
  • STM32CubeIDE(串口)
  • Python编程很简单,四步菜鸟到高手(文末送书5本)
  • Labview串口通信MSComm实现串口收发
  • 字节跳动 EB 级 Iceberg 数据湖的机器学习应用与优化
  • CentOS 安装Mysql8
  • 3-Linux实操
  • Yarn 集群的架构和工作原理
  • PostgreSQL-视图-03-查询对象依赖关系视图-dba_dependencies
  • Vue style中的 scoped 属性
  • 移动端适配rem
  • Go语言开发小技巧易错点100例(八)
  • 100个网络安全测试面试题
  • 7.26 作业 QT
  • Python - Opencv应用实例之树叶自动分割、标签及统计分析系统
  • IC设计工程师,参加IC面试应该注意哪些细节?