固定长度为6的整型数组中最快的排序方法
回答另一个Stack Overflow的问题（this one），我偶然发现了一个有趣的子问题。如何最快地对包含6个整数的数组进行排序？ 由于这个问题非常低级： 我们不能假定库是可用的（而且调用本身也有成本），只能使用纯C。 为了避免清空指令流水线（这是一种非常高的成本），我们应该尽可能...
如何最快地对10个32位数字进行排序？
我正在解决一个问题，涉及快速排序10个数字（int32）。我的应用程序需要尽可能快地对10个数字进行数百万次的排序。我正在对数十亿个元素的数据集进行抽样，每次需要从中选择10个数字（简化），并对它们进行排序（并从排序后的10个元素列表中得出结论）。 目前我正在使用插入排序，但我想我可以为我的特...
非常小的列表快速排序算法实现
很久以前我遇到了这个问题，我想向您请教一下您的想法。 假设我有非常小的数字列表（整数），4或8个元素，需要快速排序。 哪种方法/算法是最好的呢？ 我的方法是使用max/min函数（10个函数来对4个数字进行排序，没有分支，如果我没记错的话）。// s(i,j) == max(i,j), mi...
使用比较器网络对固定长度数组进行快速排序
我有一些性能关键的代码，涉及在C++中对一个非常短的、固定长度的数组进行排序，该数组在大约3到10个元素之间（参数在编译时更改）。 我想到了一种专门针对每个可能的输入大小的静态排序网络，可能是做这件事的一种非常有效的方式：我们执行所有必要的比较来确定我们所处的情况，然后执行最优数量的交换来对...
一个排序网络如何能够击败通用的排序算法？
关于如何快速排序固定长度为6的int数组，我不完全理解这个排序网络是如何比插入排序这样的算法更快的。 从该问题可以看出，下面是完成排序所需的CPU周期数的比较： Linux 32 bits, gcc 4.4.1, Intel Core 2 Quad Q8300, -O2 ...
针对小规模n值的标准排序网络
我正在寻找一个五元素排序网络实现，但由于我在SO上没有找到好的参考资料，因此我想请教所有小值n的排序网络，至少从n=3到n=6，但更高的值也很好。一个好的答案应该至少将它们列为"swap"（2个元素的排序）操作的序列，但也可以看到以较低阶排序网络为基础的递归分解。 对于我的应用程序，我实际上...
最优的9元素排序网络如何转化为最优的中位数排序网络？
我正在研究基于两个输入的最小/最大操作的九个元素的排序和中位数选择网络。Knuth，《TAOCP Vol. 3》，第2版指出（第226页），一个九元素排序网络至少需要25次比较，这相当于相同数量的SWAP()原语或50个最小/最大操作。显然，可以通过消除冗余操作将排序网络转换为中位数选择网络。...
如何修复这个非递归的奇偶归并排序算法？
我正在寻找非递归奇偶合并排序算法，并找到了两个来源： Sedgewick R.的一本书 这个SO问题 这两种算法都是相同但错误的。生成的排序网络不是一个奇偶合并排序网络。 这是一个具有32个输入的生成网络的图像。在两条水平线之间的垂直线表示比较值a[x]和a[y]，如果大于则交换数组...
不同于2^n大小的最优Batcher奇偶合并网络
最近，我一直在尝试使用最少的比较-交换单元（按大小而非深度最优）实现大小为32的排序网络。目前，我已经能够使用以下资源生成我的网络： 0到16个排序网络：Perl的Algorithm::Networksort模块，使用“Best”算法。不幸的是，它只提供了已知的最佳网络，直到大小为16。 ...
在少量元素被修改后重新排序向量
如果我们有一个大小为N的向量，之前已经排序好了，现在要用任意值替换最多M个元素（其中M远小于N），是否有一种简单的方法可以以更低的成本重新进行排序（即生成深度较小的排序网络）而不是完全排序？ 例如，如果N=10，M=2，则输入可能如下： 10 20 30 40 999 60 70 80 9...