06-堆排序

/**
 * 堆排序: 将元素看成完全二叉树, 先从(n/2-1)号元素到0号元素调整为大顶堆, 然后交换首尾值, 继续从0号元素调整
 * 时间复杂度: O(nlogn)
 * 空间复杂度: O(1)
 * 不稳定排序
 */
function heapSort(&$arr) {
    $length = count($arr);
    // 调整为大顶堆
    for($i = floor($length/2 -1); $i >= 0; --$i) {
        adjustHeap($arr, $i, $length);
    }

    // 循环交换首尾元素并调整为大顶堆, 直到所有元素有序
    for($j = $length - 1; $j >= 0; --$j) {
        list($arr[0], $arr[$j]) = [$arr[$j], $arr[0]];
        adjustHeap($arr, 0, $j);
    }
}

function adjustHeap(&$arr, $i, $length) {
    $temp = $arr[$i];
    // 从当前元素开始遍历左右子节点, 默认从左子节点开始遍历
    for($j = 2 * $i + 1; $j < $length; $j = 2 * $j + 1) {
        // 如果右子节点比左子节点大,则遍历右子树
        if ($j + 1 < $length && $arr[$j] < $arr[$j + 1]) {
            $j++;
        }
        // 如果当前遍历元素比当前所在子树的根大, 则将其父节点设为当前遍历元素的值
        if ($arr[$j] > $temp) {
            $arr[$i] = $arr[$j];
            $i = $j;
        }
    }
    $arr[$i] = $temp;
}

$arr = [38, 19, 29, 91, 85, 12, 41, 21];
heapSort($arr);
print_r($arr);