探How 社区

开发者发布了一个名为 blqs 的 C++ 快速排序头文件实现，作者声称其速度快于 std::sort。该实现采用 xorshift 随机数生成器选取枢轴，并对 2 至 4 个元素的小数组做专门的排序展开优化，同时设置了 SMALLPART、SWSZ、UNROLL 等常量参数。原文未给出具体基准测试数据。

以下正文由 AI 翻译自 Hacker News 最新（原文版权归原站所有），可能存在偏差，重要内容请以原文为准。

#ifndef BLQS_H #define BLQS_H #include <cstddef> #include <cstdint> #include <cstring> #include <functional> #include <utility> #ifndef BLQS_RAND #define BLQS_RAND #include <random> static thread_local uint64_t blqs_seed; static inline unsigned blqs_rand(void) { if (!blqs_seed) { std::random_device rd; blqs_seed = ((uintptr_t)&blqs_seed) ^ (((uint64_t)rd() << 32) | (uint64_t)rd()); if (!blqs_seed) blqs_seed = 1; uint64_t x = blqs_seed; x ^= x << 13; x ^= x >> 7; x ^= x << 17; blqs_seed = x; return (unsigned)x; #endif namespace blqs { constexpr int SMALLPART = 1024; constexpr int SWSZ = 512; constexpr int UNROLL = 16; template<typename T, typename Compare> static inline void sort2(T& a, T& b, Compare comp) { T x = a; T y = b; bool m = comp(x, y); a = m ? x : y; b = m ? y : x; template<typename T, typename Compare> static inline void sort3(T& a, T& b, T& c, Compare comp) { sort2(a, b, comp); sort2(b, c, comp); sort2(a, b, comp); template<typename T, typename Compare> static inline void sort4(T& a, T& b, T& c, T& d, Compare comp) { sort2(a, b, comp); sort2(c, d, comp); sort2(a, c, comp); sort2(b, d, comp); sort2(b, c, comp); template<typename T, typename Compare> static inline void sort5(T& a, T& b, T& c, T& d, T& e, Compare comp) { sort2(b, c, comp); sort2(d, e, comp); sort2(b, d, comp); sort2(a, c, comp); sort2(a, d, comp); sort2(c, e, comp); sort2(a, b, comp); sort2(c, d, comp); sort2(b, c, comp); template<typename T, typename Compare> static inline void sort6(T& a, T& b, T& c, T& d, T& e, T& f, Compare comp) { sort2(a, b, comp); sort2(c, d, comp); sort2(e, f, comp); sort2(a, c, comp); sort2(b, d, comp); sort2(e, f, comp); sort2(a, e, comp); sort2(b, f, comp); sort2(c, e, comp); sort2(d, f, comp); sort2(b, c, comp); sort2(d, e, comp); sort2(c, d, comp); template<typename T, typename Compare> static inline void sort7(T& a, T& b, T& c, T& d, T& e, T& f, T& g, Compare comp) { sort2(a, g, comp); sort2(c, d, comp); sort2(e, f, comp); sort2(a, c, comp); sort2(b, e, comp); sort2(d, g, comp); sort2(a, b, comp); sort2(c, f, comp); sort2(d, e, comp); sort2(b, c, comp); sort2(e, g, comp); sort2(c, d, comp); sort2(e, f, comp); sort2(b, c, comp); sort2(d, e, comp); sort2(f, g, comp); template<typename T, typename Compare> static inline void sort8(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, Compare comp) { sort2(a,b,comp); sort2(c,d,comp); sort2(e,f,comp); sort2(g,h,comp); sort2(a,c,comp); sort2(b,d,comp); sort2(e,g,comp); sort2(f,h,comp); sort2(b,c,comp); sort2(f,g,comp); sort2(a,e,comp); sort2(b,f,comp); sort2(c,g,comp); sort2(d,h,comp); sort2(c,e,comp); sort2(d,f,comp); sort2(b,c,comp); sort2(d,e,comp); sort2(f,g,comp); template<typename T, typename Compare> static inline void sort9(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, T& i, Compare comp) { sort2(a,d,comp); sort2(b,h,comp); sort2(c,f,comp); sort2(e,i,comp); sort2(a,h,comp); sort2(c,e,comp); sort2(d,i,comp); sort2(f,g,comp); sort2(a,c,comp); sort2(b,d,comp); sort2(e,f,comp); sort2(h,i,comp); sort2(b,e,comp); sort2(d,g,comp); sort2(f,h,comp); sort2(a,b,comp); sort2(c,e,comp); sort2(d,f,comp); sort2(g,i,comp); sort2(c,d,comp); sort2(e,f,comp); sort2(g,h,comp); sort2(b,c,comp); sort2(d,e,comp); sort2(f,g,comp); template<typename T, typename Compare> static inline void sort10(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, T& i, T& j, Compare comp) { sort2(a,b,comp); sort2(c,f,comp); sort2(d,g,comp); sort2(e,h,comp); sort2(i,j,comp); sort2(a,g,comp); sort2(b,i,comp); sort2(c,e,comp); sort2(d,j,comp); sort2(f,h,comp); sort2(a,c,comp); sort2(b,d,comp); sort2(e,f,comp); sort2(g,i,comp); sort2(h,j,comp); sort2(a,b,comp); sort2(c,h,comp); sort2(d,f,comp); sort2(e,g,comp); sort2(i,j,comp); sort2(b,c,comp); sort2(d,e,comp); sort2(f,g,comp); sort2(h,i,comp); sort2(b,d,comp); sort2(c,e,comp); sort2(f,h,comp); sort2(g,i,comp); sort2(c,d,comp); sort2(e,f,comp); sort2(g,h,comp); template<typename T, typename Compare> static inline void sort11(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, T& i, T& j, T& k, Compare comp) { sort2(a,j,comp); sort2(b,g,comp); sort2(c,e,comp); sort2(d,h,comp); sort2(f,i,comp); sort2(a,b,comp); sort2(d,f,comp); sort2(e,k,comp); sort2(g,j,comp); sort2(h,i,comp); sort2(b,d,comp); sort2(c,f,comp); sort2(e,h,comp); sort2(i,k,comp); sort2(a,e,comp); sort2(b,c,comp); sort2(d,h,comp); sort2(f,j,comp); sort2(g,i,comp); sort2(a,b,comp); sort2(c,g,comp); sort2(e,f,comp); sort2(h,i,comp); sort2(j,k,comp); sort2(c,e,comp); sort2(d,g,comp); sort2(f,h,comp); sort2(i,j,comp); sort2(b,c,comp); sort2(d,e,comp); sort2(f,g,comp); sort2(h,i,comp); sort2(c,d,comp); sort2(e,f,comp); sort2(g,h,comp); template<typename T, typename Compare> static inline void sort12(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, T& i, T& j, T& k, T& l, Compare comp) { sort2(a,i,comp); sort2(b,h,comp); sort2(c,g,comp); sort2(d,l,comp); sort2(e,k,comp); sort2(f,j,comp); sort2(a,c,comp); sort2(b,e,comp); sort2(d,f,comp); sort2(g,i,comp); sort2(h,k,comp); sort2(j,l,comp); sort2(a,b,comp); sort2(c,j,comp); sort2(e,h,comp); sort2(f,g,comp); sort2(k,l,comp); sort2(b,d,comp); sort2(c,h,comp); sort2(e,j,comp); sort2(i,k,comp); sort2(a,b,comp); sort2(c,d,comp); sort2(e,f,comp); sort2(g,h,comp); sort2(i,j,comp); sort2(k,l,comp); sort2(b,c,comp); sort2(d,f,comp); sort2(g,i,comp); sort2(j,k,comp); sort2(c,e,comp); sort2(d,g,comp); sort2(f,i,comp); sort2(h,j,comp); sort2(b,c,comp); sort2(d,e,comp); sort2(f,g,comp); sort2(h,i,comp); sort2(j,k,comp); template<typename T, typename Compare> static inline void sort13(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, T& i, T& j, T& k, T& l, T& m, Compare comp) { sort2(a,m,comp); sort2(b,k,comp); sort2(c,j,comp); sort2(d,h,comp); sort2(f,l,comp); sort2(g,i,comp); sort2(b,g,comp); sort2(c,d,comp); sort2(e,l,comp); sort2(h,j,comp); sort2(i,k,comp); sort2(a,e,comp); sort2(b,c,comp); sort2(d,g,comp); sort2(h,i,comp); sort2(j,k,comp); sort2(l,m,comp);

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）

正文由探How 从来源站点 RSS 同步，内容未经改写；遇到排版缺失或需要图片、视频时请以原文为准。

开发者发布 C++ 快速排序实现 blqs，声称快于 std::sort