阅读量:0
堆排序（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)。
