PHP常用排序算法复习：插入、选择、冒泡与快速排序实现

排序算法核心逻辑与实现

在PHP开发中，处理小规模的一维数组排序时，掌握原生算法的实现原理有助于深入理解数据结构。以下分别介绍四种经典排序算法的代码实现及其运行逻辑。

第1步：插入排序实现

目的：演示如何通过将待排序元素逐个插入到已排序序列的正确位置来完成排序。
原理：从第二个元素开始，依次将其与前一个元素比较。若当前元素更小，则前一个元素后移，直到找到合适的位置插入。

<?php
/*
* 插入排序（一维数组）
* 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当的位置
*/
function insertSort($arr){
    if(!is_array($arr) || count($arr)==0){
        return $arr;
    }
    $count = count($arr);
    for($i=1; $i<$count; $i++){
        if(isset($arr[$i])){
            $tmp = $arr[$i]; //获取后一个元素的值
            $j = $i - 1; //获取前面的下标
            while($arr[$j] > $tmp){ //如果前面一个比后面一个大，这里是从小到大
                $arr[$j+1] = $arr[$j]; //把小的元素和前面的对换
                $arr[$j] = $tmp;
                $j--;
            }
        }
    }
    return $arr;
}
?>

第2步：选择排序实现

目的：展示如何每一趟从未排序部分选出最小元素，放到已排序部分的末尾。
原理：维护一个已排序区间和一个未排序区间。每次遍历未排序区间找到最小值，与未排序区间的第一个元素交换。

<?php
/*
* 选择排序（一维数组）
* 每一趟从待排序的数据元素中选出最小（最大）的一个元素，顺序放在已排好序的数列的最后
*/
function selectSort($arr){
    if(!is_array($arr) || count($arr) == 0){
        return $arr;
    }
    $count = count($arr);
    for($i=0; $i<$count; $i++){
        $k = $i;
        for($j=$i+1; $j<$count; $j++){
            if ($arr[$k] > $arr[$j]) {
                $k = $j; //找出最小的
            }
            if ($k != $i){
                $tmp = $arr[$i];
                $arr[$i] = $arr[$k];
                $arr[$k] = $tmp;
            }
        }
    }
    return $arr;
}
?>

第3步：冒泡排序实现

目的：演示相邻元素两两比较并交换，使较大（或较小）的元素逐步“浮”到序列末端。
原理：重复走访要排序的数列，一次比较两个元素，如果顺序错误就交换它们。每轮结束后，最大的元素会被移动到正确位置。

<?php
/*
* 冒泡排序（一维数组）
* 两两比较待排序数据元素的大小，发现两个数据元素的次序相反即进行交换
*/
function bubbleSort($array){
    $count = count($array);
    if ($count <= 0) {
        return false;
    }
    for($i=0; $i<$count; $i++){
        for($j=$count-1; $j>$i; $j--){
            if ($array[$j] < $array[$j-1]){ //比较找到的数进行交换
                $tmp = $array[$j];
                $array[$j] = $array[$j-1];
                $array[$j-1] = $tmp;
            }
        }
    }
    return $array;
}
?>

第4步：快速排序实现

目的：展示分治法在排序中的应用，通过递归提高大型数据集的处理效率（尽管PHP实现需注意内存消耗）。
原理：选择一个基准值（key），将数组分为小于基准的左半部分和大于基准的右半部分，然后递归地对两部分进行排序。

<?php
/*
* 快速排序（一维数组）
*/
function quickSort($array){
    if (count($array) <= 1){
        return $array;
    }
    $key = $array[0];
    $left_arr = array();
    $right_arr = array();
    for ($i=1; $i<count($array); $i++){
        if ($array[$i] <= $key){
            $left_arr[] = $array[$i];
        }else{
            $right_arr[] = $array[$i];
        }
    }
    $left_arr = quickSort($left_arr);
    $right_arr = quickSort($right_arr);
    return array_merge($left_arr, array($key), $right_arr);
}
?>

多维数组按值排序的方案

在实际业务中，经常需要对二维数组（如数据库查询结果集）按照特定字段的值进行排序。以下是两种常见的实现方式：自定义实现和使用PHP内置函数。

使用自定义逻辑按值排序

入口：函数 sortByVal。
动作：提取键名和对应值，对值数组进行排序（支持升序 asc 和降序 desc），同时联动更新键名的映射关系，最后重组数组。

<?php
/**
 * 按照元素的值进行排序
 * strOrder 为排列的顺序 asc 升序 desc 降序
 */
function sortByVal($arr,$strOrder='asc')
{
    if(!is_array($arr) || count($arr)==0)
    {
        return $arr;
    }
    $arrReturn = array();
    foreach($arr as $key=>$val)
    {
        $arrKey[] = $key;
        $arrVal[] = $val;
    }
    $count = count($arrVal);
    if($count)
    {
        //创建key的顺序数组
        for($key=0;$key<$count;$key++)
        {
            $arrKeyMap[$key] = $key;
        }
        //对值进行排序
        for($i=0;$i<$count;$i++)
        {
            for($j = $count-1; $j>$i;$j--)
            {
                //<从小到大排列 升降在这修改
                $bol = $strOrder == 'asc' ? $arrVal[$j]<$arrVal[$j-1] : $arrVal[$j]>$arrVal[$j-1];
                if($bol){
                    $tmp = $arrVal[$j];
                    $arrVal[$j] = $arrVal[$j-1];
                    $arrVal[$j-1] = $tmp;
                    //值的冒泡排序，引起key的数组的交互
                    $keytmp = $arrKeyMap[$j];
                    $arrKeyMap[$j] = $arrKeyMap[$j-1];
                    $arrKeyMap[$j-1] = $keytmp;
                }
            }
        }
        if(count($arrKeyMap))
        {
            foreach ($arrKeyMap as $val)
            {
                $arrReturn[] = $arrKey[$val];
            }
        }
    }
    return $arrReturn;
}
?>

使用原生函数优化排序

优势：利用PHP核心的 asort 或 arsort 函数，底层C语言实现，性能更优且代码简洁。
操作：提取指定键的值建立临时关联数组，进行排序后重置指针，再回填到原数组结构。

<?php
/**
 * 使用原生的函数进行数组按照值进行排列
 */
function arraySortByVal($arr,$keys,$type='asc'){
    $keysvalue = $new_array = array();
    foreach ($arr as $k=>$v){
        $keysvalue[$k] = $v[$keys];
    }
    if($type == 'asc'){
        asort($keysvalue);
    }else{
        arsort($keysvalue);
    }
    reset($keysvalue);
    foreach ($keysvalue as $k=>$v){
        $new_array[$k] = $arr[$k];
    }
    return $new_array;
}
?>

注意事项与总结

上述算法主要针对少量数据（如单页显示的数据量）在本机内存中进行排序。由于PHP脚本执行的开销以及多路递归/循环的性能损耗，当数据量达到万级或十万级以上时，不建议在应用层使用这些纯PHP实现的算法进行全量排序。

对于大规模数据的排序需求，最佳实践是将排序逻辑下沉至数据库层，通过MySQL等关系型数据库的索引和优化器进行处理，或者使用专门的大数据处理工具。

以上就是PHP常用排序算法的复习和详细内容，更多关于PHP开发技巧的资料请关注本站其它相关文章！