写个堆排序吧~

math_computer

于 2020-07-12 15:05:03 发布

阅读量129

点赞数

分类专栏：数据结构与算法

本文链接：https://blog.csdn.net/math_computer/article/details/107124847

版权

数据结构与算法专栏收录该内容

17 篇文章

订阅专栏

本文深入讲解了堆排序算法的实现细节，包括调整堆、构建最大堆及堆排序过程。通过具体示例，演示了如何使用堆排序对数组进行升序排列，为读者提供了清晰的代码实现和逐步解释。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

def tune_heap(arr, heapsize, root):
    left = 2 * root + 1
    right = left + 1
    larger = root
    if left < heapsize and arr[larger] < arr[left]:
        larger = left
    if right < heapsize and arr[larger] < arr[right]:
        larger = right
    arr[root], arr[larger] = arr[larger], arr[root]
    if larger != root:
        tune_heap(arr, heapsize, larger)


def build_max_heap(arr):
    for i in range((len(arr) - 2) // 2, -1, -1):
        tune_heap(arr, len(arr), i)


def heap_sort(arr):
    if len(arr) <= 1:
        return arr
    build_max_heap(arr)
    arr[0], arr[-1] = arr[-1], arr[0]
    for i in range(len(arr) - 2):
        tune_heap(arr, len(arr) - 1 - i, 0)
        arr[0], arr[len(arr) - 2 - i] = arr[len(arr) - 2 - i], arr[0]
    return arr

# 测试通过
arr = [2, 1, 3, 4, 5, 10, 3, 2, 9]
for i in range(len(arr) + 1):
    sorted_arr = heap_sort(arr[:i])
    print(sorted_arr)

利用堆