python排序算法-（6）堆棧排序
堆排序（Heap Sort）是一種樹形選擇排序算法，其利用了堆的性質(zhì)進(jìn)行排序。堆可以看做一個完全二叉樹，分為大根堆和小根堆。大根堆滿足父節(jié)點(diǎn)的值大于等于其子節(jié)點(diǎn)的值，小根堆滿足父節(jié)點(diǎn)的值小于等于其子節(jié)點(diǎn)的值。
堆排序的過程可以分為兩個步驟：
1. 構(gòu)建堆：將原始數(shù)組轉(zhuǎn)換為一個滿足堆性質(zhì)的堆。可以從最后一個非葉子節(jié)點(diǎn)開始，從右到
左，從下至上依次對每個節(jié)點(diǎn)執(zhí)行堆化操作，將原始數(shù)組構(gòu)建成一個堆。
2. 對堆進(jìn)行排序：將堆頂元素與待排序區(qū)間的末尾元素交換位置，然后對新的待排序區(qū)間進(jìn)行
堆化操作，直到整個數(shù)組有序。
堆排序的時(shí)間復(fù)雜度為O(nlogn)，其中堆化操作的時(shí)間復(fù)雜度為O(logn)，堆排序的空間復(fù)雜
度為O(1)。
import random
def heapify(arr, n, i):
? ?largest = i ?# 初始化最大值下標(biāo)為當(dāng)前根結(jié)點(diǎn)下標(biāo)
? ?left = 2 * i + 1
? ?right = 2 * i + 2
? ?# 如果左子項(xiàng)節(jié)點(diǎn)存在且大于當(dāng)前根結(jié)點(diǎn)的值，則更新最大值下標(biāo)為左子項(xiàng)節(jié)點(diǎn)下標(biāo)
? ?if left < n and arr[left] > arr[largest]:
? ? ? ?largest = left
? ?# 如果右子項(xiàng)節(jié)點(diǎn)存在且大于當(dāng)前根結(jié)點(diǎn)的值，則更新最大值下標(biāo)為右子項(xiàng)節(jié)點(diǎn)下標(biāo)
? ?if right < n and arr[right] > arr[largest]:
? ? ? ?largest = right
? ?# 如果最大值下標(biāo)不等于當(dāng)前根結(jié)點(diǎn)下標(biāo)，則交換兩個節(jié)點(diǎn)的值，并對被交換的子樹遞歸執(zhí)行堆化操作
? ?if largest != i:
? ? ? ?arr[i], arr[largest] = arr[largest], arr[i]
? ? ? ?heapify(arr, n, largest)
def build_max_heap(arr):
? ?n = len(arr)
? ?# 從最后一個非葉子節(jié)點(diǎn)開始，依次對每個節(jié)點(diǎn)執(zhí)行堆化操作，以構(gòu)建第一次堆
? ?for j in range(n // 2 - 1, -1, -1):
? ? ? ?heapify(arr, n, j)
def heap_sort(arr):
? ?n = len(arr)
? ?build_max_heap(arr) # 構(gòu)建第一次堆
? ?# 從末尾開始遍歷數(shù)組，每次將堆頂（最大值）放到待排序區(qū)間的末尾，并對新的堆進(jìn)行堆化操作
? ?for k in range(n - 1, 0, -1):
? ? ? ?arr[0], arr[k] = arr[k], arr[0] # 交換堆頂和數(shù)組末尾元素的值
? ? ? ?heapify(arr, k, 0) # 對新的堆執(zhí)行堆化操作
# 測試
array=random.sample(range(0, 100), 50)
print("給定的數(shù)組為:")
print(array)
heap_sort(array)
print('經(jīng)過堆排序后的數(shù)組為:')
print(array)運(yùn)行環(huán)境：python3.8
給定的數(shù)組為:
[54, 43, 0, 26, 17, 33, 93, 56, 60, 4, 51, 48, 88, 71, 75, 16, 97, 95, 77, 45, 80, 98, 36, 91, 55, 94, 13, 14, 6, 61, 3, 67, 79, 28, 23, 78, 29, 5, 39, 35, 96, 31, 49, 87, 50, 20, 66, 18, 9, 92]
經(jīng)過堆排序后的數(shù)組為:
[0, 3, 4, 5, 6, 9, 13, 14, 16, 17, 18, 20, 23, 26, 28, 29, 31, 33, 35, 36, 39, 43, 45, 48, 49, 50, 51, 54, 55, 56, 60, 61, 66, 67, 71, 75, 77, 78, 79, 80, 87, 88, 91, 92, 93, 94, 95, 96, 97, 98]
