04-快速排序

/**
 * 快速排序: 每次选最左边的点, 将数组划分为左右两部分, 保证右边的比选点大,左边的都比选点小, 对左右两边递归
 * 时间复杂度: 最好 O(nlogn) 最差 O(n2)
 * 空间复杂度: O(1)
 * 不稳定排序
 */
function quickSort(&$arr, $start, $end) {
    $i = $start;
    $j = $end;
    $pivot = $arr[$start];
    while ($j > $i) {
        // 右边有比选点小的, 扔到左边, 让下一while得以继续
        while ($arr[$j] >= $pivot && $j > $i) {
            $j--;
        }
        if ($arr[$j] <= $pivot) {
            $temp = $arr[$j];
            $arr[$j] = $arr[$i];
            $arr[$i] = $temp;
        }
        // 左边的有比选点大的就,扔到右边, 让上一while得以继续
        while ($arr[$i] <= $pivot && $j > $i) {
            $i++;
        }
        if ($arr[$i] >= $pivot) {
            $temp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $temp;
        }
    }
    // 循环结束后，i,j都指向选点
    if ($i > $start) {
        quickSort($arr, $start, $i - 1);
    }
    if ($j < $end) {
        quickSort($arr, $j + 1, $end);
    }
}

$arr = [38, 19, 29, 91, 85, 12, 41, 21];
quickSort($arr, 0, count($arr) - 1);
print_r($arr);