php算法

来源：https://www.cnblogs.com/zixuanfy/p/7617451.html

交换函数：注意要按引用传递，否则无法真正交换两个数的值

　　function exchange(&$a, &$b){
        $temp = $a;
        $a = $b;
        $b = $temp;
    }

1、直接插入算法

    //第一种实现
　　function insert_sort($arr){
        for ($i = 0; $i < count($arr)-1; $i++){
            for($j = $i+1; $j > 0; $j--){
                if($arr[$j] > $arr[$j-1]){
                    exchage($arr[$j], $arr[$j-1]);
                }
            }
        }
        return $arr;
    }
　　//第二种实现
    function insert_sort($arr){
        for ($i = 0; $i < count($arr)-1; $i++){
            $j = $i + 1;
            while($j > 0){
                if($arr[$j] > $arr[$j-1]){
                    exchage($arr[$j], $arr[$j-1]);
                }
                $j--;
            }
        }
        return $arr;
    }

2、希尔排序算法【暂缺】

3、直接选择排序算法

    function select_sort($arr){
        for($i = 0; $i < count($arr); $i++){
            $key = $arr[$i];
            $n = $i;
            for($j = $i+1; $j < count($arr); $j++){
                if($key  > $arr[$j]){
                    $key  = $arr[$j];
                    $n = $j;
                }
            }
            $arr[$n] = $arr[$i];
            $arr[$i] = $key;
        }
        return $arr;
    }

4、堆排序算法【暂缺】

5、冒泡排序算法

      //第一种
     function bubble_sort($arr){
        for($i = 0; $i < count($arr)-1; $i++){
            for($j = count($arr)-1; $j > $i; $j--){
                if($arr[$j-1] < $arr[$j]){ 
                    exchage($arr[$j], $arr[$j-1]);
                }
            }
        }
        return $arr;
    }
     //第二种
    function bubble_sort($arr){
        for($i = 0; $i < count($arr)-1; $i++){
            $j = 0;
            while($j < count($arr)-1-$i){
                if($arr[$j] < $arr[$j+1]){
                    exchage($arr[$j], $arr[$j-1]);
                }
                $j++;
            }
        } 
        return $arr;
    } 

6、快速排序算法

    function quick_sort(&$arr, $p, $r){
        if($p < $r){
            $q = partition($arr, $p, $r);
            quick_sort($arr, $p, $q-1);
            quick_sort($arr, $q+1, $r);
        }
    }
    function partition(&$arr, $p, $r){
        $i = rand($p, $r);    //实现随机化快排
        exchange($arr[$i], $arr[$r]);
        $n=$p-1;
        for($m = $p; $m < $r; $m++){
            if($arr[$m] < $arr[$r]){
                ++$n;
                exchange($arr[$m], $arr[$n]);
            }
        }
        exchange($arr[$n+1], $arr[$r]);

        return $n+1;       //n位上的元素，一经排序，则已固定
    }

7、归并排序算法【注意：数组按值传输】

　　function merge_sort(&$A, $p, $r){
        if($p < $r){
            $q = floor(($p + $r)/2);
            merge_sort($A, $p, $q);
            merge_sort($A, $q+1, $r);
            merge($A, $p, $q, $r);
        }
    }
    //第一种
    function merge(&$A, $p, $q, $r){    //哨兵牌法
        $n1 = $q - $p + 1;
        $n2 = $r - $q;
        for($i = 0; $i < $n1; $i++){
            $L[$i] = $A[$p+$i];
        }
        for($j = 0; $j < $n2; $j++){
            $R[$j] = $A[$q+$j+1];
        }
        //防止越界(哨兵)
        $L[$n1] = $R[$n2] = PHP_INT_MAX;
        $i = $j = 0;
        for($k = $p; $k <= $r; $k++){
            if($L[$i] <= $R[$j]){
                $A[$k] = $L[$i];
                $i++;
            }else{
                $A[$k] = $R[$j];
                $j++;
            }
        }
    }
    //第二种
    function merge(&$A, $p, $q, $r){    
        $n1 = $q - $p + 1;
        $n2 = $r - $q;
        for($i = 0; $i < $n1; $i++){
            $L[$i] = $A[$p+$i];
        }
        for($j = 0; $j < $n2; $j++){
            $R[$j] = $A[$q+$j+1];
        }    
        $i = $j = 0;
        $k = $p;
        while($i<$n1 && $j<$n2){
            if($L[$i] <= $R[$j]){
                $A[$k++] = $L[$i++];
            }else{
                $A[$k++] = $R[$j++];
            }
        }
        
        for(; $i<$n1; $i++){
            $A[$k++] = $L[$i];
        }
        for(; $j<$n2; $j++){
            $A[$k++] = $R[$j];
        }
    }

8、基数排序算法【暂缺】

9.堆排序算法

/*** 使用异或交换2个值，原理：一个值经过同一个值的2次异或后，原值不变* @param int $a * @param int $b */ function swap(&$a,&$b){ $a = $a^$b; $b = $a^$b; $a = $a^$b; } /*** 整理当前树节点（$n），临界点$last之后为已排序好的元素 * @param int $n * @param int $last * @param array $arr * */ function adjustNode($n,$last,&$arr){ $l = $n<<1;   // 左孩子 if( !isset($arr[$l])||$l>$last ){ return ;} $r = $l+1;  // 右孩子// 如果右孩子比左孩子大，则让父节点与右孩子比 if( $r<=$last&&$arr[$r]>$arr[$l] ){ $l = $r; } // 如果其中子节点$l比父节点$n大，则与父节点$n交换 if( $arr[$l]>$arr[$n] ){ swap($arr[$l],$arr[$n]); // 交换之后，父节点($n)的值可能还小于原子节点($l)的子节点的值，所以还需对原子节点($l)的子节点进行调整，用递归实现 adjustNode($l, $last, $arr); } }  /*** 堆排序（最大堆） * @param array $arr */ function heapSort(&$arr){ // 最后一个蒜素位 $last = count($arr); // 堆排序中常忽略 $arr[0]array_unshift($arr, 0); // 最后一个非叶子节点 $i = $last>>1; // 整理成最大堆，最大的数放到最顶，并将最大数和堆尾交换，并在之后的计算中，忽略数组最后端的最大数(last)，直到堆顶（last=堆顶） while(true){ adjustNode($i, $last, $arr); if( $i>1 ){ // 移动节点指针，遍历所有节点 $i--; }else{ // 临界点$last=1，即所有排序完成 if( $last==1 ){ break; } swap($arr[$last],$arr[1]); $last--; } } // 弹出第一个元素 array_shift($arr); }