非常小的列表快速排序算法实现

Question

很久以前我遇到了这个问题，我想向您请教一下您的想法。
假设我有非常小的数字列表（整数），4或8个元素，需要快速排序。
哪种方法/算法是最好的呢？

我的方法是使用max/min函数（10个函数来对4个数字进行排序，没有分支，如果我没记错的话）。

// s(i,j) == max(i,j), min(i,j)
i,j = s(i,j)
k,l = s(k,l)
i,k = s(i,k) // i on top
j,l = s(j,l) // l on bottom
j,k = s(j,k)

我猜我的问题更关注于实现，而不是算法类型。

到这一步，它变成了某种硬件相关的问题，所以让我们假设是带有SSE3的Intel 64位处理器。

谢谢。

- Anycorn

---

我基本上是问了同样的问题，但使用了更具体的上下文（C实现、6个整数数组），并使用循环计数寄存器来评估性能。您可以在这里查看结果：https://dev59.com/8-o6XIcBkEYKwwoYTy8d - kriss

相关：固定长度为6的整数数组的最快排序方法 - Janus Troelsen

Answer 1

对于这样的小数组，您应该考虑排序网络。正如您在该页面上看到的那样，插入排序可以表示为排序网络。然而，如果您事先知道数组的大小，可以设计出最优网络。请查看此网站，它可以帮助您找到给定数组大小的最优排序网络（尽管最优只保证达到16个大小）。比较器甚至被分组成可以并行执行的操作。比较器本质上与您的s(x,y)函数相同，但如果您真的希望它快速运行，就不应该使用min和max，因为这样做会多进行两倍的比较。

如果您需要此排序算法适用于各种大小的数组，则应像其他人建议的那样选择插入排序。

- Justin Peel

---

所以，这里是一个古老的答案，但当我第一次阅读这个答案时，我误解了“最优排序网络”的概念，因此需要澄清的是：最优排序网络实际上并不使用最少数量的比较器！排序网络受限于始终使用相同的固定比较器排列；即，在决定要比较哪些元素时没有分支。这对于硬件实现和GPGU非常有用，但这意味着即使在相当小的数组大小（我相信从5开始），您也将需要比严格必要的更多的比较。 - Eamon Nerbonne

您提供的查找最佳排序网络的网站对我不起作用，但我找到了这个网站http://users.telenet.be/bertdobbelaere/SorterHunter/sorting_networks.html。 - M.J. Rayburn

Answer 2

如果要排序少量数字，您需要一个简单的算法，因为复杂性会增加额外的开销。

例如，对于四个项目进行排序的最有效方法是将排序算法展开为线性比较，从而消除所有开销：

function sort(i,j,k,l) {
  if (i < j) {
    if (j < k) {
      if (k < l) return [i,j,k,l];
      if (j < l) return [i,j,l,k];
      if (i < l) return [i,l,j,k];
      return [l,i,j,k];
    } else if (i < k) {
      if (j < l) return [i,k,j,l];
      if (k < l) return [i,k,l,j];
      if (i < l) return [i,l,k,j];
      return [l,i,k,j];
    } else {
      if (j < l) return [k,i,j,l];
      if (i < l) return [k,i,l,j];
      if (k < l) return [k,l,i,j];
      return [l,k,i,j];
    }
  } else {
    if (i < k) {
      if (k < l) return [j,i,k,l];
      if (i < l) return [j,i,l,k];
      if (j < l) return [j,l,i,k];
      return [l,j,i,k];
    } else if (j < k) {
      if (i < l) return [j,k,i,l];
      if (k < l) return [j,k,l,i];
      if (j < l) return [j,l,k,i];
      return [l,j,k,i];
    } else {
      if (i < l) return [k,j,i,l];
      if (j < l) return [k,j,l,i];
      if (k < l) return [k,l,j,i];
      return [l,k,j,i];
    }
  }
}

然而，每增加一个项目，代码量就会增加很多。添加第五个项目后，代码大约增加了四倍。在八个项目时，它大约有30000行的代码，因此尽管这是最有效的方法，但需要编写一个编写正确代码的程序。

- Guffa

---

原始程序使用了类似这样的东西，但性能相当低，我猜是由于分支问题。 - Anycorn

@aaa：我明白了...嗯，为了消除所有的分支，你可以进行所有必要的比较，并将结果合并成一个键，然后使用它从预先计算好的所有可能结果的字典中获取索引数组。 - Guffa

这个算法不错但并非最优的：它最多可以执行6次比较，而最优算法不应超过5次。 - Morwenn

Answer 3

我看到你已经有一个使用5次比较的解决方案了（假设s(i,j)只比较两个数字一次，然后要么交换它们，要么不交换）。如果你坚持使用基于比较的排序方法，那么你不能用少于5次比较来完成。

这可以被证明，因为有4! = 24种可能的方式来排列4个数字。每次比较只能将可能性减半，所以通过4次比较，你只能区分2^4 = 16种可能的排序方式。

- mathmike

Answer 4

插入排序被认为是最适合小型数组的排序算法。请参见Fast stable sort for small arrays (under 32 or 64 elements)。

- mathmike

---

嗨，我更感兴趣的是实现方法。 - Anycorn

我不确定你所说的“实现方法”是什么意思。你是在寻找关于汇编代码的讨论吗？ - mathmike

不是非常低，但需要显示分支/指令。 - Anycorn

我在C++中为嵌入式平台实现了插入排序。结果在所有情况下编译后的二进制大小都是最优的，可能是因为优化器能够将排序展开成有益的排序网络（当您在编译时拥有已知大小的列表时）。 - Emil Vikström

Answer 5

对于这样一个小数据集，你需要尽可能简单的算法。很可能，基本的插入排序就能满足你的需求。

需要了解更多关于这个系统运行情况的信息，比如每秒需要进行多少次排序等等...但是在小型排序中，通常的规则是保持简单。快速排序之类的算法并没有好处。

- bwawok

---

你好，我写了一些澄清说明。我更多地寻找实现的想法。 - Anycorn

Answer 6

排序网络可以很容易地在SIMD中实现，尽管在N = 16左右时开始变得丑陋。但对于N = 4或N = 8来说，这将是一个不错的选择。理想情况下，您需要大量小数据集同时进行排序，即如果您正在排序8位值，则至少希望有16个数据集进行排序 - 在跨SIMD向量进行此类操作要困难得多。

另请参见：固定长度为6的int数组的最快排序

- Paul R