0

私は現在、マージソートの暗黙のバージョンに取り組んでいます。私はそれをC++とC＃で実装しました。次に、それらをそれぞれstl sortおよびarray.sort（）アルゴリズムと比較しました。C ++では、同等の（場合によってはより良い）結果が得られました。しかし、C＃では、ポインターを使用するために安全でないコードを使用する必要がありました。ここでは、パフォーマンスはデフォルトのソートとそれほど比較できません。だから、私は知りたいです

-1。どのアルゴリズムがstlと.netの基本クラスライブラリで使用されていますか？（リンクの方が良いです）
2。安全でないコードにはパフォーマンスの問題がありますか？
3.新しいアルゴリズムのパフォーマンスの測定に関する提案はありますか？

4

3 に答える 3

6

.NETは、クイックソートのバリエーション（Sedgewickの3クイックソートの中央値）を使用します。

並べ替えの専門家でない限り、組み込みの並べ替えを広範囲のデータ（ランダム、既に順序付けされたセット、逆順序付けされたセットを含む）で打ち負かすことができれば驚きます。安全でないコードに頼ることは通常悪い考えです...

于 2009-06-07T10:26:40.050 に答える
1

STLソートは実装に依存する場合がありますが、（ウィキペディアが言うように）通常はイントロソートであり、クイックソートとヒープソートの組み合わせです。O（n log n）比較の平均的な複雑さを持っている必要があります。

于 2009-06-07T10:29:59.967 に答える
0

.NETはQuickSortを使用します。Reflectorを使用して、System.Collections.Generic.ArraySortHelperで実装を表示できます。

ほとんどの場合、最悪の場合の実行時間は長くなりますが、QuickSortはMergeSortよりも高速に実行されます。標準のQuickSortにもいくつかの改善があったと思いますが、これらのいずれかが使用されているかどうかはわかりません。

QuickSortを使ったSTLも思い出すようですが、完全にはわかりません。

于 2009-06-07T10:32:56.887 に答える