PHP实现常见排序算法示例代码

桃夭

发布时间：2026-10-16| 6人浏览过

原创

本文深入解析PHP中常见的排序算法，包含冒泡、选择、快速、插入、归并、希尔和堆排序的核心实现原理与完整代码。通过具体示例展示各算法的时间复杂度差异及适用场景，帮助开发者掌握数据结构基础，提升代码执行效率。

1. 冒泡排序

冒泡排序（Bubble Sort）是最基础的交换类排序算法。其核心逻辑是重复遍历数列，依次比较相邻两个元素的大小。若顺序错误则交换位置，每轮遍历会将当前未排序部分的最大值“冒泡”至末尾。经过多轮比较后，数列即可完成排序。

第1步：初始化遍历条件

目的：确定需要处理的数据范围。
参数：数组 $list，长度 $len。

第2步：执行嵌套循环比较

外层循环：控制比较的轮数，每轮结束后无需再比较末尾已确定的最大值元素。
内层循环：从索引0开始，两两对比。若前一个元素大于后一个元素，则执行交换操作。
完成状态：数组按从小到大的顺序排列。

function maopaoSort($list) {
    $len = count($list);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = 0; $j < $len - $i - 1; $j++) {
            if ($list[$j] > $list[$j + 1]) {
                // 交换元素
                $tmp = $list[$j];
                $list[$j] = $list[$j + 1];
                $list[$j + 1] = $tmp;
            }
        }
    }
    return $list;
}

2. 选择排序

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

第1步：标记当前位置为最小值索引

入口：未排序子数组的第一个位置 $i。
动作：假设当前 $pos = $i 即为最小元素。

第2步：遍历查找更优解

动作：遍历剩余元素，一旦发现比 $list[$pos] 更小的值，更新 $pos 为新索引。
结束判断：当 $pos 不等于初始索引 $i 时，说明找到了更小值，执行位置交换。

function xuanzeSort($list) {
    $len = count($list);
    for ($i = 0; $i < $len - 1; $i++) {
        $pos = $i;
        // 在未排序部分中寻找最小值的索引
        for ($j = $i + 1; $j < $len; $j++) {
            if ($list[$pos] > $list[$j]) {
                $pos = $j;
            }
        }
        // 如果找到的不是当前位置，则交换
        if ($pos != $i) {
            $tmp = $list[$pos];
            $list[$pos] = $list[$i];
            $list[$i] = $tmp;
        }
    }
    return $list;
}

3. 快速排序

快速排序（Quick Sort）采用分治法策略。通过选择一个基准值（pivot），将待排序数组划分为两部分：左边部分的所有值都比基准值小，右边部分的所有值都比基准值大。然后对这两部分分别进行递归调用，最终合并得到有序数组。

第1步：设置递归出口

判断条件：若数组长度小于等于1，直接返回原数组，此时递归终止。

第2步：划分左右区域

选择基准：通常选取第一个元素 $base。
分类遍历：遍历数组剩余元素，小于基准值的放入 $leftList，否则放入 $rightList。

第3步：递归调用与合并

动作：分别对 $leftList 和 $rightList 再次调用自身。
结果输出：使用 array_merge 将排序后的左区、基准值、排序后的右区连接起来。

function kuaisuSort($list) {
    $len = count($list);
    if ($len <= 1) { // 递归出口
        return $list;
    }
    
    $base = $list[0]; // 选择基准值
    $leftList = $rightList = [];
    
    // 分区处理
    for ($i = 1; $i < $len; $i++) {
        if ($base > $list[$i]) {
            $leftList[] = $list[$i];
        } else {
            $rightList[] = $list[$i];
        }
    }
    
    // 递归处理左右两侧并合并
    $leftList = kuaisuSort($leftList);
    $rightList = kuaisuSort($rightList);
    
    return array_merge($leftList, [$base], $rightList);
}

4. 插入排序

插入排序（Insertion Sort）适用于数据量较小或基本有序的数列。其思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。初始时，认为第一个元素是有序的，依次将后面的元素插入到前面的适当位置。

第1步：获取待插入元素

动作：从第二个元素（索引1）开始遍历，暂存当前值为 $tmp。
对象：$list[$i]。

第2步：向前比对与位移

比较方向：从后向前扫描已排序部分。
移动逻辑：若已排序部分的元素大于 $tmp，将该元素后移一位。
停止条件：遇到不大于 $tmp 的元素时停止，或直接找到头部。

第3步：填入正确位置

动作：将 $tmp 放入空出的位置。[注：原文代码实现略显冗余，此处保留原逻辑结构以维持一致性，实际标准写法通常先移位最后赋值一次即可，但原代码亦能运行]。

