30
可能性の重複：
which type of sorting is used in the function sort()?std :: sortはQuicksortを実装していますか？
がのstd ::をソートクイックソートを実装していますか？
A
答えて
-3
だと思います。 std :: listにはsortメソッドがあります。ソートを呼び出すには、2つのイテレーター、beginとendを取ることができます。
3
これはライブラリの実装によって異なります。 mergesortの実装は、最悪のケースO（N * logN）であり、クイックソートはO（N^2）に劣化する可能性があるため、最も一般的です。
Thisを確認します。
また、私が知っている限り、ある種のヒューリスティックが入力に使用され、内部で使用するのに最適なアルゴリズムを決定するので、std::sort()にさまざまなアルゴリズムを使用する可能性があります。ウィキペディアから
+1
これはクイックソートの無作為化されたバージョンかもしれないので、O（N^2）最悪の場合の引数はこの場合保持されません。 – LunaticSoul
0
-
特定のソートアルゴリズムが義務付けられておらず、実装間で異なることがあります。 Sort Wiki Link
+0
この場合はおそらく真実ですが、私はWikipediaで読んだことに非常に注意します。参照がある場合は、代わりに標準を引用してください。 – ereOn
0
quicksortまたはintrosortを使用します。高いため、最悪のクイックソートの複雑さ（N^2）とLINKLISTに実装するのが比較的厳しいの
-3
。私はクイックソートを使って考えることはできません。
+4
'std :: sort'はリンクされたリストでは動作しませんので、問題ありません。 –
32
伝統的に使われているアルゴリズムは2つあります。
std::sortはQuickSortを使用する可能性が最も高い、または少なくともクイックソートを超える変動が再帰が深すぎ行くHeapSortに「退化」IntroSortと呼ばれます。規格から
：
複雑：O（Nログ（N））の比較。
std::stable_sortは、安定性要件のためにMergeSortを使用する可能性が最も高いです。ただし、MergeSortは効率的になるために余分なスペースが必要です。標準から
：
複雑さ：それは高々N （N）の比較を記録ありません。十分な余分なメモリが利用可能である場合、それはN log（N）である。
私はstd::sortが有望であると（これまでに）パイソン（実際にはそれのために作られた）、JavaとAndroidの中で採用されているTimSortを実装見ていません。
+0
@ maxim-yegorushkin：ウィキペディアの記事では、ヒーポートの代わりにイントロソートを挿入ソートに切り替えると主張しているようです：/ http://en.wikipedia.org/wiki/Sort_(C%2B%2B） "The GNU Standard C++例えば、ライブラリは、ハイブリッドソートアルゴリズムを使用します。イントロソートは、最初に、2×log2 nで与えられる最大深度まで実行されます。ここで、nは要素数で、結果に挿入ソートが続きます。 –
関連する問題
Wikipediaは、特定のアルゴリズムが指定されていないことを示します。 – Sapph