PHPソートアルゴリズムQuick Sort（クイックソート）とその最適化

この記事では、主に PHP のソート アルゴリズム Quick Sort (クイック ソート) とその最適化アルゴリズムを紹介し、PHP Quick Sort の原理と実装方法をサンプルの形式で分析し、さまざまな最適化テクニックと運用上の注意点を分析します。を参照してください

この記事では、PHP のソート アルゴリズム Quick Sort (Quick Sort) とその最適化アルゴリズムについて例を示して説明します。参考のために皆さんと共有してください。詳細は次のとおりです:

基本的なアイデア:

クイックソートはバブルソートを改良したものです。彼の基本的なアイデアは、1 回のソートでソート対象のレコードを 2 つの独立した部分に分割し、レコードの 1 つの部分のキーワードが他の部分のキーワードよりも小さくなるようにすることで、レコードの 2 つの部分をすばやく個別にソートできるようにするというものです。全体 並べ替えプロセスは、シーケンス全体を順序付けるという目的を達成するために再帰的に実行できます。

基本的なアルゴリズム手順:

例:

今ソートされるレコードが次であると仮定します:

6 2 7 3 8 9

最初のステップは、変数 $low を作成することです。レコードに、$high は最後のレコードを指します。$pivot は、ソートされるレコードの最初の要素 (必ずしも最初の要素ではありません) にピボットとして割り当てられます。ここでは、次のようになります。ステップでは、$pivot より小さいすべての数値を $pivot の左側に移動する必要があるため、$high から始めて右から左に見て、変数 $high の値を継続的に減少させながら、6 より小さい数値を探し始めることができます。最初の添字 3 のデータは 6 より小さいため、データ 3 は添字 0 の位置 ($low が指す位置) に移動され、添字 0 のデータ 6 は添字 3 に移動され、最初の比較が完了しました:

3 2 7 6 8 9

$low = 0;
$high = 5;
$pivot = 6;

3 番目のステップでは、今回は $pivot よりも大きい比較を開始し、前から順に探します。戻る。変数 $low をインクリメントすると、添字 2 のデータが $pivot より大きい最初のデータであることがわかります。そのため、添字 2 ($low が指す位置) のデータ 7 と添字 3 ($low が指す位置) のデータ 7 を使用します。 6 つのデータが交換され、データのステータスは次の表になります:

//这时候,$high 减小为 3
$low = 0;
$high = 3;
$pivot = 6;

2 番目と 3 番目のステップを完了することをサイクルの完了といいます。 。

4 番目のステップ (つまり、次のサイクルの開始) は、2 番目のステップのプロセスを模倣します。

5番目のステップは、3番目のステップのプロセスを模倣することです。

2 番目のループを実行した後のデータのステータスは次のとおりです:

3 2 6 7 8 9

//这时候,$high 减小为 3
$low = 2;
$high = 3;
$pivot = 6;

このステップでは、$low と $high が「一致」していることがわかります。両方とも下付き文字 2 をポイントします。これで、最初の比較は終了です。結果は次のようになります。$pivot(=6) の左側の数値はすべてそれより小さく、$pivot の右側の数値はすべてそれより大きくなります。

次に、 $pivot の両側のデータ {3, 2} と {7, 8, 9} をグループ化し、グループ化できなくなるまでそれぞれ上記の処理を実行します。

注: クイック ソートの最初のパスでは最終結果が直接得られません。k より大きい数値と k より小さい数値を k の両側に分割するだけです。最終結果を得るには、添字 2 の両側の配列に対してこの手順を再度実行し、正しい結果を得るために配列が分解できなくなる (データが 1 つだけになる) まで配列を分解する必要があります。

アルゴリズムの実装:

//这时候,$high 减小为 3
$low = 2;
$high = 2;
$pivot = 6;

main 関数では、クイック ソートの最初のパスで配列全体がソートされるため、開始点は $low=0,$high=count( $ arr)-1。 次に、QSort() 関数は再帰呼び出しプロセスであるため、カプセル化されます:

