搜索
首页后端开发php教程php堆排序实现原理与应用程序代码_PHP教程

php堆排序实现原理与应用程序代码_PHP教程

Jul 20, 2016 am 11:08 AM
php代码原理实现应用程序排序教程

php教程堆排序实现原理与应用程序代码
author:        lajabs
email:        agl0dhlvqgdtywlslmnvbq==

本文以php作为描述语言较详细讲解堆排序原理
因保证程序可读性,故不做优化.


php程序中关于堆的一些概念:
假设n为当前数组的key则
n的父节点为 n>>1 或者 n/2(整除);
n的左子节点l= n*/
$arr=array(1,8,7,2,3,4,6,5,9);
/*
数组$arr的原形态结构如下:
             1
           /   
         8      7
       /         /
     2     3      4  6
    /
   5  9

*/
heaps教程ort($arr);
print_r($arr);
/*
排序后生成标准的小顶堆结构如下:
             1
           /  
         2      3
       /       / 
     4    5      6   7
    /
   8  9

既数组:array(1,2,3,4,5,6,7,8,9)
*/

function heapsort(&$arr)
{
        //求最后一个元素位
        $last=count($arr);
        //堆排序中通常忽略$arr[0]
        array_unshift($arr,0);
        //最后一个非叶子节点
        $i=$last>>1;

        //整理成大顶堆,最大的数整到堆顶,并将最大数和堆尾交换,并在之后的计算中忽略数组后端的最大数(last),直到堆顶(last=堆顶)
        while(true)
        {
                adjustnode($i,$last,$arr);
                if($i>1)
                {
                        //移动节点指针,遍历所有非叶子节点
                        $i--;
                }
                else
                {
                        //临界点last=1,既所有排序完成
                        if($last==1)break;
                        //当i为1时表示每一次的堆整理都将得到最大数(堆顶,$arr[1]),重复在根节点调整堆
                        swap($arr[$last],$arr[1]);
                        //在数组尾部按大小顺序保留最大数,定义临界点last,以免整理堆时重新打乱数组后面已排序好的元素
                        $last--;
                }
        }
        //弹出第一个数组元素
        array_shift($arr);
}

//整理当前树节点($n),临界点$last之后为已排序好的元素
function adjustnode($n,$last,&$arr)
{
        $l=$n        if(!isset($arr[$l])||$l>$last) return ;
        $r=$l+1;        //$n的右孩子位

        //如果右孩子比左孩子大,则让父节点的右孩子比
        if($r$arr[$l]) $l=$r;
        //如果其中子节点$l比父节点$n大,则与父节点$n交换
        if($arr[$l]>$arr[$n])               
        {
                //子节点($l)的值与父节点($n)的值交换
                swap($arr[$l],$arr[$n]);
                //交换后父节点($n)的值($arr[$n])可能还小于原子节点($l)的子节点的值,所以还需对原子节点($l)的子节点进行调整,用递归实现
                adjustnode($l,$last,$arr);
        }
}


//交换两个值
function swap(&$a,&$b)
{
        $a=$a ^ $b;        $b=$a ^ $b;        $a=$a ^ $b;
}


www.bkjia.comtruehttp://www.bkjia.com/PHPjc/444907.htmlTechArticlephp教程堆排序实现原理与应用程序代码 author: lajabs email: agl0dhlvqgdtywlslmnvbq== 本文以php作为描述语言较详细讲解堆排序原理 因保证程序可读性...
声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
PHP与Python:了解差异PHP与Python:了解差异Apr 11, 2025 am 12:15 AM

PHP和Python各有优势,选择应基于项目需求。1.PHP适合web开发,语法简单,执行效率高。2.Python适用于数据科学和机器学习,语法简洁,库丰富。

php:死亡还是简单地适应?php:死亡还是简单地适应?Apr 11, 2025 am 12:13 AM

PHP不是在消亡,而是在不断适应和进化。1)PHP从1994年起经历多次版本迭代,适应新技术趋势。2)目前广泛应用于电子商务、内容管理系统等领域。3)PHP8引入JIT编译器等功能,提升性能和现代化。4)使用OPcache和遵循PSR-12标准可优化性能和代码质量。

PHP的未来:改编和创新PHP的未来:改编和创新Apr 11, 2025 am 12:01 AM

PHP的未来将通过适应新技术趋势和引入创新特性来实现:1)适应云计算、容器化和微服务架构,支持Docker和Kubernetes;2)引入JIT编译器和枚举类型,提升性能和数据处理效率;3)持续优化性能和推广最佳实践。

您什么时候使用特质与PHP中的抽象类或接口?您什么时候使用特质与PHP中的抽象类或接口?Apr 10, 2025 am 09:39 AM

在PHP中,trait适用于需要方法复用但不适合使用继承的情况。1)trait允许在类中复用方法,避免多重继承复杂性。2)使用trait时需注意方法冲突,可通过insteadof和as关键字解决。3)应避免过度使用trait,保持其单一职责,以优化性能和提高代码可维护性。

什么是依赖性注入容器(DIC),为什么在PHP中使用一个?什么是依赖性注入容器(DIC),为什么在PHP中使用一个?Apr 10, 2025 am 09:38 AM

依赖注入容器(DIC)是一种管理和提供对象依赖关系的工具,用于PHP项目中。DIC的主要好处包括:1.解耦,使组件独立,代码易维护和测试;2.灵活性,易替换或修改依赖关系;3.可测试性,方便注入mock对象进行单元测试。

与常规PHP阵列相比,解释SPL SplfixedArray及其性能特征。与常规PHP阵列相比,解释SPL SplfixedArray及其性能特征。Apr 10, 2025 am 09:37 AM

SplFixedArray在PHP中是一种固定大小的数组,适用于需要高性能和低内存使用量的场景。1)它在创建时需指定大小,避免动态调整带来的开销。2)基于C语言数组,直接操作内存,访问速度快。3)适合大规模数据处理和内存敏感环境,但需谨慎使用,因其大小固定。

PHP如何安全地上载文件?PHP如何安全地上载文件?Apr 10, 2025 am 09:37 AM

PHP通过$\_FILES变量处理文件上传,确保安全性的方法包括:1.检查上传错误,2.验证文件类型和大小,3.防止文件覆盖,4.移动文件到永久存储位置。

什么是无效的合并操作员(??)和无效分配运算符(?? =)?什么是无效的合并操作员(??)和无效分配运算符(?? =)?Apr 10, 2025 am 09:33 AM

JavaScript中处理空值可以使用NullCoalescingOperator(??)和NullCoalescingAssignmentOperator(??=)。1.??返回第一个非null或非undefined的操作数。2.??=将变量赋值为右操作数的值,但前提是该变量为null或undefined。这些操作符简化了代码逻辑,提高了可读性和性能。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解锁Myrise中的所有内容
3 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

MinGW - 适用于 Windows 的极简 GNU

MinGW - 适用于 Windows 的极简 GNU

这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )专业的PHP集成开发工具

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

SublimeText3 英文版

SublimeText3 英文版

推荐:为Win版本,支持代码提示!

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境