用PHP仿照python的一个堆排序算法代码写下来发现结果不正确,代码方面也没有排查到错误,不知道是不是哪里有逻辑错误
- python代码
def heap_sort(list):
# 创建最大堆
for start in range((len(list)-2) // 2, -1, -1):
sift_down(list,start,len(list)-1)
# 堆排序
for end in range(len(list) - 1, 0, -1):
list[0], list[end] = list[end], list[0] # 一次取出最大放入列表末尾,然后重新调整最大堆(end依次-1)
sift_down(list, 0, end-1)
return list
# 最大堆调整
def sift_down(lst, start, end):
root = start # 设置初始节点
while True:
child = 2*root + 1 # 左儿子索引,右儿子索引为child+1
if child>end:
break
if child+1 <= end and lst[child] < lst[child+1]:
child += 1 # 选取节点中的最大者
if lst[root] < lst[child]:
lst[root], lst[child] = lst[child], lst[root]
root = child # 继续判断下一节点
else:
break
- PHP代码
<?php
function heap_sort($arr){
// 创建最大堆
for ($i = floor((count($arr) - 2)/2); $i>=0; $i--){
sift_down($arr, $i, count($arr) -1);
}
// 堆排序
for ($j = count($arr)-1; $j >0; $j--){
// print_r($arr);
[$arr[0],$arr[$j]] = [$arr[$j], $arr[0]];
// $temp = $arr[0];
// $arr[0] = $arr[$j];
// $arr[$j] = $temp;
sift_down($arr, 0, $j-1);
}
return $arr;
}
# 调整堆函数
function sift_down($arr, $start, $end){
$root = $start;
while (true) {
$child = 2 * $root + 1;
if ($child > $end)
break;
if ($child + 1 <= $end && $arr[$child] < $arr[$child + 1]){
$child += 1;
}
if ($arr[$root] < $arr[$child]){
[$arr[$root], $arr[$child]] = [$arr[$child], $arr[$root]];
// $temp = $arr[$root];
// $arr[$root] = $arr[$child];
// $arr[$child] = $temp;
$root = $child;
}
else
break;
}
}
$a = [2,5,3,47,46,19,15,26,36,4,50,48,44,27,38];
echo '<pre>';
print_r(heap_sort($a));
我自己觉得应该是和上面python的代码形式和逻辑上应该是一样的,但是不知道为什么得不到正确结果,纠结了好一阵也没个头绪,希望还是有专业人士能够指教一番,感谢!