首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >std::排序是否也优化了对少量项目的排序?

std::排序是否也优化了对少量项目的排序?
EN

Stack Overflow用户
提问于 2015-07-17 08:58:12
回答 3查看 1.8K关注 0票数 5

在7项比较中有一种对5项进行排序的算法:如果对5项进行调用,设计一种有效的算法,在少于8次比较中对5个不同的键进行排序 std::sort()会使用该算法吗?这个算法能扩展到7个条目吗?在C/C++中对7个整数排序最快的算法是什么?

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2015-07-18 09:18:21

研究了std::sort在MSVC++2013的STL中的代码,对7个条目进行了插入排序。

一些评论建议使用排序网络。少数项目(最多32项)的排序网络可以生成这里。特别是,对于没有并行性的7项排序,最快的算法似乎是。根据实验这里,最快的SWAP宏实现是:

代码语言:javascript
复制
#define min(x, y) (x<y?x:y)
#define max(x, y) (x<y?y:x) 
#define SWAP(x,y) { \
    const int a = min(d[x], d[y]); \
    const int b = max(d[x], d[y]); \
    d[x] = a; d[y] = b; }

7项的排序-网络代码将是:

代码语言:javascript
复制
template<typename T> void sort7(T* d)
{
    SWAP(0, 1);
    SWAP(2, 3);
    SWAP(0, 2);
    SWAP(1, 3);
    SWAP(1, 2);
    SWAP(4, 5);
    SWAP(4, 6);
    SWAP(5, 6);
    SWAP(0, 4);
    SWAP(1, 5);
    SWAP(1, 4);
    SWAP(2, 6);
    SWAP(3, 6);
    SWAP(2, 4);
    SWAP(3, 5);
    SWAP(3, 4);
} 
票数 3
EN

Stack Overflow用户

发布于 2015-07-17 09:01:58

如果std::sort试图对小尺寸进行尽可能少的比较,这并不是标准的一部分。不同的实现可以做到这一点,但这将取决于您正在使用的库。

票数 3
EN

Stack Overflow用户

发布于 2015-07-17 09:01:58

算法依赖于实现。通常采用快速排序算法,即O(n log )。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/31471951

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档