希尔排序

/*希尔排序*/
$arr = [14,18,19,37,23,40,29,30,11,7,2,1,8,6,3,5,4] ;
$sorted_arr = shellSort($arr);
myPrint($sorted_arr);    // 1 2 3 4 5 6 7 8 11 14 18 19 23 29 30 37 40  [Finished in 0.1s]
 
function shellSort($arr){
    $count = count($arr);
    $gap_list = [] ;
    $gap = floor($count/2);
    while($gap>=1){
        $gap_list [] = $gap;
        $gap = floor($gap/2);
    }   // 获得间隔序列
    

    foreach ($gap_list as $gap) {
        $subUnsortArr = getGapArr($arr,$gap) ;  // 跳过间隔所构成子序列
        $subsortArr = insertSort($subUnsortArr);    // 插入排序法排序序列
        $arr = setGapArr($arr,$subsortArr,$gap);    // 将有序子序列重新插入回原数组
    }
    return $arr;
}


function getGapArr($arr,$gap){
    $gapArr= [];$i=0;
    while($i<count($arr)){
        $gapArr[] = $arr[$i];
        $i+=$gap;
    }
    return $gapArr;
}

function setGapArr($arr,$sortedArr,$gap){
    $i=0;
    while($i<count($arr)){
        $arr[$i] = array_shift($sortedArr);
        $i+=$gap;
    }
    return $arr;
}



function insertSort($arr){
    for ($i=1; $i <count($arr) ; $i++) { 
        $tmp = $arr[$i];
        for ($j=$i; $j>0 ; $j--) {
            if($tmp<$arr[$j-1]){
                $arr[$j] = $arr[$j-1] ;
            }else{
                break;
            }
        }
        $arr[$j] = $tmp;
    }
    return $arr;
}