分割とスワップソートとも呼ばれるクイックソート。分割と征服の戦略で実装されたクイックソートアルゴリズム。
この記事では、主にJavaScriptを使用して、インプレースアイデアのクイックソートを実装することについて説明しています
方法の分割と処理：
コンピューターサイエンスでは、分割および征服法は、複数のブランチの再帰に基づいた非常に重要なアルゴリズムパラダイムです。文字通りの説明は「分裂と征服」です。これは、複雑な問題を2つ以上の同一または類似のサブ問題に分割することを意味します。サブ問題の終了が簡単かつ直接解決できることを意味し、元の問題の解決策は、サブ問題の解決策の合併です。 （ウィキペディアからの抜粋）
クイックソートアイデア
アレイ内の要素を定規として指定し、それよりも大きく配置し、要素の前よりも小さく配置し、すべてが正の順序で配置されるまでこれを繰り返します。
クイックソートは3つのステップに分かれています。
ベンチマークを選択します：データ構造のベンチマークとして要素を選択します（ピボット）
パーティション：参照要素値のサイズを参照し、順序付けられていない領域を分割します。参照要素よりも小さいすべてのデータは1つの間隔に配置され、参照要素よりも大きいすべてのデータは別の間隔に配置されます。パーティション操作が完了した後、参照要素の位置は、最終選別後の位置です。
再帰：すべての順序間隔に1つの要素が残っているまで、ステップ1とステップ2のアルゴリズムを初めて再帰的に呼び出します。
次に、一般的な実装方法について話しましょう（インプレースアルゴリズムは使用されていません）
function QuickSort（arr）{if（arr.length <= 1）return; //配列の中央に最も近い桁のベンチマーク、奇数、偶数が値が異なりますが、そうは思いません。もちろん、最初の数字または最後の数字をベンチマークとして選択できます。ここにはあまり説明がありませんvar pivotindex = math.floor（arr.length/2）; var pivot = arr.splice（pivotindex、1）[0]; //左と左の間隔は並べ替えられた数字を保存するために使用されますvar左= []; （var i = 0; i <arr.length; i ++）{console.log（ 'the' +（i + 1） + 'パーティション操作のループ：'）; {right.push（arr [i]）; console.log（ 'right：' +（arr [i]））}} // concat演算子を使用して、左の間隔、参照、および右の間隔を新しい配列にスプライスするために使用されます。 Quicksort（右））;} var arr = [14、3、15、7、76、11]; console.log（QuickSort（arr））;/**ベースが7の場合、最初のパーティションは左と右の2つのサブセットで取得されます[3、2、] 7 [14、15、76、11];左サブセットのあらゆる並べ替え*は参照76で終了し、右サブセットを分割してソートして[14、15、11] 76*この時点で、上記の[14、15、11]を分割し、上記[14、15、11]に分割して分割され、上記[14、11]に分割され、上記[14、11]に分割されます[14、11]は、上記[14、11]に分割されます。上記の[14、11]は分割され、上記の[11]に分割され、ベース11、11 [14]に分類されます。BreakPointのデバッグを通じて、結果を取得できます。
短所：
ω（n）の追加のストレージスペースが必要です。これは、マージソートと同じくらい悪いです。生産環境では、追加のメモリスペースが必要であり、パフォーマンスに影響します。
同時に、多くの人が上記が本当に迅速な種類だと考えています。したがって、以下では、インプレースアルゴリズムのクイックソートを推奨する必要があります
in-situアルゴリズムの詳細については、ウィキペディアを参照してください。壁の下にいる学生はバイドゥに似ています。
インプレース
通常、クイックソートは再帰で実装されます。最も重要なのは、配列を2つの部分に分割するパーティションセグメンテーション関数です。1つはピボットよりも小さく、もう1つはピボットよりも大きいです。特定の原則が上記で言及されています
function Quicksort（arr）{// swapp関数スワップ（arr、a、b）{var temp = arr [a]; arr [a] = arr [b]; arr [b] = temp;} //パーティション関数パーティション（arr、左、右）{/***最初は、最終的なピボットストレージを知ることができません。 = arr [右];/***ピボットよりも小さい要素を保存する場合、それらは前の要素の隣にあります。そうしないと、ギャップに格納されている要素はピボットよりも大きくなる場合があります。 */var storeIndex = left; for（var i = left; i <右; i ++）{if（arr [i] <pivot）{/*** raveseを配列をトラバースし、ピボットよりも大きい要素を見つけます（ピボットよりも大きい要素がスキップされます）スワップ*/swap（arr、storeindex、i）; storeindex ++;} //最後に：sporiindexにswap pivotに、最終的な正しい位置スワップにベンチマーク要素を配置します（arr、右、storeindex）;} function sort（arr、左、右）{if（左>右）; 1）; sort（arr、storeindex + 1、右）;} sort（arr、0、arr.length -1）; return arr;} console.log（quicksort（[8、4、90、8、34、67、1、26、17]）;パーティションの最適化
ここの慎重な学生は、異なるベンチマークを選択するときに異なるパフォーマンスパフォーマンスがあるかどうかを尋ねることができます。答えはイエスですが、私はフロントエンドの人であり、アルゴリズムについてあまり知らないので、このピットは強力な人々に任せています。
複雑
クイックソートは最速のソートアルゴリズムであり、その時間の複雑さはo（log n）です
平均的な状況では、nアイテムの順序では対１（n log n）の比較が必要です。最悪の場合、ο（n2）比較が必要です。
https://github.com/lyz0106/
上記は、編集者によって導入されたJavaScriptの実装インプレースアイデアのクイックソート方法です。私はそれが誰にでも役立つことを願っています。ご不明な点がございましたら、メッセージを残してください。編集者はあなたに時間内に返信します。 Wulin Network Webサイトへのご支援ありがとうございます！