c++ stl sort
时间: 2023-09-15 20:23:24 浏览: 83
C++ STL中的sort函数使用的是一种组合了快速排序和插入排序的内省排序算法。内省排序首先从快速排序开始,当递归深度超过一定深度(深度为排序元素数量的对数值)后转为堆排序。快速排序是通过选择一个基准值,将比它大的数置于其右侧,将比它小的数置于它左侧,然后递归对基准值的左右两个子数组进行排序。堆排序则是将数组建立成大顶堆,并重复从堆顶取出数值最大的节点,直到整个数组有序。插入排序是对未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
在sort函数中,当内省排序过程中子数组长度小于16时,采用的是插入排序。这是因为当数组长度较短时,已经大致有序,对近乎有序的数组使用插入排序算法的时间复杂度较小,可以看作是整理扑克牌的过程。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [C++ STL sort函数的底层实现](https://blog.csdn.net/TABE_/article/details/125710863)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]