PHP算法之四大基础算法

摘要：而在证明算法是正确的基础上，第二步就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。

虽然工作中，你觉得自己并没有涉及到算法这方面的东西，但是算法是程序的核心，一个程序的好与差，关键是这个程序算法的优劣，所以对于冒泡排序、插入排序、选择排序、快速排序这四种基本算法，我想还是要掌握的。

冒泡排序大概的意思是依次比较相邻的两个数，然后根据大小做出排序，直至最后两位数。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。

冒泡是从前往后冒，所以，每轮比较的次数也是逐渐减少的，最后一个数不用比较，其时间复杂度为O(n²)，算法如下：

/**
 * 冒泡排序算法
 * @param array $arr
 * @return array
 */
function bubble_sort($arr) {
    // 判断参数是否为数组，且不为空
    if (!is_array($arr) || empty($arr)) {
        return $arr;
    }
    // 循环需要冒泡的轮数
    for ($i = 1, $len = count($arr); $i < $len; $i++) {
        // 循环每轮需要比较的次数
        for ($j = 0; $j < $len - $i; $j++) {
            // 大的数，交换位置，往后挪
            if ($arr[$j] > $arr[$j + 1]) {
                $temp = $arr[$j + 1];
                $arr[$j + 1] = $arr[$j];
                $arr[$j] = $temp;
            }
        }
    }
    return $arr;
}

选择排序的原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；以此类推，直到所有元素均排序完毕。

选择是每一次从假定一个最小值的位置，然后用假定最小值和后面的值依次比较，找到实际的最小值来放到假定最小值的位置上，其时间复杂度也为O(n²)，算法如下：

/**
 * 选择排序法
 * @param array $arr
 * @return array
 */
function select_sort($arr) {
    // 判断参数是否为数组，且不为空
    if (!is_array($arr) || empty($arr)) {
        return $arr;
    }
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        // 假设最小数的位置
        $min = $i;
        // 用假设的最小数和$i后面的数循环比较，找到实际的最小数
        for ($j = $i + 1; $j < $len; $j++) {
            // 后面的数比假设的最小数小，替换最小数
            if ($arr[$min] > $arr[$j]) {
                $min = $j;
            }
        }
        // 假设的最小数和实际不符，交换位置
        if ($min != $i) {
            $temp = $arr[$min];
            $arr[$min] = $arr[$i];
            $arr[$i] = $temp;
        }
    }
    return $arr;
}

插入排序的原理：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

插入排序法是先将排序元素的前两个元素排序，然后将第三个元素插入已经排序好的两个元素中，所以这三个元素仍然是从小到大排序，接着将第四个元素插入，重复操作直到所有元素都排序好；其时间复杂度同样为O(n²)，算法如下：

/**
 * 插入排序法
 * @param array $arr
 * @return array
 */
function insert_sort($arr) {
    // 判断参数是否为数组，且不为空
    if (!is_array($arr) || empty($arr)) {
        return $arr;
    }
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        // 当前需要比较的临时数
        $tmp = $arr[$i];
        // 循环比较临时数所在位置前面的数
        for ($j = $i - 1; $j >= 0; $j--) {
            // 前面的数比临时数大，则交换位置
            if ($arr[$j] > $tmp) {
                $arr[$j + 1] = $arr[$j];
                $arr[$j] = $tmp;
            }
        }
    }
    return $arr;
}

快速排序法是对冒泡排序的一种改进。他的基本原理是：通过一趟排序将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行快速排序，整个排序过程可以递归进行，以达到整个序列有序的目的。

快速排序法是从数列中挑出第一个数（最后一个数）作为基准元素，然后循环所有数，和基准书比较分为左右两列，然后重复这样的步骤继续划分为左右两列，算法如下：

/**
 * 快速排序法
 * @param array $arr
 * @return array
 */
function quick_sort($arr) {
    // 判断参数是否为数组，且不为空
    if (!is_array($arr) || empty($arr)) {
        return $arr;
    }
    // 数组长度为1停止排序
    $len = count($arr);
    if ($len == 1) {
        return $arr;
    }
    // 声明左右两个空数组
    $left = $right = [];
    // 循环遍历，把第一个元素当做基准数
    for ($i = 1; $i < $len; $i++) {
        // 比较当前数的大小，并放入对应的左右数组
        if ($arr[$i] > $arr[0]) {
            $right[] = $arr[$i];
        } else {
            $left[] = $arr[$i];
        }
    }
    // 递归比较
    $left = quick_sort($left);
    $right = quick_sort($right);
    // 左右两列以及基准数合并
    return array_merge($left, [$arr[0]], $right);
}

声明一个待排序的数组，然后调用对应的排序方法即可得到返回的排序好的数组；说明一下，我这里的排序设计都是递增的，如果需要递减，需要修改一下排序算法的比较替换符就行。

// 待排序数组
$arr = [1, 4, 5, 9, 3, 8, 6];
// 调用排序方法
$sort_arr = bubble_sort($arr);
// 输出打印
print_r($sort_arr);

通常，对于一个给定的算法，我们要做两项分析：第一是从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等。而在证明算法是正确的基础上，第二步就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。还有我们通常说的：算法优化无非就是以时间换空间，以空间换时间，一般这两者是不可兼得。

实现一个程序，肯定是有多种算法的，大家有其他想说的，都可以留言和我交流，谢谢！如有问题，也欢迎指出，我会及时改正，谢谢！