質問: stlのlist :: sort()で使用されている並べ替えアルゴリズムはどれですか? ランダムな整数のリストがあります。どのアルゴリズムがlist::sort()メソッドで使用されているのかと思います。例えば。次のコードで:list<int> mylist; // ..insert a million values mylist.sort(); 編集:参照 このより具体的な質問 。
回答: 標準は特定のアルゴリズムを必要とせず、安定している必要があり、約n lg nの比較を使用して並べ替えを完了する必要があるだけです。これにより、たとえば、クイックソートのマージソートまたはリンクリストバージョンが可能になります(一般的な考えに反して、クイックソートは必要ありません必要ありません配列の最も一般的な実装は)ですが、不安定です。その条件付きで、短い答えは、最新の標準ライブラリではstd::sortは、基本的には再帰の深さを追跡するquicksortであるイントロソート(イントロスペクティブソート)として実装され、quicksortが通常であればheapsort(通常は低速ですがo(n log n)の複雑さ)に切り替わります。再帰が深すぎます。ただし、イントロソートは比較的最近(1990年代後半)発明されました。古い標準ライブラリは通常、代わりにクイックソートを使用していました。stable_sortが存在するのは、配列のようなコンテナーをソートする場合、最速のソートアルゴリズムのほとんどが不安定であるため、標準には両方のstd::sort(高速ですが、必ずしも安定しているとは限りません)およびstd::stable_sort(安定していますが、多くの場合多少遅くなります)。ただし、どちらも通常はランダムアクセス反復子を想定しており、リンクリストのようなものでは(もしあれば)うまく機能しません。リンクリストの適切なパフォーマンスを得るために、標準にはlist::sort。ただし、リンクされたリストの場合、そのようなトレードオフは実際にはありません-安定との両方であるマージソートを実装するのは非常に簡単です(約)何よりも速い。そのため、安定するために必要なsortメンバー関数が1つだけ必要でした。