百度360必应搜狗淘宝本站头条
mysql distinctjenkins官网mysql 子查询vba splitpython list sort
当前位置：网站首页 > IT技术 > 正文

PHP排序算法:计数、选择、插入、归并、快速、冒泡、希尔、堆

wptr33 2025-01-29 18:22 22 浏览

1.冒泡排序算法

//冒泡排序算法php
//author:Hengda
//$arr 待排序数组
//$mode false 正序，true倒序
function bubbleSort( &$arr, $mode ){
    //数组元素数
    $len = count( $arr );
    //生成阶梯
    for( $i = 0; $i < $len - 1; $i++ ){
        //遍历当前阶梯
        for( $j = 0; $j < $len - $i - 1; $j++ ){
            //两两向后比较
            if( $mode ? $arr[ $j ] < $arr[ $j + 1 ] : $arr[ $j ] > $arr[ $j + 1 ] ){
                //交换相邻两个值
                $temp = $arr[ $j ];
                $arr[ $j ] = $arr[ $j + 1 ];
                $arr[ $j + 1 ] = $temp;
            }
        }
    }
}

2.选择排序算法

//选择排序算法（php）
//author:Hengda
//$arr 待排序数组
//$mode false 正序，true倒序
function selectionSort( &$arr, $mode ){
    //数组元素数
    $len = count( $arr );

    for( $i = 0; $i < $len - 1; $i++ ){
        $k = $i;//初始化最大或者最小值标记

        for( $j = $i + 1; $j < $len; $j++ ){
            //arr[$i] 与后面所有元素比较，并将最大或者最小元素做标记
            if( $mode ? $arr[ $j ] > $arr[ $k ] : $arr[ $j ] < $arr[ $k ] ){
                $k = $j;
            }
        }
        //遍历完交换 arr[i] 和 后续发现的最大或者最小值
        $temp = $arr[ $i ];
        $arr[ $i ] = $arr[ $k ];
        $arr[ $k ] = $temp;
    }

    //return $arr;
}

3.插入排序算法

//插入排序算法（php）
//author:Hengda
//$arr 待排序数组
//$mode false 正序，true倒序
function insertionSort( &$arr, $mode ){
    //数组元素数
    $len = count( $arr );
    //依次向后遍历每个元素，然后依次将此元素与后续元素作对比，比其大或者小的值向后移动，最后将当前元素填入空缺中
    for( $i = 1; $i < $len; $i++ ){
        $temp = $arr[ $i ];
        //依次向前比较并向后移动比其大或者小的
        for( $j = $i-1; $j >=0 && ( $mode ? $arr[ $j ] < $temp : $arr[ $j ] > $temp ); $j-- ){
            //向后移动
            $arr[ $j + 1 ] = $arr[ $j ];
        }
        //填充空缺
        $arr[ $j + 1 ] = $temp;
    }
    //return $arr;
}

4.归并排序算法

//归并排序算法（php）
//author:Hengda
//$arr 待排序数组
//$start $len 每段待排序数据的起始位置和长度
//$mode false 正序，true倒序
function mergeSort( &$arr, $start, $len, $mode ){

    //左右分开排序
    if( $len > 4 ){

        $lstart = $start;//左侧部分起始位置
        $llen = floor( $len / 2 );//左侧部分长度
        $rstart = $lstart + $llen;//右侧部分起始位置
        $rlen = $len - $llen;//右侧部分长度

        mergeSort( $arr, 0, $lstart, $llen, $mode );
        mergeSort( $arr, 0, $rstart, $rlen, $mode );
    }

    //依次向后遍历每个元素，然后依次将此元素与后续元素作对比，比其大或者小的值向后移动，最后将当前元素填入空缺中
    for( $i = $start + 1; $i < $start + $len; $i++ ){

        $temp = $arr[ $i ];
        //依次向前比较并向后移动比其大或者小的
        for( $j = $i-1; $j >=$start && ( $mode ? $arr[ $j ] < $temp : $arr[ $j ] > $temp ); $j-- ){
            //向后移动
            $arr[ $j + 1 ] = $arr[ $j ];
        }
        //填充空缺
        $arr[ $j + 1 ] = $temp;
    }
    //return $arr;
}

