
在使用python中,你会遇到一个词,就是堆排序。那堆排序是什么呢?堆排序看字面意思是一种排序方法,那堆是什么呢?堆是一个近似完全二叉树的结构,并同时满足堆积的性质。其实堆排序是指利用堆这种数据结构所设计的一种排序算法。认识了堆排序,那你知道堆排序在python中如何实现吗?本文小编就像大家演示推排序在python的实现代码。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def heap_sort( array , n, length):
l = 2*n + 1
r = 2*n + 2
if l <= length - 1:
heap_sort( array , l, length)
if r <= length - 1:
heap_sort( array , r, length)
if l >= length:
return
index = l
if r < length and array [r] > array [l]:
index = r
if array [n] < array [index]:
array [n], array [index] = array [index], array [n]
|
测试:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | if __name__ == '__main__' :
a = input( "输入数组元素:" ).split( " " )
a = list(map(int, a))
b = a. copy ()
c = a. copy ()
for i in range(len(c)):
heap_sort(c, 0, len(c) - i)
c[0], c[len(c) - i - 1] = c[len(c) - i - 1], c[0]
print (c)
输入数组元素:4 8 3 6 7 1 5
[1, 3, 4, 5, 6, 7, 8]
Process finished with exit code 0
|
以上就是推排序在python中实现代码及测试部分,堆排序的时间复杂度为O(nlogn),是不稳定排序。如果你需要用到堆排序,可以套用上述代码哟~