-8

一般的なリストがあるとしましょう。

IList<T> list;

アイテムを所定の位置に並べ替える必要がありますがSort、ほとんどのコレクションには .NET メソッドがないため、.NET メソッドは使用できません。どのような種類になるか事前にわからないので、どのように並べ替えればよいですか？

public void Sort(IList<T> list) {
}
4

4 に答える 4

2

リスト内の特定のタイプのアイテムをソートできるようにするには、それらが比較可能でなければなりませTんIComparable<T>。アイテムを比較できるようになったので、次のようにソート アルゴリズムを実装するだけです。

どちらも O(n*log(n)) ですが、インタビューでは Merge ソートの方が実装しやすいと思います。ここで 1 つを選択するポイントは、 Bubble sortなど、実行時間が悪く、完全に単純化されたものを提案しないことだと思います。

于 2013-03-10T17:23:03.663 に答える
2

QuickSort 実装を使用できます。

static void QuickSort<T>(List<T> a, int left, int right) where T : IComparable<T>
{
    int i = left, j = right;
    T pivot = a[(left + right) / 2];
    while (i <= j)
    {
        while (a[i].CompareTo(pivot) < 0)
            i++;
        while (a[j].CompareTo(pivot) > 0)
            j--;
        if (i <= j)
        {
            T temp = a[i];
            a[i++] = a[j];
            a[j--] = temp;
        }
    }
    if (left < j)
        QuickSort(a, left, j);
    if (i < right)
        QuickSort(a, i, right);
}

これがList.Sort()やっていることです。

于 2013-03-10T17:25:18.900 に答える
1

多数の並べ替えアルゴリズムについては、ウィキペディアを参照してください。

それらの間に順序がある限り、タイプを知る必要はありません。Tのサブタイプであることを要求することで、それを確実にすることができますIComparable。

于 2013-03-10T17:23:11.727 に答える
1

わかりました、これは実際には 2 つの問題です: 2 つの要素を比較してそれらがどのような順序にある​​べきかを確認する方法と、それらを順序付ける方法です。

2 つの要素を比較するには、呼び出し元に何かを渡して比較を行うように依頼するか、Comparer.Defaultを使用して要素を作成します。

要素を整理するには、QuickSort を実装することをお勧めします。

于 2013-03-10T17:25:48.650 に答える