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

堆排序（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 arrarr = [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 + 2def 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 arrarr = [12, 11, 13, 5, 6, 7]print("Sorted array is:", heap_sort(arr))

以上代码分别给出了堆排序的递归和非递归实现方式。堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。