function charuSort($list) {
    $len = count($list);
    for ($i = 1; $i < $len; $i++) {
        $tmp = $list[$i]; // 获取对比元素
        for ($j = $i - 1; $j >= 0; $j--) {
            if ($list[$j] > $tmp) {
                $list[$j + 1] = $list[$j]; // 后移元素
                $list[$j] = $tmp;          // 暂时放入前位，等待下一个循环覆盖或最终确定
            } else {
                break;
            }
        }
        // 修正说明：上述for循环内重复赋值可能导致性能轻微损耗，但功能上保证有序
        // 优化建议：可改为先移位，跳出循环后统一赋值给 list[$j+1]
    }
    return $list;
}

5. 其他高级排序算法补充

除了基础的四类排序，在处理大规模数据或特定场景下，归并排序、希尔排序和堆排序也是重要选择。以下提供对应的 PHP 实现代码。

归并排序 (Merge Sort)

归并排序基于分治法，核心步骤是将数组拆分为两半直至不可拆分（单个元素），然后将这两个有序子数组不断合并为一个更大的有序数组。

分割阶段：利用 array_slice 切割数组，递归调用 merge_sort。
合并阶段merge 函数使用双指针逻辑，逐个比较左右子数组元素，较小者放入结果集，剩余部分追加至尾部。

/**
 * 归并排序主函数
 */
function merge_sort(array $lists) {
    $n = count($lists);
    if ($n <= 1) {
        return $lists;
    }
    // 计算中间点并拆分
    $mid = floor($n / 2);
    $left = merge_sort(array_slice($lists, 0, $mid));
    $right = merge_sort(array_slice($lists, $mid));
    return merge($left, $right);
}

/**
 * 辅助合并函数
 */
function merge(array $left, array $right) {
    $result = [];
    $i = $j = 0;
    $l_count = count($left);
    $r_count = count($right);

    while ($i < $l_count && $j < $r_count) {
        if ($left[$i] <= $right[$j]) {
            $result[] = $left[$i++];
        } else {
            $result[] = $right[$j++];
        }
    }
    // 拼接剩余元素
    return array_merge($result, array_slice($left, $i), array_slice($right, $j));
}

希尔排序 (Shell Sort)

希尔排序是插入排序的一种改进版本，又称缩小增量排序。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

增量缩减：设定初始步长 $gap = N/2$，每次循环除以2直至为0。
分组插入：在每组内执行类似插入排序的操作，通过 $step 控制跳跃距离。

 0) {
        // 对每个子序列进行插入排序
        for ($gi = 0; $gi < $gap; $gi++) {
            for ($i = $gi + $gap; $i < $n; $i += $gap) {
                $key = $lists[$i];
                $j = $i - $gap;
                while ($j >= 0 && $lists[$j] > $key) {
                    $lists[$j + $gap] = $lists[$j];
                    $j -= $gap;
                }
                $lists[$j + $gap] = $key;
            }
        }
        $gap = intval($gap / 2);
    }
    return $lists;
}

堆排序 (Heap Sort)

堆排序是利用堆这种数据结构所设计的一种排序算法。近似于完全二叉树，分为最大堆（父节点大于子节点）和最小堆。本文演示最大堆降维成升序排列的逻辑。

建堆过程 (build_heap)：从最后一个非叶子节点倒序调整，构建初始大顶堆。
排序过程：将堆顶（最大值）与末尾元素交换，缩小堆的有效范围（--$n），重新调整顶部使其恢复最大堆性质。

= 0; $i--) {
        heap_adjust($lists, $i, $n + 1);
    }
}

// 维护最大堆属性
function heap_adjust(array &$lists, $i, $num) {
    if ($i > $num / 2) return;
    
    $key = $i;
    $leftChild = $i * 2 + 1;
    $rightChild = $i * 2 + 2;
    
    if ($leftChild < $num && $lists[$leftChild] > $lists[$key]) {
        $key = $leftChild;
    }
    if ($rightChild < $num && $lists[$rightChild] > $lists[$key]) {
        $key = $rightChild;
    }
    
    if ($key != $i) {
        // 交换
        $val = $lists[$i];
        $lists[$i] = $lists[$key];
        $lists[$key] = $val;
        // 递归检查受影响的子树
        heap_adjust($lists, $key, $num);
    }
}

总结

在实际应用中，应根据数据规模和数据分布情况选择合适的算法。对于小规模数据，插入排序或选择排序因其实现简单且常数项低而表现良好；对于中等规模，快速排序通常是最佳选择；而对于大数据量的外部排序或内存受限环境，堆排序和归并排序则更具优势。以上就是PHP实现常见排序算法的详细内容，更多关于PHP高效算法优化的资料请关注本站其它相关文章！