私は現在、C++でベクターがどのように機能するかを調べています。私はそれらの機能をかなりよく読んで理解しました。
10,000intのベクトルオブジェクトを並べ替えるさまざまな方法を検討しています。std::sortメソッドとシェルソートを使用しました。
ベクトルのシェルソートは、単純なCスタイルの配列のソートよりも遅いことに気づきました。これは、「コンテナの中央での要素の高速挿入または削除がサポートされていないため」（http://www.cppreference.com/wiki/container/vector/start）であることがわかりました。したがって、ランダムアクセスが多いシェルソートは明らかに非常に遅くなります。
10,000 intのベクトルに対して、より良い手動ソート方法は何でしょうか？これはあなたが見る学習演習のためです！:)
すべての意図と目的のために、ベクトルは追加された優れた配列です。ランダムアクセスは、Cスタイルの配列と同じくらい高速です。ベクトルの途中で要素を削除/挿入するのは遅いですが、同じことがCスタイルの配列にも当てはまります。シェルソートは、配列の場合と同じようにベクトルでも高速である必要があります。私には、あなたが何か変わったことをしているように聞こえます。
クイックソートまたはイントロソート（std::sort1つ）は、利用可能な最速の比較ベースのソートである必要があります。マージソートはクイックソートよりもわずかに遅いですが、病理学的なケースに対するクイックソートの感受性はありません。平均すると、これらはすべてO（n lg n）時間かかります（クイックソートの場合は2次最悪の場合）。
編集された更新
コード：C配列およびベクターベースのシェルソート。最適化の有無にかかわらず、100万個の要素の並べ替えには、私にはわからない理由で、ベクトルの2倍の時間がかかります。ベクトルにアクセスするときに、STLが多くのエラーチェックを行っているようです。
クイックソートなどのアルゴリズムは、ベクトルの場合と同様に、データをインプレースで並べ替えるのに理想的です。つまり、挿入や削除はなく、固定サイズのバッファ内でデータを移動するだけです。