PHP-Sortieralgorithmus Quick Sort (Quick Sort) und seine Optimierung

Dieser Artikel stellt hauptsächlich den PHP-Sortieralgorithmus Quick Sort und seinen Optimierungsalgorithmus vor. Er analysiert die Prinzipien und Implementierungsmethoden von PHP Quick Sort und analysiert verschiedene Optimierungstechniken und Betriebsvorkehrungen, auf die sich Freunde beziehen können

Dieser Artikel beschreibt den PHP-Sortieralgorithmus Quick Sort (Quick Sort) und seinen Optimierungsalgorithmus anhand von Beispielen. Teilen Sie es wie folgt mit allen als Referenz:

Grundidee:

Quicksort ist eine Art Verbesserung der Blasensortierung. Seine Grundidee besteht darin, die zu sortierenden Datensätze durch eine Sortierung in zwei unabhängige Teile zu unterteilen. Die Schlüsselwörter eines Teils sind kleiner als die Schlüsselwörter des anderen Teils des Datensatzes. Dann können die beiden Teile der Datensätze schnell getrennt sortiert werden. Der gesamte Sortiervorgang kann rekursiv ausgeführt werden, um den Zweck der Reihenfolge der gesamten Reihenfolge zu erreichen.

Grundlegende Algorithmusschritte:

Zum Beispiel:

Angenommen, der Datensatz, der jetzt sortiert werden soll, ist:

6 2 7 3 8 9

Der erste Schritt besteht darin, die Variable $low zu erstellen, um auf den ersten Datensatz im Datensatz zu zeigen, $high, um auf den letzten Datensatz zu zeigen, und $pivot als Pivot-Zuweisung: Das erste Element des zu sortierenden Datensatzes (nicht unbedingt das erste), hier:

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

Zweiter Schritt, Wir vergleichen alle $. Die kleine Zahl in „pivot“ bewegt sich nach links von „$pivot“, sodass wir mit der Suche nach einer Zahl kleiner als 6 beginnen können, beginnend bei „$high“, von rechts nach links schauend und dabei den Wert der Variablen „$high“ ständig verringern. Wir finden den ersten Index 3. Die Daten sind kleiner als 6, daher werden die Daten 3 an die Position des Index 0 verschoben (die Position, auf die durch $low gezeigt wird), die Daten 6 des Index 0 werden an den Index 3 verschoben und der erste Vergleich erfolgt ist abgeschlossen:

3 2 7 6 8 9

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

Der dritte Schritt, wir beginnen mit dem zweiten Vergleich, dieses Mal wird es ein Vergleich sein, und Sie müssen ihn von vorne bis hinten suchen. Erhöhen Sie die Variable $low und stellen Sie fest, dass die Daten bei Index 2 die ersten sind, die größer als $pivot sind. Daher verwenden wir die Daten 7 bei Index 2 (die Position, auf die durch $low gezeigt wird) und die Daten 7 bei Index 3 (die Position, auf die gezeigt wird). at by $high). 🎜>

Das Abschließen des zweiten und dritten Schritts wird als Abschluss eines Zyklus bezeichnet.

Der vierte Schritt (d. h. der Beginn des nächsten Zyklus) ahmt den Prozess des zweiten Schritts nach.

Der fünfte Schritt besteht darin, den Prozess des dritten Schritts nachzuahmen.

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

Nach der Ausführung der zweiten Schleife ist der Datenstatus wie folgt:

3 2 6 7 8 9

An diesem Punkt stellen wir fest, dass $low und $high „zusammentreffen“: Sie zeigen beide auf Index 2. Damit ist der erste Vergleich beendet. Das Ergebnis ist wie folgt: Alle Zahlen links von $pivot(=6) sind kleiner als dieser Wert und alle Zahlen rechts von $pivot sind größer als dieser Wert.

Gruppieren Sie dann die Daten {3, 2} und {7, 8, 9} auf beiden Seiten von $pivot und führen Sie den obigen Vorgang aus, bis keine Gruppierung mehr möglich ist.

Hinweis: Der erste Durchgang der Schnellsortierung liefert nicht direkt das Endergebnis, sondern teilt nur die Zahlen größer als k und kleiner als k auf beide Seiten von k auf. Um das Endergebnis zu erhalten, müssen Sie diesen Schritt erneut für die Arrays auf beiden Seiten von Index 2 ausführen und dann das Array zerlegen, bis das Array nicht mehr zerlegt werden kann (nur ein Datenwert), um das richtige Ergebnis zu erhalten.

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

Algorithmusimplementierung:

In der Hauptfunktion, aufgrund der Beim ersten Durchgang sortiert Quicksort das gesamte Array, sodass es mit beginnt.

Dann

ist die Funktion ein rekursiver Aufrufprozess, also ist sie gekapselt:

//交换函数
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);
}

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

Aus dem obigen QSort() Anhand der Funktion können wir erkennen, dass die Funktion Partition () der Kern des gesamten Codes ist, da die Funktion dieser Funktion darin besteht, eines der Schlüsselwörter auszuwählen, beispielsweise das erste Schlüsselwort. Dann versuchen wir unser Bestes, es an einer bestimmten Position zu platzieren, sodass die Werte auf der linken Seite kleiner und die Werte auf der rechten Seite größer sind. Wir nennen ein solches Schlüsselwort einen Pivot. QSort()

Geben Sie den Code direkt ein:

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右边的记录）进行递归排序
  }
}

Der gesamte kombinierte Code lautet wie folgt:

//选取数组当中的一个关键字，使得它处于数组某个位置时，左边的值比它小，右边的值比它大，该关键字叫做枢轴
//使枢轴记录到位，并返回其所在位置
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下标处
}

Wir nennen den Algorithmus:

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);
}

Laufergebnis:

$arr = array(9,1,5,8,3,7,4,6,2);
QuickSort($arr);
var_dump($arr);

Komplexitätsanalyse:

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

In der optimalen Situation, das heißt, wenn die Zahlenachse so gewählt wird, dass sie bei liegt Mittelwert des gesamten Arrays, dann wird das Array jedes Mal in zwei Hälften geteilt. Daher beträgt die Zeitkomplexität im optimalen Fall O(nlogn) (wie Heap-Sortierung und Zusammenführungssortierung).

最坏的情况下，待排序的序列是正序或逆序的，那么在选择枢轴的时候只能选到边缘数据，每次划分得到的比上一次划分少一个记录，另一个划分为空，这样的情况的最终时间复杂度为 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)

Das obige ist der detaillierte Inhalt vonPHP-Sortieralgorithmus Quick Sort (Quick Sort) und seine Optimierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!