双路快速排序（Dual-Pivot QuickSort / Two-Way QuickSort）

<?php
function dualPivotQuickSort(array &$arr, int $low, int $high): void {
    if ($low < $high) {
        $p = partition($arr, $low, $high);
        dualPivotQuickSort($arr, $low, $p - 1);
        dualPivotQuickSort($arr, $p + 1, $high);
    }
}

function partition(array &$arr, int $low, int $high): int {
    // 选择枢轴，这里选择第一个元素
    $pivot = $arr[$low];
    $i = $low + 1;
    $j = $high;

    while (true) {
        // 向右移动 i，直到找到大于等于枢轴的元素
        while ($i <= $high && $arr[$i] < $pivot) {
            $i++;
        }
        // 向左移动 j，直到找到小于等于枢轴的元素
        while ($j >= $low + 1 && $arr[$j] > $pivot) {
            $j--;
        }
        // 如果两个指针交错，退出循环
        if ($i > $j) {
            break;
        }
        // 交换 arr[i] 和 arr[j]
        swap($arr, $i, $j);
        $i++;
        $j--;
    }
    // 将枢轴放到正确的位置
    swap($arr, $low, $j);
    return $j;
}

function swap(array &$arr, int $i, int $j): void {
    $temp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $temp;
}

// 测试示例
$data = [29, 10, 14, 37, 13, 8, 15, 29, 10];
echo "排序前: " . implode(", ", $data) . "\n";
dualPivotQuickSort($data, 0, count($data) - 1);
echo "排序后: " . implode(", ", $data) . "\n";
?>

排序前: 29, 10, 14, 37, 13, 8, 15, 29, 10
排序后: 8, 10, 10, 13, 14, 15, 29, 29, 37