44

这是我很久以前遇到的问题。我想我可以问问你的想法。假设我有非常小的数字（整数）列表，4 或 8 个元素，需要快速排序。什么是最好的方法/算法？

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

// 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 位处理器。

谢谢

4

6 回答 6

38

对于像这样的小数组，您可能应该研究排序网络。正如您在该页面上看到的那样，插入排序可以表示为排序网络。但是，如果您事先知道数组的大小，则可以设计一个最佳网络。看看这个站点，它可以帮助您找到给定数组大小的最佳排序网络（尽管我相信最佳只能保证最大 16 的大小）。比较器甚至在可以并行完成的操作中组合在一起。比较器本质上与您的 s(x,y) 函数相同，但如果您真的希望它更快，您不应该使用 min 和 max，因为这样您需要进行两倍的比较次数。

如果您需要这种排序算法来处理各种大小，那么您可能应该按照其他人的建议使用插入排序。

于 2010-05-01T03:48:24.723 回答
7

我看到您已经有了一个使用 5 次比较的解决方案（假设 s(i,j) 比较这两个数字一次，并且交换它们或不交换它们）。如果您坚持基于比较的排序，那么您不能进行少于 5 次的比较。

这可以证明，因为有 4 个！= 24 种可能的方式来订购 4 个号码。每次比较只能将可能性减半，因此通过 4 次比较，您只能区分 2^4 = 16 个可能的排序。

于 2010-05-01T03:46:53.547 回答
7

要对少量数字进行排序，您需要一个简单的算法，因为复杂性会增加更多开销。

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

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 行，所以虽然它仍然是最有效的，但它的代码很多，你必须编写一个程序来编写代码以使其正确。

于 2010-05-01T03:57:38.260 回答
4

插入排序被认为最适合小型数组。请参阅小型数组（小于 32 或 64 个元素）的快速稳定排序

于 2010-05-01T03:33:20.203 回答
3

对于这么小的数据集，您希望算法尽可能简单。一个基本的插入排序很可能会像你想要的那样做。

需要更多地了解正在运行的系统，每秒需要进行多少次这种排序，等等......但小范围的一般规则是保持简单。快速排序之类的东西没有好处。

于 2010-05-01T03:19:54.487 回答
3

排序网络可以很容易地在 SIMD 中实现，尽管它在 N = 16 左右开始变得丑陋。对于 N = 4 或 N = 8，尽管这将是一个不错的选择。理想情况下，您需要同时对大量小数据集进行排序，即，如果您要对 8 位值进行排序，那么您至少需要对 16 个数据集进行排序——在SIMD 向量中做这种事情要困难得多。

另请参阅：最快的固定长度 6 int 数组

于 2010-05-01T06:57:07.257 回答