堆排序的递归与非递归实现

堆排序（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)。