堆排序（Heap Sort）是一種利用堆的數據結構進行排序的算法。它可以分為遞歸和非遞歸兩種實現方式。

下面分別給出堆排序的遞歸和非遞歸實現代碼：

遞歸實現

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 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("Sorted array is:", heap_sort(arr))

非遞歸實現

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

    while True:
        if left < n and arr[i] < arr[left]:
            largest = left
        if right < n and arr[largest] < arr[right]:
            largest = right
        if largest == i:
            break
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest
        left = 2*i + 1
        right = 2*i + 2

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("Sorted array is:", heap_sort(arr))

以上代碼分別給出了堆排序的遞歸和非遞歸實現方式。堆排序的時間復雜度為O(nlogn)，空間復雜度為O(1)。