詳細-カットの下。
しかし、手始めに、古いものを覚えておいてください。
クイックソート（QSort）
ほとんどが彼女を知っています。 要するに-交換によって、サポート要素を取得します。小さな要素は、アレイの片側に残り、もう片方ではより大きくまたは等しくなります。 次に、結果のパーツに対して同じプロシージャを再帰的に実行します。 サポート要素自体は、ソートされた配列内の場所に既にありました。
同時に、彼らはしばしばクイックソートの最適化について話します。 最も有名な最適化は、サポート要素をランダムに選択することです。 したがって、クイックソートが最悪のパフォーマンスを示す場合の「ヒット」の可能性（O（n ^ 2）、皆が覚えているように）は大幅に減少します。
2番目に人気のあるアイデアは、配列を2つではなく3つの部分に分割することです。 要素は参照より小さく、それに等しく、要素は参照より大きくなります。 この最適化により、元の配列に同じ要素が多数ある場合の実行時間が大幅に高速化されます。結局、参照要素と参照要素が既に並べ替えられた配列の場所に「落ちた」ため、それらを並べ替える追加の手順は不要です。 実行される操作の数と再帰呼び出しの深さの両方が削減されます。 一般的に、少し節約する良い方法です。
難易度-平均でO（nlogn）、最悪の場合O（n ^ 2）、追加メモリ-O（logn）
どちらかといえば、悪くはないのでここに簡単に書いてください。
ビット単位のソート（基数ソート）
少し人気のないアルゴリズムですが、よく知られています。 彼の作品の論理は単純です。 数字の配列があるとしましょう。
まず、最初の（最高の）ランクで並べ替えます。 次に、ソートはカウントソートを使用して行われます。 難易度はo（n）です。 10個の「バスケット」を取得しました-シニアレベルは0、1、2などです。 次に、各バスケットで同じ手順を開始しますが、上級レベルではなく、次のレベルなどを検討します。
数字の桁と同じ数のステップがあります。 したがって、アルゴリズムの複雑さはO（n * k）、kはビット数です。
そのようなソートには、MSD（最上位桁-最初の上位ビット）とLSD（最下位桁-最初の下位ビット）の2種類があります。 LSDは、数値のソートに多少便利です。なぜなら、 桁数を等しくするために、左側の数字に重要でない0を「属性」する必要はありません。
MSDは、文字列のソートに便利です。
この実装のアルゴリズムには、追加のメモリ-O（n）が必要です。
詳細は、たとえばこちらをご覧ください 。
3方向のビット単位の並べ替え
文字列をソートしているとします。
要素を積極的に比較するqsortを使用すると、コストがかかりすぎます-文字列の比較は長い操作です。 はい、独自のコンパレータを作成できますが、これは多少効率的です。 しかし、まだ。
追加のメモリを必要とする基数を使用することも、あまり動機付けられません-行が大きくなる可能性があります。 はい、そして長い行、つまり 効率に対する放電抑制効果の数。
しかし、これらのアルゴリズムを何らかの方法で組み合わせるとどうなるでしょうか？
結果のアルゴリズムのロジックは次のとおりです。
1.支持要素を取ります。
2.配列を3つの部分に分割し、seniorカテゴリの参照と要素を比較します-小さい、等しい、大きいものに。
3. 3つの部分のそれぞれで、手順1から始めて、空の部分または要素が1つの部分に達するまで手順を繰り返します。
中間部分（つまり、上位ビットがサポート要素の最上位ビットに等しい場合）でのみ、次のビットに進みます。 残りの部分では、「稼働」放電を変更せずに操作が開始されます。
ソートの複雑さはO（nlogn）です。 追加メモリはO（1）です。
このアルゴリズムの欠点は、ビット単位の並べ替えとは異なり、配列を3つの部分のみに分割することです。これにより、たとえば、マルチスレッド実装の可能性が制限されます。 クイックソートよりも優れている点は、要素全体を比較する必要がないことです。 ビット単位のソートよりも優れている点は、追加のメモリを必要としないことです。
それとは別に、元の配列の要素が別の配列である場合、このような並べ替えが便利であることに注意してください。 次に、初期配列が入力された場合、たとえば、最高次が入力[i] [0]、次が入力[i] [1]などとなります。 このソートは、多次元クイックソートまたはマルチキークイックソートと呼ばれます。
より詳細-R.セジウィック、C ++の基本アルゴリズム、パート3、10章10.4「3方向のビット単位の高速ソート」
アルゴリズムのスキーム：
再度、3分割について
配列の相対参照の3つの部分への分割を実装する最も簡単な方法は、Bentley and McIlroyアルゴリズムを使用することです。 これは、標準のqsort分離手順に導入される次の追加で構成されます（要素を交換した直後）。
処理された要素が配列の左側にある場合（つまり、参照より大きくない場合）、参照と等しい場合、対応する要素（既に完全に処理されているため、参照よりも小さい）と交換することにより、配列の左側に配置されます。 同様に、処理された要素が配列の右側にあり、参照と等しい場合、配列の右側に配置されます。
分離手順が完了した後、要素の数が参照の数よりも少ない場合、等しい要素が配列の中央に（参照の要素よりも小さい要素の直後に）転送されることがすでに正確にわかっています。
詳細については、R。Sedgwick-Fundamental Algorithms in C ++、part 3、chap。7、7.6、「重複キー」を参照してください。