GCC中使用哪种排序算法? [英] Which sorting algorithm is used in GCC?

查看:154
本文介绍了GCC中使用哪种排序算法?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

cplusplus.com std :: sort 复杂性被定义:


复杂性



平均大约N * logN比较(其中N是最后一位)。
在最糟糕的情况下,最多可达N2,具体取决于库实现所使用的特定排序算法。


我有一些限制在运行时为我的应用程序。所以我需要知道如果我应该实现我自己的排序算法,否则它只会浪费时间。它们是用gcc编译的,所以我需要知道gcc使用哪种排序算法。 GCC使用 Musser的插画。这保证了最坏情况下运行时间为O( n ):


<


它以快速排序开始,并在递归深度超过一个级别时切换到堆排序。该实现可以在 <$ c $ __ introsort_loop 函数中的c> stl_algo.h 标题


From cplusplus.com std::sort complexity is defined:

Complexity

Approximately N*logN comparisons on average (where N is last-first). In the worst case, up to N2, depending on specific sorting algorithm used by library implementation.

I have some limitations at running time for my apps. So i need to know if should i implement my own sorting algorithm or it would be only waste of time. They are compiled with gcc, so i need to know which sorting algorithm gcc uses.

解决方案

GCC uses a variation of Musser’s introsort. This guarantees a worst-case running time of O(n log n):

It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on … the number of elements being sorted.

The implementation can be found in the stl_algo.h header in the __introsort_loop function.

这篇关于GCC中使用哪种排序算法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