3

我有一个函数，它可以接受两个元素并以升序返回它们：

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]);
4

2 回答 2

6

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

于 2013-10-23T11:35:43.500 回答
0

对于N2 的幂，您可以通过使用“合并排序”类型的方法来概括您使用的方法：您分别对前半部分和后半部分进行排序，然后使用一些比较合并它们。

例如，考虑一个大小为 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

为了方便ns 不是 2 的幂，重要的是在奇数长度数组上执行合并步骤。最简单的策略似乎是比较两个子数组的最小元素（产生最小元素），然后继续数组的其余部分（现在具有偶数长度）。

如果我们写g(k) = k(k+1)/2，我们现在可以有一种写递归公式的简短方法（我使用2kand2k+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)
于 2013-10-23T10:20:32.167 回答