算法系列-堆排序

定义

堆排序指利用堆这种数据结构所设计的一种排序算法

  1. 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;
  2. 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;

原理

  1. 创建一个堆H[0,1,…,n-1,n]
  2. 把堆首(最大值)和堆尾互换
  3. 把堆的尺寸缩小1,并调用shif_down(0),目的时把新的数组顶端数据调整到相应位置
  4. 重复步骤2,直到堆的尺寸为1

PHP实现

PHP沙盒环境

function buildMaxHeap(&$arr)
{
    global $len;
    for ($i = floor($len/2); $i >= 0; $i--) {
        heapify($arr, $i);
    }
}

function heapify(&$arr, $i)
{
    global $len;
    $left = 2 * $i + 1;
    $right = 2 * $i + 2;
    $largest = $i;

    if ($left < $len && $arr[$left] > $arr[$largest]) {
        $largest = $left;
    }

    if ($right < $len && $arr[$right] > $arr[$largest]) {
        $largest = $right;
    }

    if ($largest != $i) {
        swap($arr, $i, $largest);
        heapify($arr, $largest);
    }
}

function swap(&$arr, $i, $j)
{
    $temp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $temp;
}

function heap_sort($arr) {
    global $len;
    $len = count($arr);
    buildMaxHeap($arr);
    for ($i = count($arr) - 1; $i > 0; $i--) {
        swap($arr, 0, $i);
        $len--;
        heapify($arr, 0);
    }
    return $arr;
}

//例子
$numbers = [1,3,4,22,88,33,31,42];
print_r(heap_sort($numbers));

Donate

Buy me a coffee, if you thought this blog does help you. Click the link below.

My Personal PayPal.

21条评论

  1. Świetny post. Bardzo ciekawie opisany artykuł. Jak możesz sprawdź stronę o samochodach u mnie! Do zobaczenia!

  2. I needed to draft you one little observation so as to say thank you as before for these gorgeous guidelines you’ve contributed at this time. It’s extremely generous of people like you in giving extensively all a few people could have distributed as an e-book in order to make some bucks for their own end, certainly considering that you could have done it if you considered necessary. The creative ideas additionally acted as the easy way to be certain that most people have a similar dream just as mine to find out a little more in regard to this condition. I’m certain there are lots of more enjoyable moments ahead for folks who discover your blog.

  3. I am also writing to make you know what a incredible encounter my friend’s girl experienced reading your site. She even learned many issues, not to mention what it’s like to have a wonderful giving mindset to have many people quite simply grasp chosen hard to do subject areas. You really exceeded our expectations. Many thanks for giving the insightful, healthy, educational and as well as easy thoughts on the topic to Jane.

  4. Thanks for your whole work on this website. My mum takes pleasure in setting aside time for research and it is simple to grasp why. We notice all relating to the powerful ways you provide very useful tips and tricks via your website and therefore strongly encourage response from visitors on this theme while our own simple princess is without a doubt understanding so much. Take pleasure in the rest of the year. Your performing a useful job.

  5. I needed to draft you one little bit of observation to finally thank you the moment again over the remarkable tactics you have shared on this page. This has been simply surprisingly open-handed with you to offer unhampered what most of us would’ve offered for sale for an ebook to help make some money on their own, precisely seeing that you might have tried it in case you desired. Those suggestions in addition worked to become good way to realize that some people have the identical keenness similar to my personal own to realize significantly more when it comes to this matter. I believe there are several more pleasant sessions up front for people who scan your site.

  6. I am just writing to make you understand what a perfect experience my wife’s girl obtained using your webblog. She noticed so many pieces, which included what it is like to possess an excellent helping spirit to let other people with no trouble learn specific specialized things. You truly surpassed readers’ expected results. Thank you for providing these priceless, trusted, informative as well as fun tips about this topic to Lizeth.

  7. I precisely desired to say thanks again. I’m not certain the things I could possibly have created without the type of secrets provided by you on such a question. It previously was a very frustrating issue in my opinion, however , observing the very specialised strategy you processed that made me to leap over gladness. I am just happy for this information and in addition hope that you know what a great job you are always getting into teaching people thru your web page. More than likely you have never got to know any of us.

  8. I am only writing to make you understand what a really good experience my wife’s princess obtained viewing your webblog. She noticed some things, which included what it is like to possess an ideal teaching spirit to make others without difficulty learn about specific tortuous things. You undoubtedly surpassed readers’ expected results. Thanks for rendering those productive, trusted, informative as well as unique tips on your topic to Mary.

  9. I am commenting to let you know of the fine encounter my friend’s daughter found reading your site. She figured out many issues, not to mention what it’s like to have a wonderful giving mindset to have men and women quite simply have an understanding of selected hard to do subject areas. You really exceeded our expectations. Many thanks for giving the insightful, safe, explanatory and as well as easy thoughts on the topic to Jane.

  10. I am glad for writing to make you know what a notable encounter my wife’s girl had studying your web site. She mastered several pieces, which include what it’s like to possess an awesome helping nature to let other individuals with ease know precisely some problematic subject matter. You truly exceeded people’s expectations. Thank you for producing these practical, trusted, informative and in addition fun tips about this topic to Kate.

  11. I’m commenting to let you be aware of of the beneficial discovery my child developed browsing the blog. She came to find a lot of details, including how it is like to have a great coaching character to get certain people completely comprehend a number of complex issues. You actually did more than her desires. I appreciate you for coming up with such effective, dependable, edifying and cool guidance on that topic to Ethel.

  12. Thank you for your entire labor on this web site. My mom take interest in managing investigations and it is obvious why. My partner and i learn all regarding the lively tactic you produce simple things through your web site and in addition invigorate response from the others on the situation then our favorite princess is truly studying a whole lot. Take advantage of the rest of the year. You have been doing a superb job.

  13. I precisely desired to say thanks again. I’m not certain the things I could possibly have accomplished in the absence of the aspects contributed by you about my area. Completely was a challenging case for me, but being able to view a expert approach you dealt with it forced me to cry for contentment. Extremely grateful for the advice and believe you are aware of a powerful job that you’re accomplishing educating many others all through a blog. I’m certain you’ve never come across all of us.

  14. Very nice post and right to the point. I don’t know if this is really the best place to ask but do you guys have any ideea where to hire some professional writers? Thanks in advance 🙂 https://livermedi.com meds for liver

  15. You got a very fantastic website, Gladiolus I detected it through google. https://asthmamedi.com best prescription drugs for asthma

  16. Helpful info. Fortunate me I found your site accidentally, and I am surprised why this twist of fate did not came about in advance! I bookmarked it. https://stomachulcersmedi.com list of stomach medications

  17. excellent put up, very informative. I ponder why the opposite specialists of this sector don’t notice this. You must proceed your writing. I’m confident, you’ve a great readers’ base already! https://anxietymedi.com over the counter Anxiety drugs

  18. Excellent website. Plenty of helpful info here. I am sending it to several friends ans additionally sharing in delicious. And certainly, thanks to your sweat! https://cancermedph.com best breast cancer drugs

发表评论

邮箱地址不会被公开。 必填项已用*标注