algorithm - 要素が重複している配列をソートするのに最適なデータ構造は何ですか?

Question

配列に重複した要素が含まれている場合、どのデータ構造がソートに適していますか?

Bツリーは機能しますか？

Answer 1

ここで説明されているように、要素値の固定された狭い範囲の場合、カウント ソート アルゴリズムを使用できます。その複雑さは ですO(n + k)。ここで、nは配列のサイズでありk、基本的に、可能なさまざまな要素の量です。

ポイントは、同じ要素の数を計算し、正しい順序で挿入することです。