php几种常用算法

秒速五厘米 2022-05-29 01:28 168阅读 0赞

## 写一下几种常见排序算法，清一下脑子 ##

### 归并排序 ###

/** * Created by PhpStorm. * User: leon * Date: 2018/3/14 * Time: 下午2:37 */
    
    function mergeSort(&$arr) { 
        $len = count($arr);//求得数组长度
        mSort($arr, 0, $len-1);
        return $arr;
    }
    //实际实现归并排序的程序
    function mSort(&$arr, $left, $right) { 
        if($left < $right) {
            //说明子序列内存在多余1个的元素，那么需要拆分，分别排序，合并
            //计算拆分的位置，长度/2 去整
            $center = floor(($left+$right) / 2);
            //递归调用对左边进行再次排序：
            mSort($arr, $left, $center);
            //递归调用对右边进行再次排序
            mSort($arr, $center+1, $right);
            //合并排序结果
            mergeArray($arr, $left, $center, $right);
        }
    }
    //将两个有序数组合并成一个有序数组
    function mergeArray(&$arr, $left, $center, $right) { 
        //设置两个起始位置标记
        $a_i = $left;
        $b_i = $center+1;
        while($a_i<=$center && $b_i<=$right) {
            //当数组A和数组B都没有越界时
            if($arr[$a_i] < $arr[$b_i]) {
                $temp[] = $arr[$a_i++];
            } else {
                $temp[] = $arr[$b_i++];
            }
        }
        //判断 数组A内的元素是否都用完了，没有的话将其全部插入到C数组内：
        while($a_i <= $center) {
            $temp[] = $arr[$a_i++];
        }
        //判断 数组B内的元素是否都用完了，没有的话将其全部插入到C数组内：
        while($b_i <= $right) {
            $temp[] = $arr[$b_i++];
        }
    
        //将$arrC内排序好的部分，写入到$arr内：
        for($i=0, $len=count($temp); $i<$len; $i++) {
            $arr[$left+$i] = $temp[$i];
        }
    }
    
    $SortArr = array(2,9,1,8,3,8);
    $res =  mergeSort($SortArr);
    print_r($res);

### 选择排序 ###

/** * Created by PhpStorm. * User: leon * Date: 2018/3/13 * Time: 下午6:44 */
    
    /* * 思路： * 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 * 选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面） */
    function selectSort(...$array){ 
        $temp = 0;
        for($i = 0;$i < count($array) - 1;$i++){
            $minVal = $array[$i]; //假设$i就是最小值
            $minValIndex = $i;
            for($j = $i+1;$j < count($array);$j++){
                if($minVal > $array[$j]){ //从小到大排列
                    $minVal = $array[$j]; //找最小值
                    $minValIndex = $j;
                }
            }
            $temp = $array[$i];
            $array[$i] = $array[$minValIndex];
            $array[$minValIndex] = $temp;
    
            print_r($array);
        }
        return $array;
    }
    $res =  selectSort(2,9,1,8,3,8);
    var_dump($res);

### 插入排序 ###

/** * Created by PhpStorm. * User: leon * Date: 2018/3/13 * Time: 下午6:27 */
    /** * @param array ...$args * @return array * 从元素 1 开始作为插入数字 , i-1 和 i 比，换i和 i-1 位，while 再把i-2和 i-1 新的insertValue比 * 直到不满足while，或者到头 ，还需要比一下index+1是否等于当前循环次数， * 来判断是否循环超过1次，这样可以把最左边用insert补全 */
    
    function InsertSort(...$args){ 
        print_r($args);
        for ($i = 1;$i < count($args); $i++){
            $insertVal = $args[$i]; //$insertVal是准备插入的数
            var_dump($i);
            var_dump('准备插入：'.$insertVal);
            print_r('while之前');
            print_r($args);
    
            $insertIndex = $i - 1; //1
            while( $insertIndex >= 0 && $insertVal < $args[$insertIndex] ){
                var_dump('进入while');
                $args[$insertIndex + 1] = $args[$insertIndex]; //将数组往后挪
                $insertIndex--;
    
            }
            var_dump('while之后');
            print_r($args);
    
            if($insertIndex + 1 !== $i){
       //循环 > 1次时，会触发，将插入值，放在最前面
                $args[$insertIndex + 1] = $insertVal;
            }
            var_dump('if之后');
            print_r($args);
    
        }
        return $args;
    }
    
    
    (InsertSort(2,9,1,8,3,8,3,2,2));

### 快速排序 ###

/**
     * Created by PhpStorm.
     * User: leon
     * Date: 2018/3/13
     * Time: 下午4:51
     */
    
    function QuickSort($args){
    
    
        //这里要加一个限制，不然无限递归了
        if (!isset($args[1])) return $args;
    
        $mid = $args[0];//分割关键词 。小的放一个 大的放一个
        $leftArr = array();
        $rightArr = array();
    
        foreach ($args as $value){
            if ($value > $mid) $rightArr[] = $value;
            if ($value < $mid) $leftArr[] = $value;
        }
    
        $leftArr = QuickSort($leftArr);
        $leftArr[] = $mid;
        $rightArr = QuickSort($rightArr);
    
        return array_merge($leftArr,$rightArr);
    
    }
    
    $rt = array(6,3,2,8,11,1);
    print_r(QuickSort($rt));
    
    ///* //* 思路： //* 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小， //* 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 //* */
    //function quickSort1($array){
    //    if(!isset($array[1]))  return $array;
    //    $mid = $array[0]; //获取一个用于分割的关键字，一般是首个元素
    //    $leftArray = array();
    //    $rightArray = array();
    //    foreach($array as $v){
    //        if($v > $mid)
    //            $rightArray[] = $v; //把比$mid大的数放到一个数组里
    //        if($v < $mid)
    //            $leftArray[] = $v; //把比$mid小的数放到另一个数组里
    //    }
    //    $leftArray = quickSort($leftArray); //把比较小的数组再一次进行分割
    //    $leftArray[] = $mid; //把分割的元素加到小的数组后面，不能忘了它哦
    //    $rightArray = quickSort($rightArray); //把比较大的数组再一次进行分割
    //    return array_merge($leftArray,$rightArray); //组合两个结果
    //}
    //$arr= array(6,3,8,2,9,1);
    //$res = quickSort($arr);
    //var_dump($res);

### 冒泡排序 ###

/** * Created by PhpStorm. * User: leon * Date: 2018/3/13 * Time: 下午4:06 */
    
    function BubbleSort(...$args){ 
        $count = count($args);
        $temp = 0;
    
        //外层控制排序轮次
        for ($i = 0; $i < $count-1;$i++ ){
            //内层控制每轮比较次数
            for ($j = 0;$j < $count-$i-1;$j++){
                if ($args[$j] > $args[$j+1]){
                    $temp = $args[$j];
                    $args[$j] = $args[$j+1];
                    $args[$j+1] = $temp;
                }
            }
        }
        return $args;
    }
    
    print_r(BubbleSort(2323,22,2,3,5,4,2,3));

总结：  
1. 插入排序：稳定，O(n2)  
2. 冒泡排序：稳定，O(n2) 一次长度减少1  
3. 快排：不稳定。O（nlogn）最差 o（n2） ，二分排序，查找减半  
4. 选择排序：不稳定：O(n2)  
5. 归并排序：O(n log n)