//选择排序
function selection_sort($arr){
    $len = count($arr);
    if($len <= 1) return $arr;
    
    for($i=0; $i<$len; $i++){
        $min = $arr[$i];
        $pos = $i;
        for($j=$i+1; $j<$len; $j++){
            if($min > $arr[$j]){
                $min = $arr[$j];
                $pos = $j;
            }
        }
        if($pos != $i){
            $arr[$pos] = $arr[$i];
            $arr[$i] = $min;
        }
    }
    return $arr;
}

//插入排序
function insertion_sort($arr){
    $len = count($arr);
    if($len <= 1) return $arr;
    
    for($i=1; $i<$len; $i++){
        $insertion = $arr[$i];
        $j = $i - 1;
        while($insertion < $arr[$j]){
            $arr[$j+1] = $arr[$j];
            $j--;
            if($j < 0)break;
        }
        if($j == $i-1) continue;
        $arr[$j+1] = $insertion;
    }
    return $arr;
}

//冒泡排序
function bubble_sort($arr){
    $len = count($arr);
    if($len <= 1) return $arr;
    
    for($i=0; $i<$len; $i++){
        for($j=$len-1; $j>$i;  $j--){
            if($arr[$j] < $arr[$j-1]){
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j-1];
                $arr[$j-1] = $tmp;
            }
        }
    }
    return $arr;
}

//快速排序
function quick_sort($arr){
    $len = count($arr);
    if($len <= 1) return $arr;
    
    $base = current($arr);
    $left_arr = array();
    $right_arr = array();
    
    for($i=1; $i<$len; $i++){
        if($arr[$i] <= $base) $left_arr[] = $arr[$i];    
        if($arr[$i] > $base) $right_arr[] = $arr[$i];    
    }
    
    $left_arr = quick_sort($left_arr);
    $right_arr = quick_sort($right_arr);
    return array_merge($left_arr, array($base), $right_arr);
    
}

//test
$arr = array(4, 3, 2, 1, 6);
$arr_sorted = quick_sort($arr);
print_r($arr_sorted);