几大排序算法PHP实现

function swap(&$arr, $a, $b){
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}
-------------------冒泡排序------------------------------------------- 
//沉底法
function bubbleSort($arr){
    $flag = true;
    $len = count($arr);
    for($i=0; $i<$len-1 && $flag; $i++){
        $flag = false;
        for($j=0; $j<$len-$i-1; $j++){
            if($arr[$j] > $arr[$j+1]){
                swap($arr, $j, $j+1);
                $flag = true;
            }
        }
    }
    return $arr;
}

//冒泡法
function bubbleSort2($arr){
    $flag = true;
    $len = count($arr);
    for($i=0; $i<$len-1 && $flag; $i++){
        $flag = false;
        for($j=$len-1; $j>$i; $j--){
            if($arr[$j-1] > $arr[$j]){
                swap($arr, $j-1, $j);
                $flag = true;
            }
        }
    }
    return $arr;
}

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定排序

----------------------选择排序------------------------------------------------

function selectSort($arr){
    $len = count($arr);
    for($i=0; $i<$len-1; $i++){
        $min = $i;
        for($j=$i+1; $j<$len; $j++){
            if($arr[$j] < $arr[$min]){
                $min = $j;
            }
        }
        if($min != $i){
            swap($arr, $i, $min);
        }
    }
    return $arr;
}

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：不稳定排序

-----------------------插入排序-------------------------------------------------

function InsertSort($arr){
    $len = count($arr);
    for($i=1; $i<$len; $i++){
        if($arr[$i] < $arr[$i-1]){
            $insertVal = $arr[$i];
            for($j=$i-1; $j>=0 && $arr[$j] > $insertVal; $j--){
                $arr[$j+1] = $arr[$j];
            }
            $arr[$j+1] = $insertVal;
        }
    }
    return $arr;
}

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定排序

------------------------快速排序-------------------------------------------------

function quickSort(&$arr, $l=0, $r){
    $len = count($arr);
    if(!is_array($arr) || $len <= 1) { 
        return $arr;
    }
    if($l < $r){
        $i = $l;
        $j = $r;
        $baseVal = $arr[$l];
        while($i < $j){
            while($i<$j && $arr[$j] > $baseVal){
                $j--;
            }
            if($i < $j)
                $arr[$i++] = $arr[$j];
            while($i<$j && $arr[$i] < $baseVal){
                $i++;
            }
            if($i < $j)
                $arr[$j--] = $arr[$i];
        }
        $arr[$i] = $baseVal;
        quickSort($arr, $l, $i-1);
        quickSort($arr, $i+1, $r);
        return $arr;
    }
}

function quickSort2($arr){
    $arrL = $arrR = [];
    $len = count($arr);
    if(!is_array($arr) || $len <= 1) { 
        return $arr;
    }
    $baseVal = $arr[0];
    for($i=1; $i<$len; $i++){
        if($arr[$i] <= $baseVal){
            $arrL[] = $arr[$i];
        }elseif($arr[$i] > $baseVal){
            $arrR[] = $arr[$i];
        }
    }
    $arrL = quickSort2($arrL);
    $arrR = quickSort2($arrR);
    return array_merge($arrL, [$baseVal], $arrR);
}
时间复杂度：O(nlogn)
空间复杂度：O(1)
稳定性：不稳定排序