Python排序算法之堆排序算法

下面是详细讲解“Python排序算法之堆排序算法”的完整攻略，包含两个示例说明。

堆排序算法

堆排序算法是一种基于二叉堆的排序算法。它的基本思想是将待排序的序列构建成一个二叉堆，然后不断将堆顶元素与堆底元素交换，再重新调整，到整个序列有序为止。

堆排序算法的Python实现

下面是一个示例代码，用于实现堆排序算法：

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)

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

这个代码定义了两个函数：heap_sort和heapify。heap_sort函数用于实现堆排序算法。它先将待排序的序列构建成一个二叉堆，然后不断将堆顶元素与堆底元素交换，再重新调整堆，直到整个序列有序为止。heapify函数用于调整堆。它接受数组arr、堆的大小n和一个索引i作参数，将以i为根节点的子树调整为一个堆。

示例1：对整数组进行排序

让我们使用堆排序算法对整数数组进行排序。我们将以下代码：

arr = [3, 2, 1, 5, 4]
heap_sort(arr)
print(arr)

这个代码使用heap_sort函数对整数数组arr进行排序。我们调用heap_sort函数，并将arr作为参数传递。最后，我们打印结果。

输出结果为：

[1, 2, 3, 4, 5]

这表示整数数组arr已经按升序排列。

示例2：对字符串数组进行排序

让我们使用堆排序算法对字符串数组进行排序。我们将以下代码：

arr = ['apple', 'banana', 'orange', 'pear', 'grape']
heap_sort(arr)
print(arr)

这个代码使用heap_sort函数对字符串数组arr进行排序。我们调用heap_sort函数，并将arr作为参数传递。最后，我们打印输出结果。

输出结果为：

['apple', 'banana', 'grape', 'orange', 'pear']

这表示字符串数组arr已经按字母顺序排列。

希望这攻略帮助你理解如何使用Python实现堆排序算法。