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

Question

这是我很久以前遇到的问题.我想我可能会问你的想法.假设我有一个非常小的数字列表(整数),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位处理器.

谢谢

Answer 1

对于像这样的小型数组,您应该考虑分类网络.正如您在该页面上看到的那样,插入排序可以表示为排序网络.但是,如果您事先知道阵列的大小,则可以设计出最佳网络.看看这个网站,它可以帮助您找到给定大小的阵列的最佳排序网络(尽管最优化只能保证16个大小我相信).比较器甚至可以在可以并行完成的操作中组合在一起.比较器基本上与你的s(x,y)函数相同,但是如果你真的希望它快,你不应该使用min和max,因为那时你需要做两倍的必要比较.

如果您需要这种排序算法来处理各种各样的大小,那么您应该像其他人建议的那样使用插入排序.

Answer 2

我看到你已经有一个使用5次比较的解决方案(假设s(i,j)比较两个数字一次,并且交换它们或不交换).如果你坚持基于比较的排序,那么你不能用少于5次的比较来做到这一点.

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

Answer 3

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

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

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