快捷導(dǎo)航

Python堆排序的實(shí)現(xiàn)示例

更新時(shí)間：2023年11月06日 10:15:24 作者：Echo_Wish

堆排序是一種基于二叉堆數(shù)據(jù)結(jié)構(gòu)的排序算法,本文主要介紹了Python堆排序的實(shí)現(xiàn)示例,具有一定的參考價(jià)值,感興趣的可以了解一下

堆排序（Heap Sort）是一種基于二叉堆數(shù)據(jù)結(jié)構(gòu)的排序算法，它通過將元素構(gòu)建成一個(gè)最大堆或最小堆，然后重復(fù)從堆中移除根節(jié)點(diǎn)，直到堆為空，從而得到有序數(shù)組。堆排序是一種原地排序算法，具有穩(wěn)定的時(shí)間復(fù)雜度，通常效率較高。本文將詳細(xì)介紹堆排序的工作原理和Python實(shí)現(xiàn)。

堆排序的工作原理

堆排序的基本思想是：

構(gòu)建一個(gè)最大堆或最小堆，將數(shù)組元素視為二叉樹的節(jié)點(diǎn)。
交換堆的根節(jié)點(diǎn)（最大值或最小值）和堆的最后一個(gè)節(jié)點(diǎn)。
從堆中移除最后一個(gè)節(jié)點(diǎn)，然后維護(hù)堆的性質(zhì)。
4, 重復(fù)步驟 2 和 3，直到堆為空。
堆可以被看作是一個(gè)二叉樹，其中每個(gè)節(jié)點(diǎn)的值都大于或小于其子節(jié)點(diǎn)的值，根據(jù)堆的性質(zhì)，我們可以得到最大堆和最小堆兩種堆的排序方式。最大堆要求父節(jié)點(diǎn)的值大于等于子節(jié)點(diǎn)的值，最小堆要求父節(jié)點(diǎn)的值小于等于子節(jié)點(diǎn)的值。

下面是一個(gè)示例，演示堆排序的過程：

原始數(shù)組：[9, 6, 5, 2, 8]

構(gòu)建最大堆，得到 [9, 8, 5, 2, 6]。
交換根節(jié)點(diǎn) 9 和最后一個(gè)節(jié)點(diǎn) 6，得到 [6, 8, 5, 2, 9]。
從堆中移除節(jié)點(diǎn) 9，然后維護(hù)堆的性質(zhì)，得到 [8, 6, 5, 2]。
4, 重復(fù)步驟 2 和 3，直到堆為空。

Python實(shí)現(xiàn)堆排序

下面是Python中的堆排序?qū)崿F(xiàn)：

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)

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)

arr 是待排序的數(shù)組。
heapify 函數(shù)用于將節(jié)點(diǎn) i 下沉，以維護(hù)最大堆的性質(zhì)。
heap_sort 函數(shù)用于構(gòu)建最大堆和執(zhí)行堆排序。

示例代碼

下面是一個(gè)使用Python進(jìn)行堆排序的示例代碼：

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)

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)

# 測(cè)試排序
arr = [9, 6, 5, 2, 8]
heap_sort(arr)
print("排序后的數(shù)組:", arr)