JavaScriptでのクイックソートの詳細説明

この記事では、JavaScript でのクイック ソートについて説明します。JavaScript でのクイック ソートについて知らない場合、または JavaScript でのクイック ソートに興味がある場合は、この記事を見てみましょう。 point

クイックソートは、ソートアルゴリズムにおける分割統治のアイデアのもう1つの典型的な応用です。本質的に、クイック ソートは、バブル ソート に基づく再帰的分割統治法と見なされるべきです。

クイックソートの名前はシンプルで粗雑ですが、この名前を聞くとすぐにその存在の意味がわかります。これは、ビッグデータを処理するための最速のソートアルゴリズムの1つです。ワーストケースの時間計算量は O(n²) に達しましたが、これは優れており、ほとんどの場合、平均時間計算量が O(n log n) のソート アルゴリズムよりも優れたパフォーマンスを示します。どちらか知っています。 。 。幸いなことに、私の強迫性障害は再発しましたが、多くの情報を確認した結果、「アルゴリズム芸術と情報学コンペティション」に関して満足のいく答えを見つけました。

例えば、クイックソートの最悪の動作状況は O(n²) です。順序 シーケンスのクイックソート。しかし、その償却期待時間は O(n log n) であり、O(n log n) 表記に暗黙的に含まれる定数係数は非常に小さく、複雑さが安定していて O(n log n) に等しいマージ ソートよりもはるかに小さくなります。 n)。したがって、順序が弱いほとんどの乱数シーケンスでは、マージ ソートよりもクイック ソートの方が常に優れています。

クイックソートアニメーションのデモ

クイックソートJavaScriptコードの実装:

function quickSort(arr, left, right) {  
    var len = arr.length,  
        partitionIndex,  
        left = typeof left != 'number' ? 0 : left,  
        right = typeof right != 'number' ? len - 1 : right;  
  
    if (left < right) {  
        partitionIndex = partition(arr, left, right);  
        quickSort(arr, left, partitionIndex-1);  
        quickSort(arr, partitionIndex+1, right);  
    }  
    return arr;}function partition(arr, left ,right) {     //分区操作  
    var pivot = left,                      //设定基准值（pivot）  
        index = pivot + 1;  
    for (var i = index; i <= right; i++) {  
        if (arr[i] < arr[pivot]) {  
            swap(arr, i, index);  
            index++;  
        }          
    }  
    swap(arr, pivot, index - 1);  
    return index-1;}function swap(arr, i, j) {  
    var temp = arr[i];  
    arr[i] = arr[j];  
    arr[j] = temp;}

上記がこの記事のすべての内容です。あまり詳しくない場合は、両方を自分で実装できます。マスターするのは簡単です！

関連する推奨事項:

Jsのバブルソートとクイックソートの詳細な説明

以上がJavaScriptでのクイックソートの詳細説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。