5.快速排序算法

//快速排序算法（php）
//author:Hengda
//$arr 待排序数组
//$start $end 每段待排序数据的起始位置（含）和终止位置（含）
//$mode false 正序，true倒序
function quickSort( &$arr, $start, $end, $mode ){

    if( $end > $start ){

        //初始化基准值
        $baseValue = $arr[ $end ];
        $j = $start;

        //遍历整段数据元素，小于等于基准值的放在基准准直左侧（正序），大于等于基准值的放在基准值左侧（倒序）
        for( $i = $start; $i <= $end; $i ++ ){

            //与基准值作比较
            if( $mode ? $arr[ $i ] >= $baseValue : $arr[ $i ] <= $baseValue ){

                //从左端开始依次排列放置，当前排列位置为$j，把原位置的元素向后交换
                $temp = $arr[ $j ];
                $arr[ $j ] = $arr[ $i ];
                $arr[ $i ] = $temp;
                //更新下一个应排列的位置
                $j++;
            }
        }
        //循环中$j在最后的++操作并未使用，这里需要减去，使$j正确标记左右分界元素
        $j--;

        //分界元素在两端是，则靠近分界元素的一端无需再排序
        //分界元素也无需再参与排序，因为左侧的一定小于等于分界元素，右侧的也一定大于等于分界元素
        //分别对分界元素左右两侧的数据段继续排序
        if( $j > $start ) quickSort( $arr, $start, $j-1, $mode );
        if( $j < $end ) quickSort( $arr, $j+1, $end, $mode  );
    }

    //return $arr;
}

6.希尔排序算法

//希尔排序算法（php）
//author: Hengda
//$arr 待排序数组
//$mode 排序模式，true 从大到小，false从小到大
function shellSort( &$arr, $mode ){
    //$i,$j,$k循环控制变量,$temp 用于变量值交换，$gap不同分组间隙差，$len数组长度
    $i; $j; $temp; $gap = 1; $len = count( $arr );
    //计算
    while( $gap < floor( $len / 5 ) ){
        $gap = $gap * 5 + 1;
    }
    
    //遍历不同分组方案，并对每个分组方案进行排序
    for( $gap; $gap > 0; $gap = floor( $gap / 5 ) ){
        
        //以下为插入排序逻辑
        for( $i = $gap; $i < $len; $i++ ){
            
            $temp = $arr[ $i ];
            for( $j = $i - $gap; $j >= 0 && ( $mode ? $arr[ $j ] < $temp : $arr[ $j ] > $temp ); $j -= $gap  ){
                 $arr[ $j + $gap ] = $arr[ $j ];
            }
            $arr[ $j + $gap ] = $temp;
            
        } 
    }
    
    //return $arr;
}

7.堆排序算法

