時間の複雑さ
平均：o（nlgn）
最悪の場合：O（n*n）は、データが既にソート状態にあるときに発生します。
1.参照としてデータから値a [i]を選択します
2。[i]を参照として使用するには、データを2つの部分に分割します：P1とP2。 p1≤a[i]のすべてのデータ、p2> a [i]のすべてのデータ、およびデータは{{p1} {a [i]} {p2}}になります
3.各部品に1つのデータのみが残るまで、P1とP2で上記の手順を繰り返します。
4。データは昇順でソートされます
基本例：
生データ：
{3、9、8、5、2、1、6}ステップ1：最初のデータを選択します：3
ステップ2：データを2つの部分に分割し、左側は3以下で、右側は> 3を超えています。
{2,1} {3} {9,8,5,6}ステップ3：各部品に1つのデータしか残っていないまで、各パーツの上記の手順を繰り返します。
{2,1} => {1} {2} {9、8、5、6} => {8、5、6} {9} => {5、6} {8} {9} => {5} {6} {8} {9} {9} {8} {9}ステップ4：データは昇順でソートされます。
{1} {2} {3} {5} {6} {8} {9}プログラムのデータは通常、配列に保存されます。タイプintの配列を例として使用すると、上記の手順をQuickSort関数プロトタイプに書き込むことができます。
Quicksort（int begin、int end）{// beginは配列の最初のデータのインデックス値、endは配列+1 // 1つのデータまたは0データのみがある場合、プログラムが返される場合、（begin == end || begin ==（end-1））return; int p = in [begin]; // pは選択された参照データです。最初のデータを選択しますint a = begin +1; // 2部構成データのインデックス値除算線int b = a; // bは（; b <end; b ++）{//配列のデータを順序付けのデータと比較するデータのインデックス値です。継続;} //データがすでに左側にある場合、[a]でint temp =を移動しません; // [a] = in [b]でデータを左に移動しません。 [b] = temp; a ++; // [begin] = in [a-1]; // [a-1] = pの2セットのデータの中央に参照値を右に移動する}}}}を移動します。 （a-1> begin）{//左にデータがある場合、上記のステップquicksort（begin、a）を繰り返します。 } if（end-1> a）{//右にデータがある場合、上記のステップQuickSort（a、end）を繰り返します。 } 戻る; //データがない場合}アルゴリズムの最適化
上記のクイックソートアルゴリズムは、入力データを考慮していないため、最も基本的なクイックソートであると言えます。ただし、このアルゴリズムの欠陥を簡単に見つけることができます。これは、入力データが基本的に順序付けられるか、完全に順序付けられる場合、アルゴリズムはバブルソーティングに縮退し、O（nn）ではなくo（n^2）です。
根本的な原因は、コードの実装では、一度に最初の配列からのみ開始することです。 「3つのヘッダー」、つまりArr [low]、arr [high]、arr [（low+high）/2]の中央値をピボットレコードとして使用すると、最悪のシナリオでのクイックソートのパフォーマンスを大幅に改善できます。ただし、配列順序のケースでは、パフォーマンスをO（n）に改善することはできません。最悪のシナリオでの高速ソートの時間パフォーマンスをさまざまな程度に改善する方法もあります。
さらに、クイックソートには再帰スタックが必要です。これは通常、それほど深くなく、ログ（n）レベルにあります。ただし、一度に分割された2つの配列の長さがひどくバランスが取れている場合、最悪の場合、スタックの深さはO（n）に増加します。この時点で、スタックスペースによってもたらされる空間的複雑さは無視できません。追加の変数のオーバーヘッドが追加された場合、ここでは恐ろしいO（n^2）スペースの複雑さに達することさえあります。したがって、クイックソートの最悪の空間的複雑さは固定値ではなく、同じレベルにさえない可能性があります。
この問題を解決するために、各分割後の端の長さを比較し、最初に短いシーケンスを並べ替えます（目的は、これらのスタックを最初に終了してスペースを解放することです）。これにより、最大深度がO（n）レベルに戻ることができます。
クイックソートのための3つの最適化のアイデアを次に示します。
小さな配列の場合、再帰コールを避けるために挿入並べ替えを使用できます。たとえば、（hi <= lo + m）の場合、ソートを挿入することができます。
サブアレイの中央値を使用して、アレイをスライスします。これにより、スライスが改善されますが、中央値を計算する犠牲を払っています。
配列に多数の繰り返し要素が含まれている場合、3方向スライシングを使用できます。アレイを3つの部分に分けます。それぞれ、スライス要素よりも小さい、より小さいアレイ要素に対応します。コードの実装は次のとおりです。
private static void sort1（int [] a、int lo、int hi）{if（hi <= lo）return; int lt = lo、i = lo + 1、gt = hi; int v = a [lo]; while（i <= gt）{if（a [i] <v）{swap（a、lt ++、i ++）; } else if（a [i]> v）{swap（a、i、gt-）; } else {i ++; } sort（a、lo、lt -1）;ソート（a、gt + 1、hi）; }}