堆排序python实现代码
时间: 2024-11-14 07:15:38 浏览: 16
Python实现堆排序.rar
堆排序是一种基于比较的排序算法,它利用了二叉堆数据结构的特点。在Python中,我们可以首先将待排序的序列构建成一个大顶堆(最大堆),然后不断地从堆顶取出最大值放到数组的末尾,再对剩余元素调整成大顶堆,直到整个数组有序。下面是Python实现堆排序的一个简单示例:
```python
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# 构建最大堆
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 一个个提取最大值并调整堆
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0] # 交换
heapify(arr, i, 0)
# 示例
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("Sorted array is", arr)
阅读全文