//堆排，堆节点下沉操作
//author: Hengda
//$arr 堆数组, $nodeNo 当前被操作节点序号, $heapLen 堆长度, $mode 排序模式，true 从大到小，false从小到大
function heapNodeSink( &$arr, $nodeNo, $heapLen ,$mode ){

    $temp;//用于交换
    $minOrMaxNodeNo;//用于标记最大或最小节点的下标

    $leftChildNo = $nodeNo * 2 + 1;
    $rightChildNo = $leftChildNo + 1;

    $minOrMaxNodeNo = $nodeNo;//标记最大或者最小节点

    //如果有左孩子，则与左孩子比较，更新最大或者最小节点标记
    if( $leftChildNo < $heapLen ){
        if( $mode ? $arr[ $leftChildNo ] < $arr[ $minOrMaxNodeNo ] : $arr[ $leftChildNo ] > $arr[ $minOrMaxNodeNo ] ){
            $minOrMaxNodeNo = $leftChildNo;
        }
    }
    //如果有右孩子，则与右孩子比较，更新最大或者最小节点标记
    if( $rightChildNo < $heapLen ){
        if( $mode ? $arr[ $rightChildNo ] < $arr[ $minOrMaxNodeNo ] : $arr[ $rightChildNo ] > $arr[ $minOrMaxNodeNo ] ){
            $minOrMaxNodeNo = $rightChildNo;
        }
    }
    //如果需要交换，则交换之
    if( $minOrMaxNodeNo != $nodeNo ){
        //交换
        $temp = $arr[ $nodeNo ];
        $arr[ $nodeNo ] = $arr[ $minOrMaxNodeNo ];
        $arr[ $minOrMaxNodeNo ] = $temp;

        heapNodeSink( $arr, $minOrMaxNodeNo, $heapLen ,$mode );
    }
    //return $arr;
}

//堆排序算法（php）
//author： Hengda
//$arr 堆数组, $mode 排序模式，true 从大到小，false从小到大
function heapSort( &$arr, $mode ){

    $i; $j; $len = count( $arr );
    //将无序数组规范为有序堆，即父总大于子，或者父总小于子
    //最后一个父节点
    $lastFatherNo = floor( $len / 2 ) - 1;
    //从最后一个父节点到第一个父节点，逐一做下沉操作
    for( $i = $lastFatherNo; $i >= 0; $i-- ){
        //下沉节点
        heapNodeSink( $arr, $i, $len ,$mode );
    }

    //将堆顶节点与 堆尾节点做交换，然后将堆长度减去1
    for( $i = $len - 1; $i > 0; $i-- ){
            //交换堆顶与堆尾
            $temp = $arr[ 0 ];
            $arr[ 0 ] = $arr[ $i ];
            $arr[ $i ] = $temp;
            //堆顶下沉操作
            heapNodeSink( $arr, 0, $i ,$mode );
    }
    //return $arr;
}

8.计数排序算法

//计数排序算法（php）由于php数组的键无序，所以统计需要ksort根据数组的键排序，所以做统计排序无意义，这几仅做实现。
//author： Hengda
//$arr 待排序数组,
//$mode 排序模式，true 从大到小，false从小到大
function countingSort( &$arr, $mode ){
    
    $len = count( $arr );

    $countArr = Array();
    //统计
    for( $i = 0; $i < $len; $i++ ){
        if( !isset( $countArr[ $arr[ $i ] ] ) ) $countArr[ $arr[ $i ] ] = 1;
        else $countArr[ $arr[ $i ] ]++;

    }

    $arr = Array();
    //根据键对统计数组排序
    $mode ? krsort( $countArr ) : ksort( $countArr );
    
    //
    foreach( $countArr as $k => $v ){
        for( $j = 0; $j < $v; $j++ ){
            $arr[] = $k;
        }
    }

    return $arr;
}

9.测试以上各排序算法

//测试排序10000个数
$total = !empty( $_GET['total'] ) && is_numeric( $_GET['total'] ) ? $_GET['total'] : 10000;
testSort( $total , true );

测试结果

---------
正在生成 10000个无序数...
生成 10000个无序数完成
快速排序：
正序耗时：0.098215103149414秒
逆序耗时：0.10160207748413秒
---------
希尔排序：
正序耗时：0.086393117904663秒
逆序耗时：0.090419054031372秒
---------
计数排序：
正序耗时：0.012665033340454秒
逆序耗时：0.014392137527466秒
---------
插入排序：
正序耗时：20.502465963364秒
逆序耗时：21.812999010086秒
---------
堆排序：
正序耗时：0.37758088111877秒
逆序耗时：0.37416315078735秒
---------
归并排序：
正序耗时：31.614189863205秒
逆序耗时：22.086561918259秒
---------
选择排序：
正序耗时：31.307014942169秒
逆序耗时：31.074548959732秒
---------
冒泡排序：
正序耗时：53.948215961456秒
逆序耗时：57.123917102814秒

