特定情况下最快的排序算法

Question

什么是针对大量（数万）由9个正双精度值组成的组进行单独排序的最快算法？因此，它必须快速地对可能重复的双精度值进行少量排序，多次执行。

这些值在[0..1]区间内。我不关心空间复杂度或稳定性，只关心速度。

- luvieere

---

你需要对每组9个值进行排序，然后将所有的9个值的组合合并在一起吗？还是只需要对每组9个值进行排序，然后让它们保持原样？ - Justin Peel

@Justin 就让他们吧。 - luvieere

@luvieere 好的，那么排序网络确实是正确的选择。 - Justin Peel

在哪种硬件上运行？SIMD和可能的GPU可用性会影响算法选择。 - Pete Kirkham

@Pete GPU确实支持像素着色器2.0，要排序的数据由每个像素的3 x 3邻域组成。 - luvieere

Answer 1

将每个组单独排序，使用归并排序可能是最容易实现且效果良好的。

使用排序网络可能是最快的解决方案： http://en.wikipedia.org/wiki/Sorting_network

- Tom Gullen

---

排序网络的好处在于，如果您了解数据的特性，例如，如果您知道元素3始终小于元素8，则可以添加一些非常快速的优化，从而节省大量处理时间。 - Tom Gullen

只是补充一下，我曾经有一个任务是在最短的时间内对7个整数进行排序，这个排序会被执行数十亿次，而迄今为止（我是说绝对的），最快的方法是使用排序网络。 - Tom Gullen

不要忘记计算排序网络的链接：http://pages.ripco.net/~jgamble/nw.html。表示需要27次比较来对9个值进行排序。 - Justin Peel

我想提醒大家，算法的效率取决于数据的输入方式。例如，如果数据已经排序好了，那么冒泡排序会比快速排序更快。如果数据没有排序，那么快速排序肯定比冒泡排序更快。因此，了解输入数据的情况应该有助于做出正确的决策。 - user347594

@johncatfish：随机评论？ - Matthieu M.

Answer 2

看起来你想要一种最节约循环的方式来排序9个值。由于值的数量有限，我会（如Kathy建议的）首先对前4个元素和后5个元素进行展开插入排序。然后将这两个组合并。

这是一个展开的4个元素插入排序：

if (u[1] < u[0]) swap(u[0], u[1]);
if (u[2] < u[0]) swap(u[0], u[2]);
if (u[3] < u[0]) swap(u[0], u[3]);

if (u[2] < u[1]) swap(u[1], u[2]);
if (u[3] < u[1]) swap(u[1], u[3]);

if (u[3] < u[2]) swap(u[2], u[3]);

这是一个合并循环。第一组4个元素在u中，第二组5个元素在v中。结果在r中。

i = j = k = 0;
while(i < 4 && j < 5){
  if (u[i] < v[j]) r[k++] = u[i++];
  else if (v[j] < u[i]) r[k++] = v[j++];
  else {
    r[k++] = u[i++];
    r[k++] = v[j++];
  }
}
while (i < 4) r[k++] = u[i++];
while (j < 5) r[k++] = v[j++];

- Mike Dunlavey

Answer 3

这是一个好问题，因为它涉及“对9个元素的数组进行排序的最快方法”，而大多数排序方法之间的比较和分析都涉及大的N。我假设“组”已经明确定义，并且在这里没有实际作用。

您可能需要对一些候选者进行基准测试，因为许多因素（本地性）在这里发挥作用。

无论如何，将其并行化听起来像个好主意。如果您使用.NET4，则使用Parallel.For()。

- H H

Answer 4

我认为你需要尝试一些例子来看哪种方法最好，因为你有一个不寻常的条件集。我猜最好的方法之一是：

• 排序网络
• 插入排序
• 快速排序（一级 - 插入排序在下面）
• 归并排序

考虑到双精度数字相对较长，我怀疑使用基数排序效果不会更好，但请随意添加。

值得一提的是，Java在对双精度数进行排序时，直到要排序的项目数量降至7以下才使用插入排序。第三个选项模仿了这个解决方案。

此外，你的整体问题是令人尴尬的并行，因此在可能的情况下要利用并行性。该问题看起来太小，不适合分布式解决方案（网络传输所花费的时间比节省的时间还多），但如果正确设置，你的问题可以非常有效地利用多个核心。

- Kathy Van Stone