arrays - 3つの値を持つことができるオブジェクトを持つ配列を並べ替えます

Question

各オブジェクトが3つの値を持つことができるプロパティを持つようなオブジェクトを持つ配列があります。

次に、線形O（n）アルゴリズムと一定のメモリ使用量を使用してこの配列を並べ替える必要があります。

どうすればそれを実現できますか？

Dutch National Flagアルゴリズムに似ていますか？または、カウントソートを実行できますか？私が正しくない場合、他にどのような方法で進めることができますか？この質問は、実際に私の友人の1人にインタビューで尋ねられました。

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