algorithm - 最快的无条件排序算法

Question

我有一个函数，它可以获取两个元素并按升序返回它们:

void Sort2(int &a, int &b) { 
  if (a < b) return; 
  int t = a; 
  a = b; 
  b = t; 
}

如果不允许我使用额外的条件运算符，使用此函数对包含 N 个条目的数组进行排序的最快方法是什么？这意味着我的整个程序应该如下所示:

int main(){
  int a[N];
     // fill a array

  const int NS = ...; // number of comparison, depending on N.
  const int c[NS] = { {0,1}, {0,2}, ... }; // consequence of indices pairs generated depending on N.
  for( int i = 0; i < NS; i++ ) {
    Sort2(a[c[i][0]], a[c[i][1]]);
  }
     // sort is finished
  return 1;
}

大多数快速排序算法使用条件来决定要做什么。有 bubble sort当然可以，但是需要 M = N(N-1)/2 次比较。这不是最优的，例如，N = 4 需要 M = 6 比较，同时 4 个条目可以用 5 排序:

Sort2(a[0],a[1]);
Sort2(a[2],a[3]);
Sort2(a[1],a[3]);
Sort2(a[0],a[2]);
Sort2(a[1],a[2]);

---

Answer 1

标准方法称为 Bitonic Mergesort .它在并行化时非常高效，在未并行化时仅比传统算法效率稍低。 Bitonic mergesort 是一种特殊的更广泛的算法，称为“排序网络”；这在排序网络中是不寻常的，因为它的一些重新排序是按所需排序的相反顺序(尽管一旦算法完成，一切都是正确的顺序)。您可以使用 Sort2 为第一个参数传递一个比第二个参数更高的数组槽来做到这一点。