C 最佳函数，用于在小于、等于和大于某个值的元素上获取拆分数组

Question

我正在用 C 编程。什么是最好的方法(我的意思是在线性时间内)将数组吐到小于、等于和大于某个值 x 的元素上。

例如如果我有数组

{1, 4, 6, 7, 13, 1, 7, 3, 5, 11}

和x = 7那么应该是

{1, 4, 6, 1, 3, 5, 7, 7, 13, 11 } 

我不想对元素进行排序，因为我需要更有效的方法。当然，在此示例中，in 可以是 {1, 4, 6, 1, 3, 5} 和 {13, 11} 的任意排列。

我的想法:小于或大于数组中的某个元素......在这个例子中它是 7。

我的职能是:

int x = 7;
int u =0, z = 0;
for(int i=0; i<size-1; i++)  // size - 1 because the last element will be choosen value
{
  if(A[i] == x)
    swap(A[i], A[u]);
  else if(A[i] == x)
  {
     swap(A[i], A[n-(++z)]);
     continue;
  }
  i++
 }

for(int i = 0; i<z; i++)
   swap(A[u+i],A[size-(++z)];

其中u为当前less元素个数，z为equals元素个数

但是如果我让数组中的每个元素都等于那里它不起作用 (size-(++z)) 小于 0

Answer 1

这就是所谓的Dutch national flag problem ，以三条纹荷兰国旗命名。 (它是由荷兰人 E.W. Dijkstra 命名的。)它类似于实现快速排序所需的 partition 函数，但在大多数对快速排序的解释中，都介绍了双向分区算法，而这里我们是寻找三向分区。经典的快速排序分区算法将 vector 分为两部分，一部分由不大于主元的元素组成，另一部分由严格大于主元的元素组成。 [见注1]

维基百科文章提供了 Dijkstra 解决方案的伪代码，该解决方案(不同于通常在讨论快速排序时出现的经典分区算法)从左到右移动 vector :

void dutchflag(int* v, size_t n, int x) {
  for (size_t lo = 0, hi = n, j = 0; j < hi; ) {
    if (v[j] < x) {
      swap(v, lo, j); ++lo; ++j;
    } else if (v[j] > x) {
      --hi; swap(v, j, hi);
    } else {
      ++j;
    }
  }

还有另一种算法，由 Bentley 和 McIlroy 于 1993 年发现并发表在他们的论文中 "Engineering a Sort Function"其中有一些很好的图表说明了各种分区函数的工作原理，以及一些关于为什么分区算法很重要的讨论。 Bentley & McIlroy 算法在枢轴元素在列表中不常出现的情况下更好，而 Dijkstra 算法在它经常出现时更好，因此您必须了解有关数据的一些信息才能在它们之间进行选择。我相信大多数现代快速排序算法都使用 Bentley & McIlroy，因为常见的情况是要排序的数组几乎没有重复项。

注意事项

1. Wikipedia Quicksort article 中介绍的 Hoare 算法, 不会重新排列等于主元的值，因此它们最终会出现在两个分区中。因此，它不是真正的分区算法。