在7项比较中有一种对5项进行排序的算法:如果对5项进行调用,设计一种有效的算法,在少于8次比较中对5个不同的键进行排序 std::sort()会使用该算法吗?这个算法能扩展到7个条目吗?在C/C++中对7个整数排序最快的算法是什么?
发布于 2015-07-18 09:18:21
研究了std::sort在MSVC++2013的STL中的代码,对7个条目进行了插入排序。
一些评论建议使用排序网络。少数项目(最多32项)的排序网络可以生成这里。特别是,对于没有并行性的7项排序,最快的算法似乎是这。根据实验这里,最快的SWAP宏实现是:
#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项的排序-网络代码将是:
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);
} 发布于 2015-07-17 09:01:58
如果std::sort试图对小尺寸进行尽可能少的比较,这并不是标准的一部分。不同的实现可以做到这一点,但这将取决于您正在使用的库。
发布于 2015-07-17 09:01:58
算法依赖于实现。通常采用快速排序算法,即O(n log )。
https://stackoverflow.com/questions/31471951
复制相似问题