完整快排

/*完整的快速排序
1. 低于5个元素的排序使用插入排序
2. 使用middle_tree算法选择合适的pivot
*/
const cutOff = 5 ;
$arr = [14,18,19,37,23,40,29,30,11,7,2,1,8,6,3,5,4,5,4] ;
$sorted_arr = quickSort($arr);
myPrint($sorted_arr);       
// 1 2 3 4 4 5 5 6 7 8 11 14 18 19 23 29 30 37 40 [Finished in 0.1s]


function quickSort($arr)
{
    $count = count($arr);
    if($count<=1)return $arr;
    if($count<= cutOff ){
        $arr = insertSort($arr);
        return $arr;
    }
    $arr = middle_tree_pivot($arr);  

    $pivot = $arr[$count-1];
    $i = 0 ; $j = $count-1;

    while ($i<$j && $j<$count) {
        if($arr[$i]>$pivot){
            while ( $j >$i ) {
                $j--;
                if($arr[$j]<$pivot){
                    swap($arr,$i,$j);
                    break;
                }
            }
        }
        if($i==$j) break;
        $i ++;
    }
    swap($arr,$i,$count-1);

    $leftArr=  [];
    $rightArr= [];
    if($i==0){
        $rightArr = array_slice($arr, $i+1);
    }else if($i==$count-1){
        $leftArr = array_slice($arr, 0, $i );
    }else{
        $leftArr = array_slice($arr, 0, $i );
        $rightArr = array_slice($arr, $i+1);
    }
    return array_merge(quickSort($leftArr) , [ $pivot ] ,  quickSort($rightArr));
}


/*低于阈值使用插入排序*/
function insertSort($arr){
    for($j=1;$j<count($arr);$j++){
        $tmp  = $arr[$j];
        $i = $j;
        while ( ($i-1)>=0 && $arr[$i-1]>$tmp) {     // 注意: 先比较索引-1的值是否逆序, 是才对索引减1赋值
            $arr[$i] = $arr[$i-1];
            $i -- ;
        }
        $arr[$i] = $tmp;
    }
    return $arr ;
}

/*找到中位数并移动到最右*/
function middle_tree_pivot($arr){
    $count = count($arr);
    if($count%2==0) $index = $count/2;
    else  $index = ceil( $count/2);
    $index-=1;

    swap($arr,$index,$count-1);
    return $arr;
}

/*自定义格式数组输出*/
function myPrint($arr){
    foreach ($arr as  $value) {
        echo $value." " ;
    }
    echo "\n";
}

/*交换数组中索引的两个元素*/
function swap(&$arr,$index1,$index2)
{
    $tmp = $arr[$index1];
    $arr[$index1] = $arr[$index2];
    $arr[$index2] = $tmp;
}