用python写堆排序
时间: 2023-04-08 18:02:36 浏览: 67
可以回答这个问题。堆排序是一种高效的排序算法,它利用堆的数据结构来实现排序。在Python中,可以使用heapq模块来实现堆排序。具体实现方法可以参考以下代码:
import heapq
def heap_sort(arr):
heap = []
for i in arr:
heapq.heappush(heap, i)
sorted_arr = []
while heap:
sorted_arr.append(heapq.heappop(heap))
return sorted_arr
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = heap_sort(arr)
print(sorted_arr)
输出结果为:[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
相关问题
请用Python写堆排序问题
好的,以下是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)。
用Python写出堆排序算法
下面是Python实现的堆排序算法:
```python
def heapify(arr, n, i):
largest = i # 初始化最大元素为父节点
l = 2 * i + 1 # 左子节点
r = 2 * i + 2 # 右子节点
# 如果左子节点比父节点大,更新最大元素为左子节点
if l < n and arr[largest] < 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)
# 构建最大堆
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)
return arr
```
其中,`heapify`函数用于将一个节点及其子树调整为最大堆;`heapSort`函数用于构建最大堆并依次取出堆顶元素,直到所有元素都放入有序区间。