最快的无条件排序算法

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;
}

大多数快速排序算法使用条件来决定要做什么。当然有冒泡排序，但它需要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]);

---

- klm123

---

不使用比较运算符是什么意思？你使用的任何循环都应该有终止条件的比较运算符。你是指元素之间的比较不允许吗？ - Abhishek Bansal

Abhishek，你可以这样重新表述。同时，你可以说N是已知的，循环也被禁止了（就像N=5的例子一样）。 - klm123

阅读有关排序网络的内容。http://en.wikipedia.org/wiki/Sorting_network - zch

Sort2()里的那个 if 看起来对我来说很有条件呢;-) - Mateusz Dymczyk

@zch 如果不是条件运算符，那么"comparator"是什么？ - Ross Patterson

Answer 1

标准方法被称为比特位排序算法。当并行化时，它非常高效，而且在未并行化时仅比传统算法稍微低效一些。比特位排序是一类更广泛的算法中的特殊类型，称为“排序网络”；它不同于其他排序网络的地方在于，它的一些重新排序按照所需排序的相反顺序进行（不过一旦算法完成，所有内容都按正确顺序排列）。您可以通过将第一个参数传递给更高的数组槽来使用Sort2进行此操作。

- Sneftel

Answer 2

对于2的幂次方N，您可以推广您使用的方法，采用“归并排序”式的方法：将前半部分和后半部分分别排序，然后使用几个比较将它们合并。

例如，考虑一个大小为8的数组。假设通过递归应用此方法，前一半已经排序，后一半也已经排序：

A B C D P Q R S

在第一轮中，您将进行1对1、2对2等的比较：

---------
|       |
| ---------
| |     | |
A B C D P Q R S
    | |     | |
    | ---------
    |       |
    ---------

在这一轮之后，第一个和最后一个元素已经处于正确的位置，因此您需要为内部的6个元素重复此过程（我保持元素名称不变，因为不知道它们最终会停留在哪里）：

  -------
  |     |
  | -------
  | |   | |
A B C D P Q R S
      |     |
      -------

在下一轮中，将比较内部的4个元素，在最后一轮中比较内部的2个元素。

设f(n)为对长度为n的数组进行排序所需的比较次数（其中n是2的幂，暂时如此）。显然，由1个元素组成的数组已经排序：

f(1) = 0

对于更长的数组，您首先需要对两半进行排序，然后执行上述过程。 对于 n=8，这需要 4+3+2+1 = (n/2)(n/2+1)/2 次比较。 因此，一般而言：

f(n) = 2 f(n/2) + (n/2)(n/2+1)/2

请注意，对于 n=4 的情况，这确实给出了：

f(4) = 2 f(2) + 2*3/2
     = 2 * (2 f(1) + 1*2/2) + 3
     = 5

---

为了方便处理不是2的幂的n个元素，重要的是在奇数长度的数组上进行合并步骤。最简单的策略似乎是比较两个子数组的最小元素（得到最小元素），然后继续处理剩下的数组（此时长度为偶数）。

如果我们写成g(k) = k(k+1)/2，我们现在可以用一个简短的方式来表示递归公式（我使用2k和2k+1来区分偶数和奇数）：

f(1) = 0
f(2k) = 2 f(k) + g(k)
f(2k+1) = f(k+1) + f(k) + 1 + g(k)

---

以下是一些处理此问题的伪代码：

function sort(A, start, length) {
    if (length == 1) {
        // do nothing
    } else if (length is even) {
        sort(A, start, length/2)
        sort(A, start+length/2, length/2)
        merge(A, start, length)
    } else if (length is odd) {
        sort(A, start, length/2+1)
        sort(A, start+length/2+1, length/2)
        Sort2(A[start], A[start+length/2+1])
        merge(A, start+1, length-1)            
    }
}

function merge(A, start, length) {
    if (length > 0) {
        for (i = 0; i < length/2; i++)
            Sort2(A[i], A[i]+length/2)
        merge(A, start+1, length-2)
    }
}

你可以通过以下方式在数组上运行它：

sort(A, 0, A.length)

- Vincent van der Weele

---

这个算法的时间复杂度是O(n^2)。虽然可行，但现有更简单和更快的方法。排序网络在单调合并方面表现不佳，因为它们之间的关联已经预定义了。 - Sneftel