常用的排序算法

image.png

图中标红的下面代码都有实现。

<?php

/**
 * 插入排序
 *     直接插入排序
 * 交换排序
 *      快排 冒泡
 * 选择排序
 *      直接选择
 * 归并排序
 *      二路归并
 * 基数排序
 */

//直接插入排序:
// 空间复杂度O(1)  时间复杂度O(n^2)  稳定性：稳定
function insertSort($arr)
{
    for ($i = 1, $l = count($arr); $i < $l; ++$i) {
        $tmp = $arr[$i];
        $j = $i - 1;
        while ($j >= 0 && $tmp < $arr[$j]) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        if (($j + 1) != $i) {
            $arr[$j + 1] = $tmp;
        }
    }
    return $arr;
}

//快速排序（交换排序）
//时间复杂度 O (nlogn)  不稳定
function quickSort($arr)
{
    $l = count($arr);
    if ($l <= 1) return $arr;
    $base = $arr[0];
    $left = [];
    $right = [];
    for ($i = 1; $i < $l; ++$i) {
        if ($arr[$i] > $base) {
            $right[] = $arr[$i];
        } else {
            $left[] = $arr[$i];
        }
    }
    $right = quickSort($right);
    $left = quickSort($left);
    return array_merge($left, [$base], $right);
}


//冒泡排序（交换排序）
function bubble($arr)
{
    for ($i = 0, $l = count($arr); $i < $l - 1; $i++) {
        for ($j = 0; $j < $l - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $tmp;
            }
        }
    }
    return $arr;
}

//直接选择排序（选择排序 堆排序）
//时间复杂度 O（n）空间复杂度 O（1） 不稳定
function selectSort($arr)
{
    for ($i = 0, $l = count($arr); $i < $l; ++$i) {
        $p = $i;
        for ($j = $i + 1; $j < $l; ++$j) {
            if ($arr[$j] < $arr[$p]) {
                $p = $j;
            }
        }
        if ($p != $i) {
            $tmp = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }
    return $arr;
}

//归并排序
//时间复杂度 O(nlogn) 稳定
function mergeArray($arrA, $arrB)
{
    $a_i = $b_i = 0;
    $a_len = count($arrA);
    $b_len = count($arrB);
    while ($a_i < $a_len && $b_i < $b_len) {
        if ($arrA[$a_i] < $arrB[$b_i]) {
            $arrC[] = $arrA[$a_i++];
        } else {
            $arrC[] = $arrB[$b_i++];
        }
    }
    while ($a_i < $a_len) {
        $arrC[] = $arrA[$a_i++];
    }
    while ($b_i < $b_len) {
        $arrC[] = $arrB[$b_i++];
    }
    return $arrC;
}