PHP常用的排序和查找算法

排序算法

冒泡排序

冒泡排序是一种简单的排序算法。 它多次遍历要排序的列表，每次比较相邻的两项，如果它们的顺序错误就把它们交换过来。

示例代码如下：

function bubble_sort($arr) {
    $len = count($arr);
    for($i=1; $i<$len; $i++) {
        for($j=0; $j<$len-$i; $j++) {
            if($arr[$j] > $arr[$j+1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $temp;
            }
        }
    }
    return $arr;
}

$arr = array(3, 8, 2, 1, 6, 5, 4, 7);
$arr = bubble_sort($arr);
print_r($arr);

输出结果：

Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 6
    [6] => 7
    [7] => 8
)

快速排序

快速排序也是一种常用的排序算法。 它的基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都要比另一部分的所有数据都要小，然后再按此方法分别对两部分数据进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

示例代码如下：

function quick_sort($arr) {
    $len = count($arr);
    if($len <= 1) {
        return $arr;
    }
    $mid = $arr[0];
    $left = array();
    $right = array();
    for($i=1; $i<$len; $i++) {
        if($arr[$i] > $mid) {
            $right[] = $arr[$i];
        } else {
            $left[] = $arr[$i];
        }
    }
    $left = quick_sort($left);
    $right = quick_sort($right);
    return array_merge($left, array($mid), $right);
}

$arr = array(3, 8, 2, 1, 6, 5, 4, 7);
$arr = quick_sort($arr);
print_r($arr);

输出结果：

Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 6
    [6] => 7
    [7] => 8
)

查找算法

顺序查找

顺序查找是一种简单的查找算法，它从数据的一端开始，逐个比较数据元素，以此查找所需的数据元素。时间复杂度为$O(n)$。

示例代码如下：

function sequential_search($arr, $key) {
    $len = count($arr);
    for($i=0; $i<$len; $i++) {
        if($arr[$i] == $key) {
            return $i; 
        }
    }
    return -1;
}

$arr = array(3, 8, 2, 1, 6, 5, 4, 7);
$key = 6;
$index = sequential_search($arr, $key);
echo "Value ".$key." found at index ".$index;

输出结果：

Value 6 found at index 4

二分查找

二分查找是一种高效的查找算法，前提是数据必须是有序的。算法的基本思想是先找到中间的元素进行比较，如果等于则找到，如果小于则在左边继续查找，如果大于则在右边继续查找，以此类推。时间复杂度为$O(Logn)$。

示例代码如下：

function binary_search($arr, $key) {
    $low = 0;
    $high = count($arr) - 1;
    while($low <= $high) {
        $mid = intval(($low + $high) / 2);
        if($arr[$mid] == $key) {
            return $mid;
        } elseif($arr[$mid] < $key) {
            $low = $mid + 1;
        } else {
            $high = $mid - 1;
        }
    }
    return -1;
}

$arr = array(1, 2, 3, 4, 5, 6, 7, 8);
$key = 6;
$index = binary_search($arr, $key);
echo "Value ".$key." found at index ".$index;

输出结果：

Value 6 found at index 5