Java でのクイックソートの簡単な例

この記事では主に Java の簡単なクイックソートの例を詳しく紹介しますので、興味のある方は参考にしてください

1. 基本概念

要素の検索 (理論上は気軽に行うことができます)をピボット (ピボット) として指定し、ピボットの左側の要素の値がピボットの値を超えず、ピボットの右側の要素の値が以下になるように配列を分割します。このようにして、ピボットとしての要素はソート後に正しい値に調整されます。再帰的クイックソートは、ソート後に他の n-1 個の要素を正しい位置に調整します。最後に、ソート後に各要素が正しい位置に配置され、ソートが完了します。したがって、クイック ソート アルゴリズムの中核となるアルゴリズムは分割操作、つまり分割統治再帰のためにベンチマークの位置を調整し、返されたベンチマークの最終位置を調整する方法です。

2. ベンチマーク要素を選択します

1. ベンチマーク要素を修正します

入力シーケンスがランダムであれば、処理時間は許容範囲内です。配列がすでにソートされている場合、この時点での除算は非常に悪い除算です。各除算ではソート対象のシーケンスを 1 つずつ減らすことしかできないため、これは最悪のシナリオであり、クイック ソートはバブル ソートになり、時間計算量は Θ(n^2) になります。さらに、入力データが順序付けされているか、部分的に順序付けされていることが非常に一般的です。したがって、最初の要素を基本要素として使用することは非常に悪いため、すぐに中止する必要があります。

2. ランダムな基本元

これは比較的安全な戦略です。参照要素の位置はランダムであるため、結果として得られるセグメンテーションが常に低品質になるとは限りません。配列全体の番号がすべて等しい場合でも、これは最悪のケースであり、時間計算量は O(n^2) です。実際、理論上の最悪のケースを得るためにクイックソートをランダム化する確率は、わずか 1/(2^n) です。したがって、ランダム化されたクイック ソートは、ほとんどの入力データに対して予想される時間計算量 O(n×log(n)) を達成できます。

3. 3 つの数値の中央を見つける

最良の分割は、並べ替えるシーケンスを同じ長さのサブシーケンスに分割することです。最良の状態では、シーケンスの中央の値 (N/2 番目) を使用できます。番号。ただし、これは計算が難しく、クイックソートの速度が大幅に低下します。このような中央値の推定値は、3 つの要素をランダムに選択し、それらの中央値を基本要素として使用することによって取得できます。実際には、ランダム性はあまり役に立たないため、左端、右端、中央位置の 3 つの要素の中央値をベース要素として使用するのが一般的なアプローチです。

3. パーティションアルゴリズム

パーティションアルゴリズムはクイックソートを学ぶ前に、まずこのアルゴリズムを学ぶことができます。コードは以下に掲載されています:

  public int partition(int[] num,int left,int right){
    if(num==null || num.length<=0 || left<0 || right>=num.length){
      return 0;
    }
    int prio=num[left+(right-left)/2];  //获取数组中间元素的下标
    while (left<=right){         //从两端交替向中间扫描
      while (num[left]<prio)
        left++;
      while (num[right]>prio)
        right--;
      if (left<=right){
        swap(num,left,right);    //最终将基准数归位 
        left++;
        right--;
      }
    }
    return left;
  }

このメソッドのアイデアは、まずピボット要素を見つけることです (最初の要素はこのメソッドの実装で見つかります。実際にはそれに関する記事がたくさんありますが、ここでは説明を簡略化します)、配列から開始します (特に、どこに行くかは渡されたパラメーターによって決まります)。左側の要素が大きいことが判明するたびに、左右に 2 つのポインターが生成されます。ピボット要素、i は停止し、右側の要素がピボット要素 j より小さければ停止し、これを 2 つの数字の位置を交換します。左右の2つのポインタが交わるまで。次に、ピボット要素を左側の位置 (本来あるべき場所) に挿入します。

これを実行すると、配列の [left, right] 部分が 2 つの部分に分かれて表示され、左側のピボット要素の最終位置はピボット要素以下になります。右側の値はピボット要素以上です。ピボット要素は完全に正しい位置に挿入されます。

4. ソートアルゴリズムの実装

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