迅速なソートを本当に理解する文章です

エンジニアであれば、多かれ少なかれ速い列を知っていて、その中の多くの人は簡単に速い列の実現を書くことができます.しかし、チェン一峰の速排事件を知っていますか.速排のベストプラクティスを知っていますか.本文は1つの争いから話して、生き生きとした詳しい例を通じてあなたに本当に速い列を理解させます.ええ、これは確かに冷たいご飯を炒める文章ですが、冷たいご飯をおいしい卵チャーハンに炒めたいです.余談は抜きにして、さっそく~

1.チェン一峰快排事件

事件全体を一言で要約すると、dissチェン一峰の速排が間違っている人がいて、以下の図になる.実は図からも見ましたが、この微博は発酵しておらず、掘金に発表された「チェン一峰版の急速なソートは完全に間違っている」(文章はもう訪問できない)という文章まで、また人に知られていることを質問されて、全体がにぎやかになりました.Dissの主なポイントは2つです.

一つは哨兵用のspliceで配列下標

ではなく

アルゴリズムは、

をその場で分割するのではなく、追加の空間を使用する.
歩哨:快速列で選択された比較対象の基準要素
この件では、ほとんどの学生がチェン先生を支持している.実は、このような粗雑な批判には問題があると思います.3つの理由があります.

1.1 spliceはすでに言及されており、時間の複雑さにはレベルの違いはない。

まず、チェン一峰の速排ブログのコメントでは、spliceは確かに問題があると述べています.下図を参照してください.また,spliceを用いたとしても,時間的複雑さはO(n)+O(n)=O(n)であり,スケール的には影響しなかった.

1.2アルゴリズムは空間複雑度を規定しておらず、極端な場合のアルゴリズム問題は通病である。

なお、快排はウィキペディア(中国語|英語)の定義では時間的複雑度のみが規定されており、空間的複雑度の定義は、
日文:実現方法によって違う
英語:O(n) auxiliary (naive) O(log n) auxiliary
だから空間の複雑さでアルゴリズムを攻撃するのは根拠がない.また,winterは上記のような問題においても,その場での早送りの空間的複雑さは尾再帰ではなくスタックを用いなければならないため,空間的複雑さはO(log(n))であり,早送りのたびに新しい空間を用いてもO(2n)=O(n)にほかならない.
もちろん、極端な場合(哨兵は毎回配列を分けますn-1および1個)チェン先生のアルゴリズムでは空間の複雑さがO(n )ですが、このような状況はチェット式アルゴリズムの特例ではなく、その場で速く並ぶ通病ではないので、チェット先生のせいにすることはできません.

1.3わかりやすい位置付けに基づいて肯定的

チェン先生のブログは実はずっと分かりやすくて、私も分かりやすいことを私自身がずっと追求しています.このアルゴリズムには瑕疵がないわけではないかもしれませんが、絶対に間違いとは言えません.私たちがやったのも瑕疵を批判するのではなく、どのような改善の方向があるかを考えています.
チェン先生のこの速い列は確かに覚えやすいです.私自身も含めて、チェン先生のこのアルゴリズムを通じてやっと本当に速い列を覚えました.その上で、この微博発の意味はないと思います.

2.クイックソートの複雑度分析

前に私たちは長い間チェットの1峰の速い列の事件をBBして、中間は私たちは何度も速い列の時間の複雑さと空間の複雑さに言及して、この部分では、私たちはなぜそれらがこのようなのかを分析します.

2.1時間複雑度

十分に理想的であれば,配列を毎回平均的な2つの部分に分けることを期待し,このような理想的な状況で分けると,最終的に完全な二叉木を得ることができる.n個の数字を並べ替えると、この木の深さはlog2n+1であり、n個の数を比較するのにかかる時間をT(n)に設定すると、以下の式が得られる[1].

T(n) ≤ 2T(n/2) + n，T(1) = 0  
T(n) ≤ 2(2T(n/4)+n/2) + n = 4T(n/4) + 2n  
T(n) ≤ 4(2T(n/8)+n/4) + 2n = 8T(n/8) + 3n  
......
T(n) ≤ nT(1) + (log2n)×n = O(nlogn) 

最悪の場合、この木は完全な斜めの木で、左半分か右半分しかありません.このとき我々の比較回数は=O(n )となる

2.2スペースの複雑さ

2.2.1その場で並べ替える

その場速列の空間占有は再帰によるスタック空間の使用であり、好ましくは再帰log2n回であるため、空間複雑度はO(log2n)であり、最悪の場合は再帰n-1回であるため、空間複雑度はO(n)である.

2.2.2その場で並べ替えない

非原地ソートの場合、再帰のたびにnの総数の余分な空間が宣言されるため、空間複雑度は原地ソートのn倍になります.すなわち、最良の場合はO(nlog2n)、最悪の場合はO(n )です.
複雑さについてもっと詳しく知りたい方は、「クイックソート複雑度分析」を参考にしてください.

3.早並びのベストプラクティスですね

上の部分を通ると、先端に並ぶ是非について初歩的な理解があると思います.では、速列のベストプラクティスとは何でしょうか.

3.1最も簡単で覚えやすい

これはチェン一峰先生のアルゴリズム実現の変体であり、es6の書き方を使ったため、コード量がより簡素になり、主体がより際立った.

function quickSortRecursion (arr) {
  if (!arr || arr.length < 2) return arr;
  const pivot = arr.pop();
  let left = arr.filter(item => item < pivot);
  let right = arr.filter(item => item >= pivot);
  return quickSortRecursion(left).concat([pivot], quickSortRecursion(right));
}

3.2より高い効率

ここにwinterの実装を貼って、もっと多くの実装を見たいので、githubの上の相互噴射アドレスを移動することができます.

function wintercn_qsort(arr, start, end){
    var midValue = arr[start];
    var p1 = start, p2 = end;
    while(p1 < p2) {
        swap(arr, p1, p1 + 1);
        while(compare(arr[p1], midValue) >= 0 && p1 < p2) {
            swap(arr, p1, p2--);
        }
        p1 ++;
    }
    if(start < p1 - 1) 
        wintercn_qsort(arr, start, p1 - 1);
    if(p1 < end) 
        wintercn_qsort(arr, p1, end);
}

3.3実際の最適化方法

さっきも言ったように、早列は実は最悪の場合があります.実際、日常の仕事の中で、もし本当にこのようなビッグデータレベルの最適化の必要があるならば、私たちは往々にして実際の状況に基づいて速い列に対していろいろな最適化を行います.
主な考え方は以下の点である[3].

合理的に哨兵を選択し、できるだけ斜樹

が現れないようにする.

重複する要素については、一度に

を並べ替える.

選択ソートを用いる小配列(V 8では10に設定)

を処理する.

最悪の場合を処理するためにスタックソートを使用するパーティション

は、左から右へ

を両側から中間へ遍歴する代わりに、従来から用いられている.

使用末尾再帰

異なるスレッドで問題を同時処理する

本文は本当に少し長いので、これは詳しく述べないで、必要な学生は自分で《高速ソートアルゴリズムの最適化の構想の総括》を参照することができます.

3.まとめ

本文はチェン一峰の速い列の事件から着手して、速い列の異なる情況の下の空間の複雑度と時間の複雑度を分析して、そして速い列の最良の実践と最適化の方法を提供しました.皆さんに速い列を知るのに役立つことを望んでいます.

参照ドキュメント:

「クイックソート複雑度分析」

「文章『面接官:チェン一峰版の急速なソートは完全に間違っている』をどう思いますか?」

「高速ソートアルゴリズムの最適化構想総括」