[数据结构与算法]PHP 面试（常用算法）

1、冒泡排序

基本思路：对排序记录关键字从后往前（逆序）进行多遍扫描，当发现两个相邻的关键字的次序与排序要求的规则不符时，就将两个记录进行交换。

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

2、快速排序算法

基本思路：快速排序使用分治策略来把待排序数据序列分为两个子序列；

步骤：

? ? ? ? 一、从数列中挑出一个元素，称该元素为“基准”

? ? ? ? 二、扫描一遍数列，将所有比 “基准” 小的元素排在基准前面，所有比 “基准” 大的元素排在基准后面。

? ? ? ? 三、通过递归，将各子序列划分为更小的序列，直到把小于基准值元素的子数列和大于基准值元素的子数列排序。

function quickSort($arr)
{
    $num = count($arr);
    $l = $r = 0;
    for ($i = 1; $i < $num; $i++) {
        if ($arr[$i] < $arr[0]) {
            $left[] = $arr[$i];
            $l++;
        } else {
            $right[] = $arr[$i];
            $r++;
        }
    }
    if ($l > 1) {
        $left = quickSort($left);
    }
    $new_arr = $left;
    $new_arr[] = $arr[0];
    if ($r > 1) {
        $right = quickSort($right);
    }
    for ($i = 0; $i < $r; $i++) {
        $new_arr[] = $right[$i];
    }
    // 或者 数组合并
    // return  array_merge($new_arr,$right);
    return $new_arr;
}

?3、插入排序

基本思路：在要排序的一组数中，假设前面的数已经是排好顺序的，现在要把第 n 个数插到前面的有序数中，使得这 n 个数也是排好顺序的。如此反复循环，直到全部排好顺序。

function insertSort($arr)
{
    $count = count($arr);
    for ($i = 1; $i < $count; $i++) {
        $tmp = $arr[$i];
        for ($j = $i - 1; $j >= 0; $j--) {
            // 从小到大 【<】 从大到小 【>】
            if ($tmp < $arr[$j]) {
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $tmp;
            } else {
                break;
            }
        }
    }
    return $arr;
}

4、选择排序

在要排序的一组数中，选出最小的一个数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

function selectSort($arr){
    for ($i=1;$i<count($arr);$i++){
        $p = $i;
        for ($j = $i + 1; $j < count($arr);$j++){
            if ($arr[$p] > $arr[$j]){
                $p = $j;
            }
        }
        if ($p != $i){
            $tmp = $arr[$p];
            $arr[$i] = $tmp;
            $arr[$p] = $arr[$i];
        }
    }
    return $arr;
}