搜索
首页后端开发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怎么把负数转为正整数php怎么把负数转为正整数Apr 19, 2022 pm 08:59 PM

php把负数转为正整数的方法:1、使用abs()函数将负数转为正数,使用intval()函数对正数取整,转为正整数,语法“intval(abs($number))”;2、利用“~”位运算符将负数取反加一,语法“~$number + 1”。

php怎么实现几秒后执行一个函数php怎么实现几秒后执行一个函数Apr 24, 2022 pm 01:12 PM

实现方法:1、使用“sleep(延迟秒数)”语句,可延迟执行函数若干秒;2、使用“time_nanosleep(延迟秒数,延迟纳秒数)”语句,可延迟执行函数若干秒和纳秒;3、使用“time_sleep_until(time()+7)”语句。

php怎么除以100保留两位小数php怎么除以100保留两位小数Apr 22, 2022 pm 06:23 PM

php除以100保留两位小数的方法:1、利用“/”运算符进行除法运算,语法“数值 / 100”;2、使用“number_format(除法结果, 2)”或“sprintf("%.2f",除法结果)”语句进行四舍五入的处理值,并保留两位小数。

php怎么根据年月日判断是一年的第几天php怎么根据年月日判断是一年的第几天Apr 22, 2022 pm 05:02 PM

判断方法:1、使用“strtotime("年-月-日")”语句将给定的年月日转换为时间戳格式;2、用“date("z",时间戳)+1”语句计算指定时间戳是一年的第几天。date()返回的天数是从0开始计算的,因此真实天数需要在此基础上加1。

php怎么替换nbsp空格符php怎么替换nbsp空格符Apr 24, 2022 pm 02:55 PM

方法:1、用“str_replace(" ","其他字符",$str)”语句,可将nbsp符替换为其他字符;2、用“preg_replace("/(\s|\&nbsp\;||\xc2\xa0)/","其他字符",$str)”语句。

php怎么判断有没有小数点php怎么判断有没有小数点Apr 20, 2022 pm 08:12 PM

php判断有没有小数点的方法:1、使用“strpos(数字字符串,'.')”语法,如果返回小数点在字符串中第一次出现的位置,则有小数点;2、使用“strrpos(数字字符串,'.')”语句,如果返回小数点在字符串中最后一次出现的位置,则有。

php字符串有没有下标php字符串有没有下标Apr 24, 2022 am 11:49 AM

php字符串有下标。在PHP中,下标不仅可以应用于数组和对象,还可应用于字符串,利用字符串的下标和中括号“[]”可以访问指定索引位置的字符,并对该字符进行读写,语法“字符串名[下标值]”;字符串的下标值(索引值)只能是整数类型,起始值为0。

php怎么读取字符串后几个字符php怎么读取字符串后几个字符Apr 22, 2022 pm 08:31 PM

在php中,可以使用substr()函数来读取字符串后几个字符,只需要将该函数的第二个参数设置为负值,第三个参数省略即可;语法为“substr(字符串,-n)”,表示读取从字符串结尾处向前数第n个字符开始,直到字符串结尾的全部字符。

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.能量晶体解释及其做什么(黄色晶体)
2 周前By尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前By尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

mPDF

mPDF

mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序,非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具,帮助Web开发人员更好地理解保护Web应用程序的过程,并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞,难度各不相同。请注意,该软件中

PhpStorm Mac 版本

PhpStorm Mac 版本

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