堆排序php

关于堆排序的理论网上有许多,就不多做解释,一般在非常大的数据集中,按排序获取前面一段排序结果,使用堆排序。
堆排序的时间复杂度为:O(nlogn);
空间复杂度为常数:O(1)

/**
 * 堆排序
 * @param array $ary 待排序输入
 * @param $func $大顶堆func 或者 $小顶堆func
 * @param int $num 结果数量,比如说获取最小前10个数,默认返回所有排序
 * @return array
 */
function mysort($ary, $func, $num = 0)
{
    $length = count($ary);
    $_ = 0;
    while ($_++ < $num) {
        if ($length == 1) {
            break;
        }
        for ($index = floor($length / 2) - 1; $index >= 0; $index--) {
            if ($length - 1 >= (2 * $index + 2)) {
                $func($ary[$index], $ary[2 * $index + 1], $ary[2 * $index + 2]);
            } else {
                $func($ary[$index], $ary[2 * $index + 1]);
            }
        }

        list($ary[0], $ary[$length-1]) = [$ary[$length-1], $ary[0]];
        $length--;
    }
    return $num < count($ary) ? array_slice($ary, -$num) : $ary;
}

$大顶堆func = function (&$a1, &$a2, &$a3 = null) {
    if ($a1 < $a2) {
        list($a2, $a1) = [$a1, $a2];
    }

    if (!is_null($a3)) {
        if ($a1 < $a3) {
            list($a1, $a3) = [$a3, $a1];
        }
    }
};

$小顶堆func = function (&$a1, &$a2, &$a3 = null) {
    if ($a1 > $a2) {
        list($a2, $a1) = [$a1, $a2];
    }

    if (!is_null($a3)) {
        if ($a1 > $a3) {
            list($a1, $a3) = [$a3, $a1];
        }
    }
};

$ary = [ 1, 0, 2,10,8,21,3,6,7,5,11,121,43,-1];
$res = mysort($ary, $小顶堆func, 7);
echo print_r($res);
此条目发表在php, php函数集分类目录,贴了标签。将固定链接加入收藏夹。

发表评论

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

看不清?