3

これは、STL std::sort 関数を使用したソートの背後にあるメカニズムに関する一般的な質問です。並べ替えに関するいくつかの投稿を読みましたが、一般に、ベクトルの並べ替えは、リンクされたリストの並べ替えよりも高速です。これは構造/オブジェクトのベクトルとリンクされたリストに当てはまりますか? 構造のリンクされたリストの場合、インデックスを変更するだけで簡単にソートできると思います。一方、ベクトルの並べ替えは、構造体/オブジェクトのデータが連続しているため、データの場所を物理的に切り替える必要があるように見えます (これは本当ですか?)。その場合、リンクされたリストをソートする方が速いようです。

編集!!!: 写真付き:

ここに画像の説明を入力

したがって、質問はより適切に表現されていると思います:オブジェクトの並べ替え、リンクされたリストの並べ替え、またはベクトル (これはオブジェクトのサイズに依存する場合があります) のどちらが高速ですか? また、連結リストのソートは 3) のように行われ、ベクトルのソートは 2) のように行われますか?

4

3 に答える 3

3

の並べ替えlistは特殊です（つまりlist、関数sortがあり、で並べ替えることはできませんstd::sort）。

void sort();
template <class Compare> void sort(Compare comp);

複雑さ：約N個のlog（N）比較。ここで、N == size（）。

std::sort一般的に。

template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);

複雑さ：O（N log（N））（ここで、N ==最後-最初）の比較。

std::list::sortの結果は。と同じであることに注意してくださいstd::stable_sort。標準には情報がないことに注意してください。どのsortように実現する必要がありますか。実装定義です。

于 2012-09-14T21:12:20.407 に答える
2

インデックスやポインターなどの並列コレクションを並べ替えることで、いつでも並べ替えることができます。これは、リストとベクトルの両方で機能します。

リストのソートが遅い理由は、最速のソートアルゴリズムがランダムアクセスを必要とするためです。つまり、特定のインデックスの値をすぐに取得できる能力です。リストではそれができません。リンクされたリスト (たとえば) の 10 番目の項目を取得するには、最初から開始して 10 回進む必要があります。

于 2012-09-14T21:16:48.933 に答える
2

おっしゃる通りstd::vector、要素のコピーが遅い場合は、ある程度遅くなります。C++11 では移動セマンティクスが導入されており、要素をコピーする代わりに移動できます。

リンクされたリストは、マージソートを使用してソートするのが非常に簡単です。これは、他の優れたソートアルゴリズムと同じ O(n log n) です。違いはオーバーヘッドにあります。

いつものように、結果が重要な場合は、特定のケースをベンチマークすることをお勧めします。

于 2012-09-14T21:26:14.243 に答える