Python 堆排序
最后更新于：2022-03-27 02:37:31
Python 堆排序
Python3 实例堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。
实例
def heapify(arr, n, i):
largest = i
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
largest = l
largest = r
arr[i],arr[largest] = arr[largest],arr[i] # 交换
n = len(arr)
for i in range(n, –1, –1):
heapify(arr, n, i)
for i in range(n–1, 0, –1):
arr[i], arr[0] = arr[0], arr[i] # 交换
heapify(arr, i, 0) arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("排序后")
for i in range(n):
print ("%d" %arr[i]),
largest = i
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i] # 交换
heapify(arr, n, largest) def heapSort(arr):
n = len(arr)
# Build a maxheap.
for i in range(n, –1, –1):
heapify(arr, n, i)
# 一个个交换元素
for i in range(n–1, 0, –1):
arr[i], arr[0] = arr[0], arr[i] # 交换
heapify(arr, i, 0) arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("排序后")
for i in range(n):
print ("%d" %arr[i]),
执行以上代码输出结果为：
排序后 5 6 7 11 12 13