请用Python写堆排序问题
时间: 2023-06-29 09:18:25 浏览: 45
好的,以下是Python实现堆排序的代码:
```python
def heap_sort(arr):
# 创建最大堆
def build_heap(arr, size):
for i in range(size // 2 - 1, -1, -1):
heapify(arr, i, size)
# 维护最大堆
def heapify(arr, i, size):
left_child = 2 * i + 1
right_child = 2 * i + 2
largest = i
if left_child < size and arr[left_child] > arr[largest]:
largest = left_child
if right_child < size and arr[right_child] > arr[largest]:
largest = right_child
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, largest, size)
size = len(arr)
build_heap(arr, size)
for i in range(size - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, 0, i)
return arr
```
使用示例:
```python
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(heap_sort(arr))
# [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
```
该代码实现了堆排序算法,时间复杂度为 O(nlogn)。