赞
踩
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。
- def heapify(arr, n, i):
- largest = i # 初始化最大值为根节点
- l = 2 * i + 1 # 左子节点的索引
- r = 2 * i + 2 # 右子节点的索引
-
- # 如果左子节点存在且大于根节点
- if l < n and arr[i] < arr[l]:
- largest = l
-
- # 如果右子节点存在且大于当前最大值
- if r < n and arr[largest] < arr[r]:
- largest = r
-
- # 如果最大值不是根节点
- if largest != i:
- arr[i], arr[largest] = arr[largest], arr[i] # 交换
- print(arr,'@') # 对每次处理过程进行输出并标记
-
- # 递归地调整受影响的子堆
- heapify(arr, n, largest)
-
-
- def heap_sort(arr):
- n = len(arr) # 获取列表长度
-
- # 构建最大堆,将数据调整为最大堆结构
- for i in range(n//2-1, -1, -1):
- heapify(arr, n, i)
- print(arr,'*')
-
- # 一个个从堆中取出元素
- print('--------------------')
- for i in range(n - 1, 0, -1):
- arr[i], arr[0] = arr[0], arr[i] # 交换
- heapify(arr, i, 0) # 将交换数据后的arr列表调整为最大堆,确保每一步都是最大堆数据结构
- print(arr,'-')
-
-
- # 测试堆排序函数
- arr = [1, 2, 3, 5, 6, 7]
- heap_sort(arr)
- print("排序后的数组:")
- print(arr)
数据处理过程:
原始列表:
arr = [1, 3, 2, 5, 4, 7]
堆型数据结构为:
构建最大堆第一步处理:
1、第一个for循环中,i =2, heapify(arr, 6, 2),运行后
2、第一个for循环中,i =1, heapify(arr, 6, 1),运行后
3、第一个for循环中,i =0, heapify(arr, 6, 0),运行后
到此第一个for循环完成,已经完成了最大堆数据的构建
开启第二个for循环,对数据进行排序的程序
1、第二个for循环 分别是5,4,3,2,1,进行遍历,
i = 5,此时最大值的索引为0,将索引5和索引值为0的项进行交换
heapify(arr, 5, 0)对arr列表的对数据进行调整,确保为最大堆
1)heapify(arr, 5, 0)
2) heapify(arr, 5, 1)-自调用
已经是最大堆数据结构
2、第二个for循环 i=4 对索引是0和4的项进行交换
1) heapify(arr, 4, 0)-递归
2) heapify(arr, 4, 1)-递归
已经完成对结构的调整,是最大堆数据结构
3、第二个for循环 i=3 对索引是0和3的项进行交换
1) heapify(arr, 3, 0)-递归
已经条整对大堆形式的数据结构
4、第二个for循环 i=2 对索引是0和2的项进行交换
1) heapify(arr, 2, 0)-递归
已经调整为最大堆形式的数据
5、4、第二个for循环 i=1 对索引是0和1的项进行交换
完成所有数据排序
输出排序完成的列表
arr[1,2,3,4,5,7]
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。