117.info
人生若只如初见

python堆排序算法怎么实现

堆排序算法的实现步骤如下:

  1. 构建最大堆(Max Heap):首先将待排序的序列构建成一个最大堆。从最后一个非叶子节点开始,依次将当前节点与其子节点进行比较,如果当前节点的值小于子节点的值,则将两者交换位置,并继续比较下一个子节点,直到当前节点的值大于或等于其子节点的值。
  2. 将堆顶元素与数组末尾元素交换位置:将堆顶元素与数组最后一个元素进行交换。这样,最大的元素就排在了数组的末尾。
  3. 重新调整剩余元素,使其满足最大堆的性质:将剩余的元素重新调整为最大堆。重复步骤1和步骤2,直到所有元素都排序完毕。

下面是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 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[i], arr[0] = arr[0], arr[i]  # 交换堆顶元素和尾部元素
        heapify(arr, i, 0)

    return arr


# 测试
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heapSort(arr)
print("排序结果:", sorted_arr)

输出结果:[5, 6, 7, 11, 12, 13]

未经允许不得转载 » 本文链接:https://www.117.info/ask/fe90cAzsLBQNeDFU.html

推荐文章

  • linux的python如何进行进程管理

    在Linux中,可以使用Python的内置库os和subprocess进行进程管理 使用os.system()执行外部命令: import os # 执行外部命令,例如:ls
    os.system("ls") 使用...

  • linux的python怎样进行系统调用

    在Linux中,Python可以通过os和sys库进行系统调用 使用os库: os库提供了许多与操作系统交互的函数。例如,要使用os.system()执行系统命令,可以这样做:
    i...

  • python中set怎样进行集合排序

    在Python中,可以使用sorted()函数对集合(set)进行排序。sorted()函数返回一个排序后的列表(list),而不是集合,因为集合本身是无序的。以下是一个示例:

  • python中set如何进行集合转换

    在Python中,可以使用集合(set)的内置方法进行集合转换。以下是一些常用的集合转换方法: 将列表转换为集合: my_list = [1, 2, 3, 4, 5]
    my_set = set(m...

  • java签名实现的方式有哪些

    Java签名实现的方式有以下几种: 数字签名:使用非对称加密算法,如RSA或DSA,生成一个数字签名,用于验证数据的完整性和认证发送者的身份。
    消息认证码(M...

  • spring加载过程和初始化方法是什么

    Spring加载过程分为以下几个阶段: 资源定位:Spring框架会根据配置文件或注解扫描的方式,定位到配置文件或类文件的位置。
    资源加载:Spring框架会加载配置...

  • string数组长度如何获取

    要获取字符串数组的长度,可以使用数组的length属性。例如,如果有一个名为arr的字符串数组,则可以使用arr.length来获取数组的长度。以下是一个示例:
    Str...

  • 怎么用python抓取游戏数据

    要使用Python抓取游戏数据,你可以按照以下步骤进行操作: 导入所需的库,例如requests和BeautifulSoup: import requests
    from bs4 import BeautifulSoup ...