// 给定一个数组
$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);
}
}
php - 快速排序的枢轴选取
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
