6

C# 5.0の次のコードを考えてみましょう。289:

int[] numbers = { 1, 2, 3, 4, 5 };
Array.Sort (numbers, (x, y) => x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1);

結果が得られ{3, 5, 1, 2, 4}ます。

これを紙で試してみたところ、 {1, 3, 5, 2, 4}.

なぜコンピュータソーティングは を与えたの3 > 5 > 1ですか?

4

5 に答える 5

6

ほとんどの場合、トピックはSort要素の順序が等しいことを保証しないという事実に関するものです。等しい要素の元の順序を保持する安定した並べ替えアルゴリズムとは異なり、「不安定な並べ替え」はそれらを入れ替える可能性があります。通常、手動でソートする場合は、「安定したソート」バージョンを実行します。

Array.Sort :

この実装は、不安定な並べ替えを実行します。つまり、2 つの要素が等しい場合、それらの順序は保持されない可能性があります。対照的に、安定した並べ替えは、等しい要素の順序を保持します。

サンプルで使用されている並べ替え関数は、1 == 3, 1 == 5他の番号と比較して正しい順序である限り、この番号を任意の方法で並べ替えることができる不安定な並べ替えを作成します: 1,3,5 (安定 - ソースと同じ順序) または任意のシーケンス 3 ,1,5 (不安定なソート)。

つまり、OrderByは「安定した並べ替え」を実装し、同じ比較関数を使用して次のサンプルで結果を確認できます。

void Main()
{
    int[] numbers = { 1, 2, 3, 4, 5 };
    var result = numbers.OrderBy(x=> x, new MyComparer()));
      // 1, 3, 5, 2, 4
}

public class MyComparer : IComparer<int>  
{
    public int Compare( int x, int y)
    {
      return  x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1;
    }
}
于 2013-05-02T06:44:32.797 に答える
3

Array.Sortは指定しますが

パーティション サイズが 16 要素未満の場合、挿入ソート アルゴリズムが使用されます。

この挿入ソートをどのように行うか、または使用する挿入ソートのフレーバーを指定しません。すでに述べたように、さらに指定します

この実装は不安定な並べ替えを実行します

その結果、Array.Sort返された後の要素の順序について保証される唯一のことは、それらがソートされることです。これは に当てはまります{3, 5, 1, 2, 4}。

で使用されるアルゴリズムが次のArray.Sortようなことを行うことさえ許可されることを考慮してください (疑似コード):

if sequence = {1, 2, 3, 4, 5} then
    sequence := {3, 5, 1, 2, 4}
end if
Sort(sequence);

もちろん、これは実装定義の動作であり、別のバージョンの .NET フレームワークでは変更される可能性があります。

コードを次のように変更する

Array.Sort(numbers, (x, y) =>
    {
        Console.WriteLine(x + ", " + y);
        return x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1;
    });

によって行われる比較が得られますArray.Sort:

1, 3
1, 5
3, 5
1, 3
3, 5
2, 3
3, 4
3, 3
5, 3
5, 3
5, 5
5, 3
2, 4
2, 1
4, 2
1, 4
4, 4
4, 2
1, 2
1, 2
1, 1
1, 2
1, 1

そして、これは紙の上で挿入ソートを行う方法ではない可能性が非常に高いです。

ポイントは、シーケンスをソートすることを約束しますが、これを行う方法Array.Sortを約束しません。

于 2013-05-02T07:22:55.610 に答える
1

ここで、あなたがどのように順番に得たのかを並べ替えるわけではありません

これを試して：

Array.Sort(numbers, (x, y) => x % 2 == y % 2 ? x < y ? 1 : -1 : x % 2 == 1 ? -1 : 1);
于 2013-05-02T07:07:54.847 に答える