常见算法

1、冒泡排序

/**
 * 冒泡排序
 * @param $arr
 * @return void
 */
public function bubbleSort(&$arr): void
{
    $length = count($arr);
    for ($i = 0; $i < $length; $i++) {
        for ($j = $length - 1; $j > $i; $j--) {
            if ($arr[$j] < $arr[$j - 1]) {
                [$arr[$j], $arr[$j - 1]] = [$arr[$j - 1], $arr[$j]];
            }
        }
    }
}

2、选择排序

/**
 * 选择排序
 * @param array $arr
 * @return void
 */
function selectionSort(array &$arr): void
{
    $length = count($arr);
    // 外层循环，从数组首部开始，每完成一次循环，可确定一个元素的位置
    for ($i = 0; $i < $length - 1; $i++) {
        // 选定的最小值的索引
        $minIdx = $i;
        // 从 $i + 1 位开始循环，判断当前选定的元素是否是当次循环的最小值
        for ($j = $i + 1; $j < $length; $j++) {
            // 若出现比选定的值还小的值，则替换最小值的索引
            if ($arr[$minIdx] > $arr[$j]) {
                $minIdx = $j;
            }
        }
        // 互换数组两个位置的值
        [$arr[$i], $arr[$minIdx]] = [$arr[$minIdx], $arr[$i]];
    }
}

/**
 * 选择排序
 * @param array $arr
 * @return void
 */
function selectionSort2(array &$arr): void
{
    $length = count($arr);
    // 外层循环，从数组首部开始，每完成一次循环，依次确定数组元素的位置
    for ($i = 0; $i < $length; $i++) {
        // 从 $i + 1 位开始循环，依次判定 $arr[$i] 与 $arr[$j] 的大小
        for ($j = $i + 1; $j < $length; $j++) {
            // 若 $arr[$i] 比 $arr[$j] 大，则互换两个元素的位置
            if ($arr[$i] > $arr[$j]) {
                // 互换数组两个位置的值
                [$arr[$j], $arr[$i]] = [$arr[$i], $arr[$j]];
            }
        }
    }
}

/**
 * 插入排序
 * @param array $arr
 * @return void
 */
public function insertSort(array &$arr): void
{
    $length = count($arr);
    // 从数组首部开始排序，每完成一次循环，可确定一个元素的位置
    for ($i = 0; $i < $length - 1; $i++) {
        // 内层循环从 $i + 1 个元素开始，一位一位向前比较 // 若前面的值比自己大，则替换，直到前面的值比自己小了，停止循环
        for ($j = $i + 1; $j > 0; $j--) {
            if ($arr[$j] >= $arr[$j - 1]) {
                break;
            }
            [[$arr[$j], $arr[$j - 1]]] = [[$arr[$j - 1], $arr[$j]]];
        }
    }
}
/**
 * 插入排序
 * @param array $arr
 * @return void
 */
function insertionSort2(array &$arr): void
{
    $length = count($arr);
    // 从数组首部开始排序，每完成一次循环，可确定一个元素的位置
    for ($i = 0; $i < $length - 1; $i++) { // 从第二个元素开始，选择固定位置的值作为基准值
        $currentVal = $arr[$i + 1]; // 初始键位于选定值的前一个位置
        $preIdx = $i;
        // 拿基准值一步一步向前比较，直到基准值比前面的值小，则两值互换位置
        while ($preIdx >= 0 && $currentVal < $arr[$preIdx]) {
            $arr[$preIdx + 1] = $arr[$preIdx];
            $arr[$preIdx] = $currentVal;
            $preIdx--;
        }
    }
}

/**
 * 快速排序
 * @param $arr
 * @return void
 */
public function quickSort1(&$arr)
{
    $length = count($arr);
    if ($length <= 1) {
        return $arr;
    }
    $mid = $arr[0];
    $leftArr = [];
    $rightArr = [];
    for ($i = 1; $i < $length; $i++) {
        if ($arr[$i] < $mid) {
            $leftArr[] = $arr[$i];
        } else {
            $rightArr[] = $arr[$i];
        }
    }
    self::quickSort($leftArr);
    self::quickSort($rightArr);
    $arr = array_merge($leftArr, [$mid], $rightArr);
}