尝试使用Python实现Introsort。在
给出的伪代码是:
1 n ←|A|
2 if n ≤ 1
3 return
4 elseif d = 0
5 Heap-Sort(A)
6 else
7 p ← Partition(A) // Partitions A and returns pivot position
8 Intro-Sort(A[0:p],d−1)
9 Intro-Sort(A[p+1:n],d−1)
我的源代码是:
^{pr2}$给出的结果是错误的:
>python introsort.py
[3, 5, 6, 1, 15, 7, 21, 632, 123, 53, 62, 421, 23, 672, 521, 435, 6243]
在子列表上排序似乎停止了,而且在子列表上也没有停止工作。很明显,21是轴心,隔板工作得很好。在
谁能指出我的错误吗?非常感谢你!在
删除
并插入
^{pr2}$完整代码:
另外,请参阅关于Python中引用的答案https://stackoverflow.com/a/986145/9210255
实际上,我通过使用一个helper函数来修复这个问题,该函数对列表的一部分调用heapsort。我没有通过修改堆排序函数来完成,而是在单独的副本中执行此操作,并将排序后的元素更新回原始列表中。代码显示为:
通过以下测试,它运行良好:
^{pr2}$给予:
相关问题 更多 >
编程相关推荐