安定した2値配列の並べ替えですか？

私はオブジェクトの配列を持っています。オブジェクトには、配列をソートするためのキー（真であるすべてのオブジェクトがすべてのオブジェクトの前に来る）のキーとして使用するブール値がありますが、それ以外の場合は同じ順序で残ります。安定した2値配列の並べ替えですか？

シンプルで、その場でのO（n）解決策はありますか？多分radix-sortのいくつかの亜種ですか？

出典

2009-04-02 BCS

もう一つの非常に似た質問があります。 http://stackoverflow.com/questions/682171/arrange-0s-1s-in-a-array – sharptooth

しかし、その半分の要素が1であり、半分が0であることが与えられていることで、少しのスペースや時間の要件を減らすことができます。 – MahlerFive

これは妥当です。 – sharptooth

マージソート。 O（n log n）である。

出典

2009-04-02 06:18:44 leppie

これは、O（n）でなくてはならない。 – MartinStettner

このトピックの説明は、hereを参照してください。基本的には、追加の領域が必要なO（n） - ソリューションまたはO（n log n）のインプレースソリューションを持つことができます。

出典

2009-04-02 06:24:38 MartinStettner

Hmm。リンクされたリストでは、実行可能でなければなりません。最初の「false」エントリを検索し、それを「挿入場所」として保持します。（「偽」のエントリがない場合は、とにかく完了しています:)次に、挿入位置の前にいて "false"エントリを見つけた場合、または挿入位置の後ろにある場合はリスト全体を繰り返し処理します。「真の」エントリを見つけて、それを「挿入場所」の直前に移動します。これまでのところ、O(n)です。

アレイをO(n)のリンクリストに変換することができ、の後ろにあるをO(n)の配列にコピーすることができます。だから、それはの複雑さの点ではという意味ではうまくいくと思いますが、それはインプレースではありません。私はそれがインプレースで行うことができるかどうかについて考えてみましょう...

出典

2009-04-02 06:33:30

安定した2値配列の並べ替えですか？

答えて

関連する問題