arrays - 对具有可以具有 3 个值的对象的数组进行排序

Question

我们有一个包含对象的数组，每个对象都有一个可以有 3 个值的属性。

现在我们需要使用线性 O(n) 算法和恒定的内存使用对这个数组进行排序。

我们该怎么做呢？

是不是类似于荷兰国旗算法？或者我们可以做计数排序吗？如果我不正确，那么我们还有什么其他方法可以继续？这个问题实际上是在一次采访中向我的一位朋友提出的。

Answer 1

这是数组元素的重新排列问题。荷兰国旗算法应该在这里做

void partition(int data[], int size, int low, int high) {
  int p = -1;
  int q = size;
  for (int i = 0; i < q;) {
    if (data[i] < low) {
      swap(data[i], data[++p]);
      ++i;
    } else if (data[i] >= high) {
      swap(data[i], data[--q]);
    } else {
      ++i;
    }
  }
}