PHP 堆排序

作者:yiqiu,最后更新时间:2018-02-25 12:05,访问:718

原文:http://www.upwqy.com/details/95.html



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

堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

堆排序的平均时间复杂度为Ο(nlogn)

算法步骤:

  1. 创建一个堆H[0..n-1]

  2. 把堆首(最大值)和堆尾互换;

  3. 把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置;

  4.  重复步骤2,直到堆的尺寸为1

/**
* 堆排序
*
* @param array $lists
* @return array
*/
function heap_sort(array $lists)
{
   $n = count($lists);
   build_heap($lists);
   while (--$n) {
       $val = $lists[0];
       $lists[0] = $lists[$n];
       $lists[$n] = $val;
       heap_adjust($lists, 0, $n);
       //echo "sort: " . $n . "\t" . implode(', ', $lists) . PHP_EOL;
   }
   return $lists;
}

function build_heap(array &$lists)
{
   $n = count($lists) - 1;
   for ($i = floor(($n - 1) / 2); $i >= 0; $i--) {
       heap_adjust($lists, $i, $n + 1);
       //echo "build: " . $i . "\t" . implode(', ', $lists) . PHP_EOL;
   }
   //echo "build ok: " . implode(', ', $lists) . PHP_EOL;
}

function heap_adjust(array &$lists, $i, $num)
{
   if ($i > $num / 2) {
       return;
   }
   $key = $i;
   $leftChild = $i * 2 + 1;
   $rightChild = $i * 2 + 2;

   if ($leftChild < $num && $lists[$leftChild] > $lists[$key]) {
       $key = $leftChild;
   }
   if ($rightChild < $num && $lists[$rightChild] > $lists[$key]) {
       $key = $rightChild;
   }
   if ($key != $i) {
       $val = $lists[$i];
       $lists[$i] = $lists[$key];
       $lists[$key] = $val;
       heap_adjust($lists, $key, $num);
   }
}


上一篇: PHP 希尔排序
下一篇: PHP 归并排序