私は整数ベクトルを持っています。ベクトルのサイズは約 2k で、ベクトル内の各数値は [0, 2M] の範囲にあり、0 である可能性が高いです。
まばらなベクトルなので、ベクトルをソートするための通常のアルゴリズムよりも優れたアルゴリズムがあるかどうか疑問に思っていますか? このシナリオに最適な並べ替えアルゴリズムはどれですか?
ありがとう
4 に答える
3
この答えは少し明白すぎるかもしれません...
ほとんどのエントリはゼロなので、すべてのゼロがベクトルの一方の端にあり、ゼロ以外の要素がもう一方の端にあるように、事前交換を行わないでください。
ベクターの両端から開始します。一方の端から最初の非ゼロ要素を検索し、もう一方の端から最初のゼロ要素を検索します。それらを交換し、2 つの検索位置が一致するまで続行します。ベクトルは、ミーティング ポイントで 2 つの部分に分割されます。1 つの部分にはゼロ要素のみが含まれ、その他の非ゼロ要素は含まれます。ゼロ以外の要素でミーティング ポイントからのベクトルを並べ替えます。実際にソートが必要なアイテムはほとんどないはずです。
数ダース程度の要素を並べ替える場合、実際に使用される並べ替えアルゴリズムは、パフォーマンスの観点から大きな違いはありません (半ダース程度の要素の場合、バブル ソートに勝るものはありません!)。
于 2013-10-22T19:54:34.460 に答える
2
2000 要素のベクトルがある場合、それをどのようにソートするかについてあまり心配する必要はありません...非常に小さいです!
つまり、n 個の整数を持つベクトルがあり、それぞれが 0 から M の間で、M が小さい場合、Counting sortを使用して O(n) 時間で並べ替えることができます。
ベクトルが既知の範囲内に n 個の実数を持ち、その数が均一に分布している場合、バケット ソートを使用して O(n) 予想時間でソートできます。
于 2013-10-22T19:49:24.493 に答える
1
たまたま多くの要素を持つ通常の密なベクトルを記述しています。スパース0ベクトルは非ゼロ要素のみを格納し、要素が格納されていない場合は と見なされます。0
スパース ベクトルを並べ替えるには、通常どおりに並べ替えます。2000年はもう小さいですが、純粋にスパース構造を使って「（要素が）0の可能性が高い」とすれば、その数はもっと少なくなります。
疎な構造の例は、vector< pair<int, double> >がpair.firstインデックスで、pair.secondが値です。
于 2013-10-22T19:52:32.493 に答える
1
私の頭に浮かぶ最高のものは基数ソートですが、これは 3 方向クイックソートよりも実装が困難です。O(n*log(n)) -> O(n) である多くの同じ要素をスキップするため、3-way クイックソートが最適です。ほぼすべてのプログラミング言語に実装があると思います。
于 2013-10-22T19:53:39.843 に答える