introsort(内省排序)
本文转载于：https://blog.csdn.net/sky453589103/article/details/51116264
快速排序是一种很快的算法，它平均的时间复杂度WieO(nlgn)， 最坏时间复杂度为O(n^2)。但是快排有很多改良版，其中一种就是内省式的快排，在STL中的快快排使用的就是这种算法。
1.为什么需要这种算法
因为快排在面对小数组（比如大小为10的数组）且基本有序的情况下，它的表现还没插入排序要好。因为数组的基本有序，使得插入排序不用很多次的执行元素的移动，并且可以避免递归。 在SGI STL中的函数sort使用的排序算法其实就是内省式的排序算法。内省的排序算法是基于快排实现的。假设待排序的数组大小为n，去一个k值，使得k为满足2^k <= n的最大值。k为最大的递归层次、 为什么要设置最大递归层次呢？ 因为快排的递归层次过深的时候，很可能会退化成O(n^2)。内省式排序使用k来控制快排的递归深度，当快排的递归深度到达k的时候选择使用heap排序。
2. 为什么不一开始就使用heap排序
heap排序在平均时间复杂度是O(nlgn)，最坏情况也是O(nlgn)，看起来要比快排要快。但是实际上，快排是要比heap排序要快，第一个原因是：heap排序虽然和快排在平均情况下的时间复杂度是O(nlgn)，但是heap排序的时间常数要比快排的时间常数要大。第二个原因是：据统计，快排的最坏情况在是很少发生的。第三个原因是：快排能够比较好的吻合程序的空间局部性原理，因为它操作的基本都是相邻的元素（虚拟存储器的设计理论基础中就有程序的时间局部性和空间局部性），能够减少内存缺页中断的发生次数。
3.为什么要使用heap排序呢
因为在递归层次太深的时候，就意味着发生最坏情况的概率大大的提升了，这时候因为heap排序的最坏情况下的时间复杂度是O(nlgn)比快排的O(n^2)要好，因此使用heap排序能更好优化排序效率。
参考资料：《STL源码剖析》
最新文章
- C++ Pitfalls 之 reference to an object in a dynamically allocated containter
- ArcGIS生成根据点图层生成等值面并减小栅格锯齿的操作步骤
- WPF窗体的命令绑定
- DHT(Distributed Hash Table) Translator
- Adobe Edge Animate –Edge Commons强势来袭，Edge团队开发成为现实
- 深刻理解C#的传值调用和传引用调用
- js制作圆角按钮（兼容谷歌，ie7，ie8）
- [转]VS2010 （C#）winform程序打包发布图解
- html5 实现手机端相册浏览功能
- Python学习打算
- 使用CoApp创建NuGet C++静态库包
- C# 生成二维码 QRCoder
- JavaScript之事件委托（附原生js和jQuery代码）
- istio-opentracing链路追踪方案
- centos6.8安装mysql5.5
- 文件操作命令(replace)
- MFCC特征参数提取流程概述
- C#设置随机整数
- 网站的title添加图片
- 百度地图自定义icon,定位偏移问题