php排序算法

冒泡排序

//循环进行相邻两数比较，大的放后边
$arr = [2,44,56,23,11,46,69,35];
function pop_sort($arr){
    $len = count($arr);
    for($i=1; $i<$len; $i++){
        for($j=0; $j<$len-$i; $j++){
            if($arr[$j] > $arr[$j+1]){
                $tmp = $arr[$j+1];
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $tmp;
            }
        }
    }
    return $arr;
}

选择排序

//假设每次循环找到最小值依次放进数组
$arr = [2,44,56,23,11,46,69,35];
function select_sort($arr)
{
    $len = count($arr);
    for($i=0; $i<$len-1; $i++){
        $min = $i;
        for($j=$min+1; $j<$len; $j++){
            if($arr[$min] > $arr[$j]){
                $min = $j;
            }
        }
        if($min <> $i){
            $tmp = $arr[$min];
            $arr[$min] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }
    return $arr;
}

插入排序

//将要排序的元素插到假定已经排好序的数组里
$arr = [2,44,56,23,11,46,69,35];
function insert_sort($arr)
{
    $len = count($arr);
    for($i=1; $i<$len; $i++){
        $tmp = $arr[$i];
        for($j=$i-1; $j>=0; $j--){
            if($tmp < $arr[$j]){
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $tmp;
            }else{
                break;
            }
        }
    }
    return $arr;
}

快速排序

//从数组取一个数作为标尺，遍历数组小于标尺的放数组a, 大于标尺的放数组b, 递归，最后合并a-标尺-b即可
function quick_sort($arr)
{
    $len = count($arr);
    if($len <= 1){
        return $arr;
    }
    $base_num = $arr[0];

    $left =[];
    $right =[];
    for($i=1; $i<$len; $i++){
        if($arr[$i] < $base_num){
            $left[] = $arr[$i];
        }else{
            $right[] = $arr[$i];
        }
    }
    $left = quick_sort($left);
    $right = quick_sort($right);

    $arr = array_merge($left, [$base_num], $right);
    return $arr;
}

时间复杂度

排序方式	最差时间分析	平均时间复杂度	稳定度	空间复杂度
冒泡排序	O(n2)	O(n2)	稳定	O(1)
快速排序	O(n2)	O(n*log2n)	不稳定	O(log2n)~O(n)
选择排序	O(n2)	O(n2)	稳定	O(1)
二叉树排序	O(n2)	O(n*log2n)	不稳定	O(n)
插入排序	O(n2)	O(n2)	稳定	O(1)
堆排序	O(n*log2n)	O(n*log2n)	不稳定	O(1)
希尔排序	O	O	不稳定	O(1)

空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

对于一个算法来说，空间复杂度和时间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。

有时我们可以用空间来换取时间以达到目的。