以下是测试代码

//totalNum 测试排序的元素个数
//isPrintArrData 是否打印数组数据
function testSort( $totalNum, $isPrintArrData ){

    //生成测试数据
    $arr = makeData( $totalNum, $isPrintArrData );

    //1>调用测试函数，对 快速排序 算法进行测试
    testOneSortFunc( $arr, 'quickSort', ', 0, count( $arr ) - 1' , "快速排序", $isPrintArrData );
    
    //2>调用测试函数，对 希尔排序 算法进行测试
    //testOneSortFunc( $arr, 'shellSort', "", "希尔排序", $isPrintArrData );

    //3>调用测试函数，对 计数排序 算法进行测试
    testOneSortFunc( $arr, 'countingSort', "", "计数排序", $isPrintArrData );

    //4>调用测试函数，对 插入排序 算法进行测试
    testOneSortFunc( $arr, 'insertionSort', "", "插入排序", $isPrintArrData );

    //5>调用测试函数，对 堆排序 算法进行测试
    testOneSortFunc( $arr, 'heapSort', "", "堆排序", $isPrintArrData );

    //6>调用测试函数，对 归并排序 算法进行测试
    testOneSortFunc( $arr, 'mergeSort', ', 0, count( $arr ) ', "归并排序", $isPrintArrData );

    //7>调用测试函数，对 选择排序 算法进行测试
    testOneSortFunc( $arr, 'selectionSort', "", "选择排序", $isPrintArrData );

    //8>调用测试函数，对 冒泡排序 算法进行测试
    testOneSortFunc( $arr, 'bubbleSort', "", "冒泡排序", $isPrintArrData );
    
}

//
function testOneSortFunc( $arr, $funcName, $funcOtherArgv, $textName, $isPrintArrData ){

    echo "---------
";
    echo $textName."：
";

    //正序排序
    $arr1 = $arr;
    //$funcOtherArgv = ", 0, count(arr1) - 1";
    $stime = microtime( true );

    //quickSort( $arr1, 0, count( $arr ) - 1, false );
    eval( $funcName.'( $arr1'.$funcOtherArgv.", false );" );
    $etime = microtime( true );
    echo "正序耗时：".( $etime - $stime )."秒
";
    if( $isPrintArrData ){
        echo "正序排序结果：";
        echo implode( ',', $arr1 )."
";
    }

    //逆序
    $arr2 = $arr;
    //$funcOtherArgv = ", 0, count(arr1) - 1";
    $stime = microtime( true );

    //quickSort( $arr2, 0, count( $arr ) - 1, true );
    eval( $funcName.'( $arr2'.$funcOtherArgv.", true );" );
    $etime = microtime( true );
    echo "逆序耗时：".( $etime - $stime )."秒
";
    if( $isPrintArrData ){
        echo "倒序排序结果：";
        echo implode( ',', $arr2 )."
";
    }
}

//数据生成函数
function makeData( $totalNum, $isPrintArrData ){

    echo "---------
";
    echo "正在生成 " . $totalNum . "个无序数...
";

    $arr = Array();
    $i = $totalNum;
    while( $i-- ){
        $arr[] = mt_rand( 0, $totalNum );
    }

    echo "生成 " . $totalNum . "个无序数完成
";
    if( $isPrintArrData ){
        echo "原始无序数据：
";
        echo implode( ",", $arr );
    }

    return $arr;
}

/*
//生成$n个随机数组成的数组
//author:Hengda
//$n随机数个数
function makeData( $n ){
    $arr = Array();
    $i = $n;
    while( $i-- ){
        $arr[] = mt_rand( 0, $n );
    }
    return $arr;
}
*/

相关推荐

MySQL进阶五之自动读写分离mysql-proxy

