Python堆排序是一种排序算法,它利用了堆这种数据结构来排序。堆排序的步骤如下:
Python堆排序是一种排序算法,它利用了堆这种数据结构来排序。
堆排序的步骤如下:
1. 将无序序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;
2. 将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;
3. 重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。
以下是Python实现的堆排序代码:
def heap_sort(arr):
# 构建大顶堆
for i in range(len(arr) // 2 - 1, -1, -1):
heap_adjust(arr, i, len(arr))
# 将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端
# 重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序
for j in range(len(arr) - 1, 0, -1):
arr[j], arr[0] = arr[0], arr[j]
heap_adjust(arr, 0, j)
return arr
def heap_adjust(arr, start, end):
root = start
while True:
child = root * 2 + 1
if child > end:
break
if child + 1 < end and arr[child] < arr[child + 1]:
child += 1
if arr[root] < arr[child]:
arr[root], arr[child] = arr[child], arr[root]
root = child
else:
break
本站系公益性非盈利分享网址,本文来自用户投稿,不代表码文网立场,如若转载,请注明出处
评论列表(81条)