python堆排序代码

### 回答1：

很高兴回答您的问题。Python堆排序的代码如下：def heapify(arr, n, i):
largest = i # 初始化最大值
l = 2 * i + 1 # 左子节点
r = 2 * i + 2 # 右子节点

# 找出最大的节点
if l < n and arr[i] < 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[i], arr[0] = arr[0], arr[i] # 交换
heapify(arr, i, 0)

arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("排序后:")
for i in range(n):
print ("%d" %arr[i]),

### 回答2：
堆排序（Heap Sort）是一种基于二叉堆数据结构的排序算法。它的基本思想是将待排序的序列构建成一个大顶堆（或小顶堆），然后将根节点与最后一个节点交换位置，再对剩下的n-1个节点重新构建堆，依此类推，直到完成排序。

以下是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 = [9, 5, 2, 8, 3, 1, 6]
sorted_arr = heapSort(arr)
print(sorted_arr)

上述代码中，`heapify()`函数用于调整堆，保持大顶堆的性质。`heapSort()`函数首先构建大顶堆，然后通过循环将堆顶元素与最后一个元素交换，并重新调整堆，最终得到有序序列。测试代码中打印输出的是排序后的序列。

需要注意的是，在堆排序中，序列的索引是从0开始的，因此在计算左子节点和右子节点索引时需要做相应的调整。此外，最后一个非叶子节点的索引是`(n // 2 - 1)`。

### 回答3：
请看以下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)


arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
print("排序后的数组：")
for i in arr:
    print("%d" % i)

上述代码实现了堆排序算法。首先，定义了一个`heapify`函数来构建最大堆，该函数接受三个参数：`arr`表示待排序的数组，`n`表示数组的长度，`i`表示根节点的索引。`heapify`函数通过比较根节点与其左右子节点的大小关系，将最大值交换至根节点，然后递归调用`heapify`函数来对交换后的子节点进行调整。其次，定义了`heapSort`函数来实现堆排序。该函数首先将数组构建为最大堆，然后依次将堆顶元素（最大值）与最后一个元素交换，并对交换后的二叉树进行调整，重复该过程直到数组完全有序。最后，定义了一个示例数组`arr`，调用`heapSort`函数对其进行排序，并输出排序后的结果。