HTML5 Academy-Coder: 「アルゴリズムの旅」の前号で、バブルソート方法と選択ソート方法を共有しました。どちらも時間計算量が O(n^) で「遅い」です。 2) 並べ替えます。今日は、さまざまなソート アルゴリズムの中で最も広く使用され、高速なソート アルゴリズムであるクイック ソート [平均時間計算量は O (n logn)] を紹介したいと思います。
ヒント１：「アルゴリズム」と「並べ替え」の基礎知識は、前回の「選択範囲の並べ替え方法」で詳しく説明していますので、記事末尾の該当記事リンクをクリックしてご覧ください。ここでは繰り返しません。
ヒント 2: 特に指定がない限り、この記事のクイック ソートは小さいものから大きいものの順に並べられています。
クイックソートは分割交換ソートであり、通常分割統治法と呼ばれます。
基本的な考え方: 元の問題を、元の問題とサイズは小さいが構造が似ているいくつかのサブ問題に分解します。これらの部分問題を再帰的に解決し、これらの部分問題の結果を元の問題の結果に結合します。
「基数」としてシーケンスから任意の数値を選択します。
「基数」より小さいすべての数値は「基数」以上のすべての数値に移動します。は「ベースライン」の右側の「」に移動されます。
この移動が終了すると、「ベースライン」は 2 つのシーケンスの中央になり、その後の並べ替えには参加しなくなります。
について繰り返します。 「ベースライン」の左右に 2 つのサブシーケンス すべてのサブシーケンスに 1 つの数値だけが残るまで、上記の手順が繰り返されます。
既存のシーケンス [8、4、7、2、0、3、1] があり、以下はクイック ソート方法を使用して並べ替える方法を示します。
まずベンチマークのインデックス値を取得し、次にスプライス配列メソッドを使用してベンチマーク値を取り出します。
ヒント: この例では、ベンチマークのインデックス値 = parseInt (シーケンス長 / 2)
ヒント: splice メソッドは元の配列を変更します。たとえば、 arr = [1, 2, 3]; ベースのインデックス値が 1、ベースの値が 2 の場合、元の配列は arr = [1, 3] になります
; 「ベースライン」サイズで 2 つのサブシーケンスに分割します
「ベースライン」より小さい数値は leftArr 配列に保存され、「ベースライン」以上の数値は rightArr 配列に保存されます
ヒント: もちろん、以下を入れることもできます。数値「ベンチマーク」は leftArr に格納され、「ベンチマーク」より大きい数値は rightArr に格納されます
シーケンスを走査してサイズを比較する必要があるため、各数値を「ベンチマーク」にするには、for ステートメントを使用して再帰呼び出しを実装し、サブシーケンスを走査し、サブシーケンスの結果を結合する必要があります
関数を定義し、仮パラメーターは配列を受け取るために使用されます
サブシーケンスの長さを判断します
再帰呼び出しでは、サブシーケンスの長さが 1 に等しい場合、再帰呼び出しは停止し、現在の配列が返されます。 
クイックソートメソッドの完全なコード
時間の複雑さ
クイックソートは不安定なソートアルゴリズムです
例: 既存のシーケンスは[1, 0, 1, 3]で、「ベースライン」の数値が2番目の1として選択されます
最初のラウンドでは比較後は[0, 1, 1, 3]となり、左の列が[0]、右の列が[1, 3]になります(右の列の1は前の1です)
です見つけるのは難しくありません。元のシーケンスにある 2 つの 1 の順序が破壊され、順序が変更されます。これは当然、「不安定な」ソート アルゴリズムです
前回の記事「バブルソート方法」では、 Oとは何か、ここでは多くは言いませんが、写真を見てください
以上がクイックソートの実装方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
