c# - SortedList のパフォーマンス - ソートされたリストはどのようにソートされますか?

Question

ソートされたリストの詳細を調べて、いくつかの特定の状況で必要なように機能するかどうかを分析できるようにしています。

要素をソートするために使用する特定のソートアルゴリズムを知っている人はいますか?

Answer 1

SortedList<T,U>内部でキーに配列を使用し、アイテムをAdd正しい順序で挿入して「並べ替え」を実行します。Add新しいアイテムで呼び出すとArray.BinarySearch、Array.Insert.

これが、これらの特性を備えている理由です。

このメソッドは、並べ替えられていないデータの O(n) 操作です。ここで、n はカウントです。新しい要素がリストの最後に追加された場合、これは O(log n) 操作です。挿入によってサイズが変更される場合、操作は O(n) です。