快速排序（三种写法：第三种 - 三路快速排序）

这里使用的语言是PHP，但是语言都是相通的，用别的语言也可以实现，可以参考这里自行实现别的语言版本

/**
 * 快速排序 3 三路快速排序
 * <v, =v, >v
 * 重复元素很多的情况
 */

//快速排序 1、主方法
function quickSort(&$arr)
{
    $arr_len = count($arr);
    if ($arr_len <= 0) {
        return [];
    }
    quick_sort($arr, 0, $arr_len - 1);
}

/**
 * 2、递归调用对arr[l...r]的范围进行排序
 * 三路快速排序
 * 
 */
function quick_sort(&$arr, $l, $r)
{
    
    if ($l >= $r) {
        return;
    }

    //在将要归并的数组区间随机一个数组索引
    $rand_index = rand() % ($r - $l + 1) + $l;
    SortHelper::swap($arr, $l, $rand_index);

    //使用最左侧的元素
    $v = $arr[$l];

    $lt = $l;//arr[$l+1...$lt] < v
    $i = $l + 1;//arr[$lt+1...$i) == v
    $gt = $r+1;// arr[$gt...$r] > v
    
    while ($i < $gt) {
        if ($arr[$i] < $v) {
            SortHelper::swap($arr, $i, $lt + 1);
            $lt++;
            $i++;  
        }elseif($arr[$i] > $v){
            SortHelper::swap($arr, $i, $gt - 1);
            $gt--;
        }else{
            $i++;
        }
    }
    SortHelper::swap($arr, $l, $lt);

    quick_sort($arr, $l, $lt - 1);
    quick_sort($arr, $gt, $r);
}

$arr = [100,4,5,6,7,2,44,59,67,57,45,71,82,85,98,94];
quickSort($arr);
for ($i=0; $i < count($arr); $i++) { 
    echo $arr[$i].', ';
}