自动读写分离目前，大量现网用户的业务场景中存在读多写少、业务负载无法预测等情况，在有大量读请求的应用场景下，单个实例可能无法承受读取压力，甚至会对业务产生影响。为了实现读取能力的弹性扩展，分担数据库压...

Postgres vs MySQL_vs2022连接mysql数据库

...

3分钟短文 | Laravel SQL筛选两个日期之间的记录，怎么写?

引言今天说一个细分的需求，在模型中，或者使用laravel提供的EloquentORM功能，构造查询语句时，返回位于两个指定的日期之间的条目。应该怎么写？本文通过几个例子，为大家梳理一下。学习时...

一文由浅入深带你完全掌握MySQL的锁机制原理与应用

本文将跟大家聊聊InnoDB的锁。本文比较长，包括一条SQL是如何加锁的，一些加锁规则、如何分析和解决死锁问题等内容，建议耐心读完，肯定对大家有帮助的。为什么需要加锁呢？...

验证Mysql中联合索引的最左匹配原则

后端面试中一定是必问mysql的，在以往的面试中好几个面试官都反馈我Mysql基础不行，今天来着重复习一下自己的弱点知识。在Mysql调优中索引优化又是非常重要的方法，不管公司的大小只要后端项目中用到...

MySQL索引解析(联合索引/最左前缀/覆盖索引/索引下推)

目录1.索引基础...

你会看 MySQL 的执行计划(EXPLAIN)吗?

SQL执行太慢怎么办？我们通常会使用EXPLAIN命令来查看SQL的执行计划，然后根据执行计划找出问题所在并进行优化。用法简介...

MySQL 从入门到精通(四)之索引结构

索引概述索引(index)，是帮助MySQL高效获取数据的数据结构(有序)，在数据之外，数据库系统还维护者满足特定查询算法的数据结构，这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构...

mysql总结——面试中最常问到的知识点

mysql作为开源数据库中的榜一大哥，一直是面试官们考察的重中之重。今天，我们来总结一下mysql的知识点，供大家复习参照，看完这些知识点，再加上一些边角细节，基本上能够应付大多mysql相关面试了（...

mysql总结——面试中最常问到的知识点(2)

首先我们回顾一下上篇内容，主要复习了索引，事务，锁，以及SQL优化的工具。本篇文章接着写后面的内容。性能优化索引优化，SQL中索引的相关优化主要有以下几个方面：最好是全匹配。如果是联合索引的话，遵循最...

MySQL基础全知全解!超详细无废话!轻松上手~

本期内容提醒：全篇2300+字,篇幅较长，可搭配饭菜一同“食”用，全篇无废话(除了这句)，干货满满，可收藏供后期反复观看。注：MySQL中语法不区分大小写，本篇中...

深入剖析 MySQL 中的锁机制原理_mysql 锁详解

在互联网软件开发领域，MySQL作为一款广泛应用的关系型数据库管理系统，其锁机制在保障数据一致性和实现并发控制方面扮演着举足轻重的角色。对于互联网软件开发人员而言，深入理解MySQL的锁机制原理...

Java 与 MySQL 性能优化:MySQL分区表设计与性能优化全解析

引言在数据库管理领域，随着数据量的不断增长，如何高效地管理和操作数据成为了一个关键问题。MySQL分区表作为一种有效的数据管理技术，能够将大型表划分为多个更小、更易管理的分区，从而提升数据库的性能和可...

MySQL基础篇:DQL数据查询操作_mysql 查

一、基础查询DQL基础查询语法SELECT字段列表FROM表名列表WHERE条件列表GROUPBY分组字段列表HAVING分组后条件列表ORDERBY排序字段列表LIMIT...

MySql:索引的基本使用_mysql索引的使用和原理

一、索引基础概念1.什么是索引？索引是数据库表的特殊数据结构（通常是B+树），用于...

一周热门
最近发表
标签列表
赣ICP备2024040476号-12