ここには私が持っていたインタビューの質問があります。文字の配列を並べ替える
入力：文字列（ASCII）。文にすることができます。ダブができます。私の考えはあなたがサイズ256の配列を持っているし、次にそれを使用ソートバケットの種類を行うことでした
線形時間と一定の追加のスペースが、もし： 出力：
期待複雑ASCII順にソートが値あなたは重複を持っていますし、それをどう扱うのでしょうか？これは一定の空間と見なされますか？私はそれがあなたがたった256のサイズの配列を使用していて、入力の大きさに合わせて成長しないためだと思います。
私はそれを自分自身でやりたいのですが、具体的なコードは望ましくありませんが、ヒントがあれば助かります！
この問題の解決方法はcounting sortです。
サイズ128の配列を持ち、すべての値が0に初期化されます。文字のASCII値を使用して配列にインデックスを付け、配列の値をインクリメントします。
並べ替えられたシーケンスはサイズ128の配列を走査するだけで生成され、配列[i]がゼロでない場合はascii値iの文字を出力し、値は印刷する文字の頻度を示します。
これは一定の大きさのO（1）アルゴリズムと線形時間O（N）アルゴリズムです。
ASCIIの場合、配列サイズは256でなく、128でなければなりません。ASCIIは7ビットエンコーディングです。 –
@JonSkeet拡張アスキー文字セットがあります。しかし、それはポイントではありません。とにかく –
「拡張ASCII」は特定のエンコーディングではありません。私の経験では一般に役に立たない用語です。あなたの答えを編集してASCIIに256文字の印象を与えないようにする方が良いでしょう - 既にその誤りを伝播させるネット上の場所が多すぎます。 –
配列の値は何であるべきかを考えてください。 （そして、あなたはASCIIのために128であるサイズが必要なだけです...） –
ああ私が参照してください。インデックスの位置は文字になり、値はカウントになります。ありがとう！ –
これはカウントソートになります。 128サイズ配列の線形時間。 –