快速排序是一种分而治之的算法。它基于这样的思想:选择一个元素作为主元，并围绕主元对数组进行分区，主元的左侧包含所有小于主元的元素，主元的右侧包含所有大于主元的元素。选择枢轴的方法有很多种。下面提到了其中的一些:
- 数组的第一个元素
- 数组的最后一个元素
- 数组的随机元素
- 数组的中位索引元素
与合并排序相比，快速排序的空间复杂度较低，因为它不使用辅助数组。
示例:
为了理解快速排序，让我们考虑一个未排序的数组 [-4, 1, 25, 50, 8, 10, 23] 并讨论对数组进行排序所采取的每个步骤升序排列。
在实现中在本例中，选择数组的最后一个元素作为主元。在分区过程开始时，创建变量i和j，它们最初是相同的。随着分区的进行，i 和 j 的值会变得不同。 i表示小于主元的元素和大于主元的元素之间的边界。 j表示大于pivot的元素和未分区数组之间的边界。
分区后生成两个分区，左侧分区包含小于pivot的元素，右侧分区包含大于pivot的元素。两个分区再次使用相同的逻辑进行分区，并且该过程继续进行，直到分区具有零个或一个元素。此过程的最终结果将是一个已排序的数组。
快速排序的实现
<?php
// 调用分区函数的快速排序函数
//根据枢轴元素排列和分割列表
//快速排序是一个递归函数
function quicksort(&$Array, $left, $right) {
if ($left < $right) {
$pivot = partition($Array, $left, $right);
quicksort($Array, $left, $pivot-1);
quicksort($Array, $pivot+1, $right);
}
}
//分区函数排列和分割列表
//基于主元元素分成两个列表
// 在本例中，选择列表的最后一个元素
//作为枢轴元素。一个列表包含所有元素
//小于另一个列表包含的主元元素
//所有大于主元的元素
function partition(&$Array, $left, $right) {
$i = $left;
$pivot = $Array[$right];
for($j = $left; $j <=$right; $j++) {
if($Array[$j] < $pivot) {
$temp = $Array[$i];
$Array[$i] = $Array[$j];
$Array[$j] = $temp;
$i++;
}
}
$temp = $Array[$right];
$Array[$right] = $Array[$i];
$Array[$i] = $temp;
return $i;
}
//打印数组的函数
function PrintArray($Array, $n) {
for ($i = 0; $i < $n; $i++)
echo $Array[$i]." ";
echo "\n";
}
//测试代码
$MyArray = array(-4, 1, 25, 50, 8, 10, 23);
$n = sizeof($MyArray);
echo "原始数组\n";
PrintArray($MyArray, $n);
quicksort($MyArray, 0, $n-1);
echo "\n排序数组\n";
PrintArray($MyArray, $n);
?> 上面的代码将给出以下输出:
原始数组
-4 1 25 50 8 10 23
排序数组
-4 1 8 10 23 25 50 时间复杂度:
最坏情况下快速排序的时间复杂度为θ(N²)，最佳和平均情况下的时间复杂度为θ(NlogN) .