// 给定一个数组
$arr = [5, 1, 9, 3, 7, 4, 8, 6, 2];
// 指定某个下标的值作为中间数
$pivot = $arr[0];
// 重新排列数组, 使得 左边的元素 <= $pivot <= 右边的元素
// 类似 [ 左边元素, $pivot, 右边元素]
// 提示: $pivot 的位置不一定就是正中间
partition($arr, 0);
dd($arr);
function swap(array &$arr, int $i, int $j)
{
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}
function partition(array &$arr, int $index)
{
$len = count($arr);
$low = 0;
$high = $len - 1;
if ($index != $low)
{
swap($arr, $low, $index);
}
$pivot = $arr[$low];
while ($low < $high)
{
while ($low < $high && $arr[$high] >= $pivot)
$high--;
swap($arr, $low, $high);
while ($low < $high && $arr[$low] <= $pivot)
$low++;
swap($arr, $low, $high);
}
}
网友评论