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,"
";
        $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;
    }