PHP 实现快速排序、桶排序、递归、二分法查找、选择排序、插入排序、冒泡排序

怼烎@ 2021-06-24 16:10 485阅读 0赞

### 冒泡排序 ###

/**
     * 冒泡排序
     * @authors Joker (njfupl@foxmail.com)
     * @date    2017-08-12 19:39:13
     * 基本思想:每次比较两个相邻得数,如果两个数的顺序与要求的顺序相反就将他们换过来;
     * 缺点:非常耗时间;
     */

代码示例:

$arr=[23,345,67,798,0,45,78,890,0,34,567,789,89,345,678,890,90,465,4564,6767,4353,2345,456,67,567,567,678,89,90,90,345,345,45,8789,788903,45345,52,34,4567,567,678,568,90];
    
    
    // echo count($arr),"<br>";
    for ($i=0; $i < count($arr)-1; $i++) {  
       // 外循环,循环的总次数就是数组长度减一次
       for ($j=0; $j < count($arr)-1-$i; $j++) {  
       	// 内循环,在每次外循环下循环,每次的循环次数是数组长度减去外循环的第几次数;
       	// 第一次外循环就要进行数组长度减一次内循环,以此循环下去
       	if ($arr[$j]>$arr[$j+1]) { 
       		// $tmp = 0;
       		$tmp = $arr[$j+1];
       		$arr[$j+1] = $arr[$j];
       		$arr[$j] = $tmp;
       	}
       }
    }
    // var_dump($arr);die;
    foreach ($arr as $v) { 
       echo $v,"<br>";
    }

### 二分法查找 ###

/**
     * 二分法查找
     * @authors Joker (njfupl@foxmail.com)
     * @date    2017-10-18 21:53:00
     * 已知一个排序好的数组和一个数,去查找数组中是否包含这个数
     */

代码示例

$arr = [
    1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,45,67,78,89,90,123,234,456,567,678,
    789,900,912,1234,2345,3456,4567,5678,6789,7890,8901,9012,12345,23456
    ]; // 查找的数组
    $x = 12345; // 要查找的数

*  递归的解决思想

*  while条件判断

### 插入排序 ###

/**
     * 插入排序
     * @authors Joker (njfupl@foxmail.com)
     * @date    2017-08-12 21:09:23
     * 假设数组的前面几位是排序好的,遍历出来数组后面的每一个元素,
     * 将这个元素和前面排序好的每一个元素进行比较,当其和所要的排序要求相反时,
     * 就将这个元素和前面的元素交换位置;
     * 我们这里从数组的第二位开始遍历,
     * 第一次拿出数组的第二个元素和第一个元素进行对比,
     * 并将它们排序好;
     * 之后要进行的就是遍历出来数组之后的元素,和他后一位进行对比
     * 实现数组的升序
     */

代码示例:

### 递归 ###

/**
     * 递归
     * @authors Joker (njfupl@foxmail.com)
     * @date    2017-08-12 21:25:46
     * 斐波那契数列
     */

代码示例:

function digui($n){ 
    	if($n==1||$n==2){ 
    		return 1;
    	}else{ 
    		$tmp = digui($n-1)+digui($n-2);
    		return $tmp;
    	}
    }
    echo digui(6);

### 选择排序 ###

/**
     * 选择排序
     * @authors Joker (njfupl@foxmail.com)
     * @date    2017-10-22 11:48:15
     * 实现数组的升序
     */

代码示例:

### 桶排序 ###

/**
     * 桶排序
     * @authors Joker (njfupl@foxmail.com)
     * @date    2017-08-12 19:21:13
     * 缺点: 浪费空间;
     * 思路: 就是将要排序的数组里面的值去占位置,
     * 使用场景: 考试分数排序,最高分是10分时,就需要使用11个桶--因为有可能有零分的,提供位置
     */

代码示例:

echo "这是桶排序法,又称基数排序法--我们实现的仅仅只是一个简易的桶排序";
    $arr = array (5,3,2,5,3,8,0,0);
    $arr1 = array(0,0,0,0,0,0,0,0,0,0,0);
    
    foreach ($arr as $v) { 
    	$arr1[$v]=$arr1[$v]+1;
    }
    foreach ($arr1 as $k => $v) { 
    	if ($v!=0){ 
    		for ($i=1; $i <=$v ; $i++) {  
    			echo $k,"<br>";
    		}
    	}
    }

### 快速排序 ###

/**
     * 快速排序
     * @authors Joker (njfupl@foxmail.com)
     * @date    2017-08-12 20:26:22
     * 基于二分法的思想:改进冒泡排序
     * 将小于和大于基数的数分别放在两边;
     * 得到两个新数组,再对两个新数组进行上述操作,最后就将数组顺序排好了;
     * 再将三个数组拼接在一起;
     *
     * 优点: 跳跃性的比较,相较于冒泡排序,这个更加的省内存
     */

代码示例:

### 基于《啊哈!算法》介绍的快速排序 ###

/**
     * 快速排序
     * @authors Joker (njfupl@foxmail.com)
     * @date    2019-01-14 09:27
     * 基于《啊哈!算法》介绍的快速排序
     */

代码示例:

/** * @param $low: 左边起点 * @param $high: 右边起点 * @param $arr: 要处理的数组 * 快速排序 递归调用 * 关键点在于part动作 */
    function qsort($low, $high, &$arr){ 
        if($low < $high){ 
            $pivot = part($low, $high, $arr);
            // 第一轮比较完之后,将数组分为左右两个数组,
            // 再次对数组左右两边进行比较---递归调用
            qsort($low, $pivot-1, $arr);
            qsort($pivot+1, $high, $arr);
        }else{ 
            return;
        }
    }
    
    /** * @param $low * @param $high * @param $arr * @return mixed * part的核心动作在于 -- 中枢点的位置不断变换, * 比它小的换到它的左边,比它大的换到它的右边 */
     
    function part($low, $high, &$arr){ 
        $pivot = $arr[$low];// 中枢点默认是列表第一个
    
        while($low < $high){ 
            while($low < $high && $arr[$high] >= $pivot){ 
            // 右边选比中枢点小的
                $high--;
            }
            swap($arr, $low, $high);
            // 此时中枢点在低位置,而此时的高位置小于中枢点。两点交换
    
            while($low < $high && $arr[$low] <= $pivot){ 
            // 左边选比中枢点大的
                $low++;
            }
            swap($arr, $low, $high);
            // 此时中枢点在高位置,而此时的低位置大于中枢点。两点交换
        }
    
        return $low;// 低位此时是中枢点,返回中枢点位置
    }
    
    /** * @param $arr * @param $i * @param $j * 交换位置 */
    function swap(&$arr, $i, $j){ 
        $temp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $temp;
    }
    $arr = array(19, 17, 13, 16,12 , 11, 4, 9, 77, 18);
    qsort(0, count($arr) - 1, $arr);