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}and 的任何排列{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 是当前较少元素的数量，z 是等于元素的数量

但是如果我让数组中的每个元素都等于那里，它就不起作用（大小-（++ z））低于 0

Answer 1

这就是所谓的荷兰国旗问题，以三条纹荷兰国旗命名。（它由荷兰人 EW Dijkstra 命名。）它类似于partition实现快速排序所需的函数，但在快速排序的大多数解释中，都提供了双向分区算法，而在这里我们寻找的是三向分区。经典的快速排序分区算法将向量分为两部分，一部分由不大于主元的元素组成，另一部分由严格大于的元素组成。[见注1]

维基百科文章提供了 Dijkstra 解决方案的伪代码，它（与快速排序讨论中通常介绍的经典分区算法不同）通过向量从左向右移动：

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. 维基百科 Quicksort 文章中介绍的 Hoare 算法不会重新排列与主元相等的值，因此它们最终会出现在两个分区中。因此，它不是真正的分区算法。