php插入排序,快速排序,归并排序,堆排序

function bubble_sort(&$arr) {//php的陣列視為基本型別,所以必須用傳參考才能修改原陣列
    for ($i = 0; $i < count($arr) - 1; $i++)
        for ($j = 0; $j < count($arr) - 1 - $i; $j++)
            if ($arr[$j] > $arr[$j + 1]){
                $temp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $temp;
            }
                
}

插入排序

public function insertSort(&$arr){
        for($i = 1;$i < count($arr); $i++){
            $temp = $arr[$i];
            for($j = $i - 1;$j >= 0 && $arr[$j] > $temp; $j--)
            $arr[$j + 1] = $arr[$j];
            $arr[$j] = $temp;
        }
    }

快速排序

public function quickSort($arr){
        $len = count($arr);

        if($len <= 1)
            return $arr;
        $left = $right = [];
        $mid_index = $len>>1;echo $len,'.....',$mid_index,"<br>";
        $mid_value = $arr[$mid_index];

        for($i = 0;$i < $len;$i++){
            if($i == $mid_index)
                continue;

            if($arr[$i] < $mid_value)
                $left[] = $arr[$i];
            else
                $right[] = $arr[$i];
        }
        return array_merge($this->quickSort($left),(array)$mid_value,$this->quickSort($right));

    }

归并排序

public function merge_sort($arr){
        $len = count($arr);
        if($len <= 1)
            return $arr;
        $half = ($len >> 1) + ($len & 1);dd(($len >> 1));
        $arr2d = array_chunk($arr,$half);
        $left = $this->merge_sort($arr2d[0]);
        $right = $this->merge_sort($arr2d[1]);
        while(count($left) && count($right)){
            if($left[0] < $right[0])
                $reg[] = array_shift($left);
            else
                $reg[] = array_shift($right);
        }
        return array_merge($reg,$left,$right);
    }

堆排序

public function swap(&$x,&$y){
        $t = $x;
        $x = $y;
        $y = $t;
    }
    public function max_heapify(&$arr,$start,$end){
        $dad = $start;
        $son = $dad*2+1;
        if($son >=$end)
            return;
        if($son + 1 < $end && $arr[$son] < $arr[$son + 1])
            $son++;
        if($arr[$dad] < $arr[$son]){
            $this->swap($arr[$dad],$arr[$son]);
            $this->max_heapify($arr,$son,$end);
        }
    }
public function heap_sort($arr){
        $len = count($arr);//获取个数
        for($i = ceil($len/2) - 1;$i >= 0;$i--){//处理一半的数据
            $this->max_heapify($arr,$i,$len);
        }
        for($i= $len-1;$i > 0;$i--){
            $this->swap($arr[0],$arr[$i]);
            $this->max_heapify($arr,0,$i);
        }
        return $arr;
    }

相关推荐