python 写一段堆排序

下面是 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 heap_sort(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)

arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print(arr)

在堆排序中，我们首先将数组转换为最大堆。然后从堆的最后一个元素开始，将其与堆的根节点交换，然后重新堆化剩余的元素。重复此过程，直到所有元素都已排序。

相关问题

用python写一个堆排序

堆排序是一种基于堆的排序算法，它的时间复杂度为O(nlogn)。下面是用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 heap_sort(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]
print(heap_sort(arr))

在这段代码中，`heapify`函数用来构建最大堆，`heap_sort`函数用来排序。首先，`heap_sort`函数调用`heapify`函数来构建最大堆。然后，它从最后一个元素开始，将其与堆顶元素交换，并重新构建最大堆。最后，返回已排序的数组。

堆排序 python

堆排序是一种基于二叉堆数据结构的排序算法。下面是一个用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("排序后的数组：")
print(sorted_arr)

这段代码首先定义了两个函数，`heapify`函数用于维护最大堆的性质，`heapSort`函数则是通过调用`heapify`函数实现堆排序。

在`heapify`函数中，首先找到当前节点及其左右子节点中的最大值，并将最大值与当前节点交换位置，然后递归调用`heapify`函数来修复子树。

在`heapSort`函数中，首先构建初始最大堆，然后将堆顶元素（最大值）与末尾元素交换位置，并修复堆的性质。重复这个步骤直到堆为空，此时排序完成。

运行以上代码，将得到输出结果：

排序后的数组：
[5, 6, 7, 11, 12, 13]

这就是使用堆排序算法对给定数组进行排序的过程。希望对你有所帮助！如果还有其他问题，请随时提问。