温馨提示×

Python堆排序怎么实现

小亿
106
2023-08-01 16:12:15
栏目: 编程语言

Python中可以使用heapq模块来实现堆排序。堆排序的主要步骤如下:

  1. 导入heapq模块。

  2. 定义堆排序函数heap_sort,该函数接收一个列表作为参数。

  3. 使用heapq.heapify()函数将列表转换为最小堆。

  4. 创建一个空列表sorted_list用于存储排序后的结果。

  5. 使用heapq.heappop()函数从堆中依次取出最小值并将其添加到sorted_list中。

  6. 返回sorted_list作为排序结果。

以下是具体实现代码:

import heapq
def heap_sort(arr):
heapq.heapify(arr)
sorted_list = []
while arr:
sorted_list.append(heapq.heappop(arr))
return sorted_list

使用示例:

arr = [4, 2, 8, 6, 5, 1, 7, 3]
sorted_list = heap_sort(arr)
print(sorted_list)

输出结果为:[1, 2, 3, 4, 5, 6, 7, 8]

0