基础算法

矫情吗；* 2023-07-10 08:19 32阅读 0赞

## 二分法查找 ##

前提是数据得有一定的顺序，从小到大或者是从大到小。采用折中的办法去查找数据，范围控制在数组区间内然后逐渐缩小范围查找。

<?php
    
    function binary_search($array, $val) {
        if (!is_array($array) || empty($array)) {
    		return $array;
    	}
        $count = count($array);
        $low = 0;
        $high = $count - 1;
        while ($low <= $high) {
            $mid = intval(($low + $high) / 2);
            if ($array[$mid] == $val) {
                return $mid;
            }
            if ($array[$mid] < $val) {
                $low = $mid + 1;
            } else {
                $high = $mid - 1;
            }
        }
        return false;
    }
    var_dump(binary_earch([1,3,5,7,9,11,12,13,14,15,18,19,20,21,22,23,24],11));

## 冒泡算法 ##

它重复地走访过要排序的元素列，依次比较两个相邻的元素，直到没有相邻元素需要交换 。

<?php
    
    function bubbleSort($arr){
        
    	if (!is_array($arr) || empty($arr)) {
    		return $arr;
    	}
    	$count = count($arr);
    	for($i = 0; $i < $count ; $i++){
    
    		for($j = 0; $j < $count - 1 - $i; $j++){
    
    			if($arr[$j] > $arr[$j + 1]){
    				$temp        = $arr[$j];
    				$arr[$j]     = $arr[$j + 1];
    				$arr[$j + 1] = $temp;
    			}
    		}
    	}
    
    	return $arr;
    }
    $arr = [20,40,60,50,80,10,30];
    var_dump(bubbleSort($arr));

## 快速排序 ##

1.设定一个分界值，通过该分界值将数组分成左右两部分。

2.将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

3.左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

4.重复上述过程。

<?php
    
    function quick_sort($arr) {
        
        if (!is_array($arr) || empty($arr)) {
    		return $arr;
    	}
    
    	$count = count($arr);
    	if ($count <= 1) {
    		return $arr;
    	}
    
    	$baseNum = $arr[0];
    	$leftArray = array(); 
    	$rightArray = array();
        
    	for ($i = 1; $i < $count; $i++) {
    		if ($baseNum > $arr[$i]) {
    			$leftArray[] = $arr[$i];
    		} else {
    			$rightArray[] = $arr[$i];
    		}
    	}
    	$leftArray = quick_sort($leftArray); 
    	$rightArray = quick_sort($rightArray); 
    	return array_merge($leftArray, array($baseNum), $rightArray);
    }
    var_dump(quick_sort([9, 5, 3, 3]));

## 选择排序 ##

思想：比较+交换

它的工作原理如下。首先在未排序序列中找到最小或者最大元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小或者最大元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。

<?php
     
    $arr = [11, 62, 1, 22, 6];
     
    function select_sort($arr) {
        if (!is_array($arr) || empty($arr)) {
    		return $arr;
    	}
    	$len = count($arr);
     
    	for ($i = 0; $i < $len - 1; $i++) {
    		$p = $i;
     
    		for ($j = $i + 1; $j < $len; $j++) {
    			$p = ($arr[$p] >= $arr[$j]) ? $p : $j;
     
    		}
    		if ($p != $i) {
    			$tmp = $arr[$p];
    			$arr[$p] = $arr[$i];
    			$arr[$i] = $tmp;
    		}
     
     
    	}
    	return $arr;
    }
     
    $arr = select_sort($arr);

冒泡算法，每次比较如果发现符合条件，就交换两个相邻的元素，两两比较。

而选择排序算法的改进在于：先并不急于调换位置，先从A\[i\]开始逐个检查，看哪个数最小就记下该数所在的位置P，等一躺扫描完毕，再把A\[P\]和A\[i\]对调，这时A\[i\]到A\[P\]中最小或者最大的数据就换到了最前面的位置。

所以，选择排序每扫描一遍数组，只需要一次真正的交换，而冒泡需要很多次。

## 插入排序法 ##

每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。

<?php
    
    function insert_sort($arr) {
    	$count = count($arr);
    	for ($i = 1; $i < $count; $i++) {
    		$temp = $arr[$i];
    		for ($j = $i - 1; $j >= 0; $j--) {
    			if ($temp < $arr[$j]) {
    				$arr[$j + 1] = $arr[$j];
    				$arr[$j] = $temp;
    			} else {
    				break;
    			}
    		}
    	}
    	return $arr;
    }
    
    $arr = array(6, 19, 26, 62, 88, 99, 18, 16, 1);
    var_dump(insert_sort($arr));

##  ##