//交换函数
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//主函数：
function QuickSort(array &$arr){
  $low = 0;
  $high = count($arr) - 1;
  QSort($arr,$low,$high);
}

上記の QSort() 関数から、Partition() 関数がis この関数の機能は、最初のキーワードの選択など、キーワードの 1 つを選択することであるため、これはコード全体の中核です。次に、左側の値がそれより小さく、右側の値がそれより大きくなるように、それを特定の位置に配置するように最善を尽くします。このようなキーワードをピボットと呼びます。

$low=0,$high=count($arr)-1。

然后 QSort()コードに直接移動します:

function QSort(array &$arr,$low,$high){
  //当 $low >= $high 时表示不能再进行分组，已经能够得出正确结果了
  if($low < $high){
    $pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二，算出枢轴值
    QSort($arr,$low,$pivot - 1); //对低子表（$pivot左边的记录）进行递归排序
    QSort($arr,$pivot + 1,$high); //对高子表（$pivot右边的记录）进行递归排序
  }
}

結合されたコード全体は次のとおりです:

//选取数组当中的一个关键字，使得它处于数组某个位置时，左边的值比它小，右边的值比它大，该关键字叫做枢轴
//使枢轴记录到位，并返回其所在位置
function Partition(array &$arr,$low,$high){
  $pivot = $arr[$low];  //选取子数组第一个元素作为枢轴
  while($low < $high){ //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环）
    while($low < $high && $arr[$high] >= $pivot){
      $high --;
    }
    swap($arr,$low,$high); //终于遇到一个比$pivot小的数，将其放到数组低端
    while($low < $high && $arr[$low] <= $pivot){
      $low ++;
    }
    swap($arr,$low,$high); //终于遇到一个比$pivot大的数，将其放到数组高端
  }
  return $low;  //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

アルゴリズムを呼び出します:

function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
function Partition(array &$arr,$low,$high){
  $pivot = $arr[$low];  //选取子数组第一个元素作为枢轴
  while($low < $high){ //从数组的两端交替向中间扫描
    while($low < $high && $arr[$high] >= $pivot){
      $high --;
    }
    swap($arr,$low,$high); //终于遇到一个比$pivot小的数，将其放到数组低端
    while($low < $high && $arr[$low] <= $pivot){
      $low ++;
    }
    swap($arr,$low,$high); //终于遇到一个比$pivot大的数，将其放到数组高端
  }
  return $low;  //返回high也行，毕竟最后low和high都是停留在pivot下标处
}
function QSort(array &$arr,$low,$high){
  if($low < $high){
    $pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二，算出枢轴值
    QSort($arr,$low,$pivot - 1);  //对低子表进行递归排序
    QSort($arr,$pivot + 1,$high); //对高子表进行递归排序
  }
}
function QuickSort(array &$arr){
  $low = 0;
  $high = count($arr) - 1;
  QSort($arr,$low,$high);
}

実行結果:

れee

複雑さの分析:

最適な状況では、つまり、数値軸が配列全体の中央の値になるように選択された場合、配列は毎回 2 つの半分に分割されます。したがって、最適な場合の時間計算量は O(nlogn) になります (ヒープ ソートおよびマージ ソートと同じ)。

最坏的情况下，待排序的序列是正序或逆序的，那么在选择枢轴的时候只能选到边缘数据，每次划分得到的比上一次划分少一个记录，另一个划分为空，这样的情况的最终时间复杂度为 O(n^2).

综合最优与最差情况，平均的时间复杂度是 O(nlogn).

快速排序是一种不稳定排序方法。

由于快速排序是个比较高级的排序，而且被列为20世纪十大算法之一。。。。如此牛掰的算法，我们还有什么理由不去学他呢！

尽管这个算法已经很牛掰了，但是上面的算法程序依然有改进的地方，下面具体讨论一下

快速排序算法优化

优化一：优化选取枢轴：

在前面的复杂度分析的过程中，我们看到最坏的情况无非就是当我们选中的枢轴是整个序列的边缘值。比如这么一个序列：

9 1 5 8 3 7 4 6 2

按照习惯我们选择数组的第一个元素作为枢轴，则 $pivot = 9，在一次循环下来后划分为{1，5，8，3，7，4，6，2} 和{ }（空序列），也就是每一次划分只得到少一个记录的子序列，而另一个子序列为空。最终时间复杂度为 O(n^2)。最优的情况是当我们选中的枢轴是整个序列的中间值。但是我们不能每次都去遍历数组拿到最优值吧？那么就有了一下解决方法：

1、随机选取：随机选取 $low 到 $high 之间的数值，但是这样的做法有些撞大运的感觉了，万一没撞成功呢，那上面的问题还是没有解决。

2、三数取中法：取三个关键字先进行排序，取出中间数作为枢轴。这三个数一般取最左端、最右端和中间三个数，也可以随机取三个数。这样的取法得到的枢轴为中间数的可能性就大大提高了。由于整个序列是无序的，随机选择三个数和从左中右端取出三个数其实就是同一回事。而且随机数生成器本身还会带来时间的开销，因此随机生成不予考虑。

出于这个想法，我们修改 Partition() 函数：

function Partition(array &$arr,$low,$high){
  $mid = floor($low + ($high - $low) / 2);  //计算数组中间的元素的下标
  if($arr[$low] > $arr[$high]){
    swap($arr,$low,$high);
  }
  if($arr[$mid] > $arr[$high]){
    swap($arr,$mid,$high);
  }
  if($arr[$low] < $arr[$mid]){
    swap($arr,$low,$mid);
  }
  //经过上面三步之后，$arr[$low]已经成为整个序列左中右端三个关键字的中间值
  $pivot = $arr[$low];
  while($low < $high){  //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环）
    while($low < $high && $arr[$high] >= $pivot){
      $high --;
    }
    swap($arr,$low,$high); //终于遇到一个比$pivot小的数，将其放到数组低端
    while($low < $high && $arr[$low] <= $pivot){
      $low ++;
    }
    swap($arr,$low,$high); //终于遇到一个比$pivot大的数，将其放到数组高端
  }
  return $low;  //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

三数取中法对于小数组有很大可能能沟得出比较理想的 $pivot，但是对于大数组就未必了，因此还有个办法是九数取中法。。。。。。

优化二：优化不必要的交换：

现在假如有个待排序的序列如下：

5 1 9 3 7 4 8 6 2

根据三数取中法我们取 5 7 2 中的 5 作为枢轴。

当你按照快速排序算法走一个循环，你会发现 5 的下标变换顺序是这样的：0 -> 8 -> 2 -> 5 -> 4，但是它的最终目标就是 4 的位置，当中的交换其实是不需要的。

根据这个思想，我们改进我们的 Partition() 函数:

function Partition(array &$arr,$low,$high){
  $mid = floor($low + ($high - $low) / 2);  //计算数组中间的元素的下标
  if($arr[$low] > $arr[$high]){
    swap($arr,$low,$high);
  }
  if($arr[$mid] > $arr[$high]){
    swap($arr,$mid,$high);
  }
  if($arr[$low] < $arr[$mid]){
    swap($arr,$low,$mid);
  }
  //经过上面三步之后，$arr[$low]已经成为整个序列左中右端三个关键字的中间值
  $pivot = $arr[$low];
  $temp = $pivot;
  while($low < $high){  //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环）
    while($low < $high && $arr[$high] >= $pivot){
      $high --;
    }
    //swap($arr,$low,$high); //终于遇到一个比$pivot小的数，将其放到数组低端
    $arr[$low] = $arr[$high];  //使用替换而不是交换的方式进行操作
    while($low < $high && $arr[$low] <= $pivot){
      $low ++;
    }
    //swap($arr,$low,$high); //终于遇到一个比$pivot大的数，将其放到数组高端
    $arr[$high] = $arr[$low];
  }
  $arr[$low] = $temp;  //将枢轴数值替换回 $arr[$low];
  return $low;  //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

在上面的改进中，我们使用替换而不是交进行操作，由于在这当中少了多次的数据交换，因此在性能上也是有所提高的。

优化三：优化小数组的排序方案：

对于一个数学科学家、博士生导师，他可以攻克世界性的难题，可以培育最优秀的数学博士，当让他去教小学生“1 + 1 = 2”的算术课程，那还真未必比常年在小学里耕耘的数学老师教的好。换句话说，大材小用有时会变得反而不好用。

也就是说，快速排序对于比较大数组来说是一个很好的排序方案，但是假如数组非常小，那么快速排序算法反而不如直接插入排序来得更好（直接插入排序是简单排序中性能最好的）。其原因在于快速排序用到了递归操作，在大量数据排序的时候，这点性能影响相对于它的整体算法优势而言是可以忽略的，但如果数组只有几个记录需要排序时，这就成了大炮打蚊子的大问题。

因此我们需要修改一下我们的 QSort() 函数：

//规定数组长度阀值
#define MAX_LENGTH_INSERT_SORT 7
function QSort(array &$arr,$low,$high){
  //当 $low >= $high 时表示不能再进行分组，已经能够得出正确结果了
  if(($high - $low) > MAX_LENGTH_INSERT_SORT){
    $pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二，算出枢轴值
    QSort($arr,$low,$pivot - 1); //对低子表（$pivot左边的记录）进行递归排序
    QSort($arr,$pivot + 1,$high); //对高子表（$pivot右边的记录）进行递归排序
  }else{
    //直接插入排序
    InsertSort($arr);
  }
}

PS：上面的直接插入排序算法大家可以参考：《PHP排序算法之直接插入排序（Straight Insertion Sort）》

在这里我们增加一个判断，当 $high - $low 不大于一个常数时（有资料认为 7 比较合适，也有认为 50 比较合适，实际情况可以是适当调整），就用直接插入排序，这样就能保证最大化的利用这两种排序的优势来完成排序工作。

优化四：优化递归操作：

大家知道，递归对性能时有一定影响的，QSort()函数在其尾部有两次递归的操作，如果待排序的序列划分极端不平衡（就是我们在选择枢轴的时候不是中间值），那么递归的深度将趋近于 n，而不是平衡时的 log₂n，这就不仅仅是速度快慢的问题了。

我们也知道，递归是通过栈来实现的，栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多，因此如果能减少队规，将会大大提高性能。

听说，递归都可以改造成循环实现。我们在这里就是使用循环去优化递归。（关于递归与循环大家可以参考知乎里面的讨论 《所有递归都可以改写成循环吗？》）

我们对QSort() 函数尾部递归进行优化：

//规定数组长度阀值
#define MAX_LENGTH_INSERT_SORT 7
function QSort(array &$arr,$low,$high){
  //当 $low >= $high 时表示不能再进行分组，已经能够得出正确结果了
  if(($high - $low) > MAX_LENGTH_INSERT_SORT){
    while($low < $high){
      $pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二，算出枢轴值
      QSort($arr,$low,$pivot - 1); //对低子表（$pivot左边的记录）进行递归排序
      $low = $pivot + 1;
    }
  }else{
    //直接插入排序
    InsertSort($arr);
  }
}

在上面，我们使用循环替换递归，减少了之前一般的递归量。结果是一样的，但是采用循环而不是递归的方法可以缩减堆栈的深度，从而提高了整体性能。

相关推荐：

PHP排序算法之归并排序(Merging Sort)

PHP排序算法之冒泡排序(Bubble Sort)

PHP排序算法之简单选择排序(Simple Selection Sort)

以上がPHPソートアルゴリズムQuick Sort（クイックソート）とその最適化の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。