python堆排序算法怎么實(shí)現(xiàn)

131次閱讀

共計(jì) 921 個(gè)字符，預(yù)計(jì)需要花費(fèi) 3 分鐘才能閱讀完成。

堆排序算法的實(shí)現(xiàn)步驟如下：

構(gòu)建最大堆（Max Heap）：首先將待排序的序列構(gòu)建成一個(gè)最大堆。從最后一個(gè)非葉子節(jié)點(diǎn)開始，依次將當(dāng)前節(jié)點(diǎn)與其子節(jié)點(diǎn)進(jìn)行比較，如果當(dāng)前節(jié)點(diǎn)的值小于子節(jié)點(diǎn)的值，則將兩者交換位置，并繼續(xù)比較下一個(gè)子節(jié)點(diǎn)，直到當(dāng)前節(jié)點(diǎn)的值大于或等于其子節(jié)點(diǎn)的值。
將堆頂元素與數(shù)組末尾元素交換位置：將堆頂元素與數(shù)組最后一個(gè)元素進(jìn)行交換。這樣，最大的元素就排在了數(shù)組的末尾。
重新調(diào)整剩余元素，使其滿足最大堆的性質(zhì)：將剩余的元素重新調(diào)整為最大堆。重復(fù)步驟 1 和步驟 2，直到所有元素都排序完畢。

下面是 Python 代碼的實(shí)現(xiàn)：

def heapify(arr, n, i):
    largest = i  # 初始化最大元素的索引 
    left = 2 * i + 1  # 左子節(jié)點(diǎn)的索引 
    right = 2 * i + 2  # 右子節(jié)點(diǎn)的索引 

    # 如果左子節(jié)點(diǎn)存在且大于根節(jié)點(diǎn)，則將最大元素索引設(shè)為左子節(jié)點(diǎn)的索引 
    if left < n and arr[i] < arr[left]:
        largest = left

    # 如果右子節(jié)點(diǎn)存在且大于當(dāng)前最大元素，則將最大元素索引設(shè)為右子節(jié)點(diǎn)的索引 
    if right < n and arr[largest] < arr[right]:
        largest = right

    # 如果最大元素索引發(fā)生了變化，則將當(dāng)前根節(jié)點(diǎn)和最大元素交換位置，并繼續(xù)調(diào)整以確保最大堆結(jié)構(gòu) 
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


def heapSort(arr):
    n = len(arr)

    # 構(gòu)建最大堆，從最后一個(gè)非葉子節(jié)點(diǎn)開始 
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 依次將堆頂元素與數(shù)組末尾元素交換，并重新調(diào)整堆 
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 交換堆頂元素和尾部元素 
        heapify(arr, i, 0)

    return arr


# 測(cè)試 
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heapSort(arr)
print(" 排序結(jié)果:", sorted_arr)