堆排序:heap sort属于选择排序
堆的定义:有n个元素的序列(k1,k2...kn)满足:
1:Ki =< K2i 且 Ki =< K2i+1 (小顶堆)
或
2:Ki >= K2i 且 Ki >= K2i+1 (大顶堆)
i = (1,2,...n/2)
基本思想:
把要排序的n个数的序列组建成一个堆,将堆顶元素输出(这时,堆顶元素也即是根元素是最大或最小),然后对剩余的n-1个元素再次组建成堆,再次输出堆顶元素……
直到只有两个结点的堆,对它们进行交换,得到一个n个结点有序数列
操作:需要解决两个问题:
1:怎么建成堆
2:输出堆顶元素后,怎么对余下的n-1个元素,构成新的堆
先看第二个问题的解决:
1)将堆底元素送入堆顶(最后一个元素与堆顶交换),堆被破坏
2)将根结点与左,右子树中的最小(或最大)元素进行交换
3)若与左子树交换,若左子树的根结点不满足堆定义,重复2)
4)若与右子树交换,若右子树的根结点不满足堆定义,重复2)
5)继续对不满足堆定义的结点进行调整,直到叶子节点,堆建成
再看第一个问题,堆的建成
1)n个结点的完全二叉树,最后一个节点是第n/2个结点的子树
2)筛选从第n/2个结点为根的子树开始,将该子树建成堆
3)继续对n/2-1的结点,重复2)直到n/2-1=1
算法复杂度:
最坏情况下接近最差情况:O(n*logn)
稳定性:
不稳定
python代码:heap_sort.py
#coding:utf-8
def build_heap(l, length):
for i in range((length-1)/2, -1, -1):
adjust_heap(l, i, length)
#l是待排序数列
#s是待调整的数组元素的位置
#length是数组长度
#这是小顶堆排序
def adjust_heap(l, s, length):
tmp = l[s]
child = 2*s + 1 #左孩子结点的位置
while(child < length):
if(child+1 < length and l[child] < l[child+1]):
child += 1 #查找左右结点中最小的元素
if l[s] < l[child]:
l[s] = l[child]
s = child #重新设置s,即待调整的下一个结点的位置
child = 2*s + 1
else:
break
l[s] = tmp
def heap_sort(l, length):
#初始化堆
build_heap(l, length)
#从最后一个元素开始对序列进行调整
for i in range(length - 1, -1, -1):
tmp = l[i] #堆顶元素和堆底元素交换
l[i] = l[0]
l[0] = tmp
adjust_heap(l, 0, i) #注意此时堆的大小i
if __name__ == '__main__':
l = [3,1,5,7,2,4,9,6,10,8]
heap_sort(l, 10)
print('result:' + str(l))
分享到:
相关推荐
常用的排序算法--堆排序,通过创建堆的方法进行排序
排序算法:排序算法汇总--各类排序算法 冒泡,选择,插入,快排,归并,堆排
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
各类排序算法整理--C语言描述--本人编写 排序算法种类有: 冒泡 快速排序 堆排序 希尔排序 插入排序 选择排序 二路归并排序
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
堆排序的源程序--编译、运行成功的。 其基本算法思想参照《算法导论》。 有点编译器需去掉-system("pause");
经典排序算法 - 堆排序Heap sort序 经典排序算法 - 地精排序Gnome Sort 经典排序算法 - 奇偶排序Odd-even sort 经典排序算法 - 梳排序Comb sort 经典排序算法 - 耐心排序Patience Sorting 经典排序算法 - 珠...
最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort...选择排序:直接选择排序selectionsort,堆排序maxheapsort 插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序mergesort
详解Java常用排序算法-堆排序
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
简单的堆排序算法:以定长数组为例,动态数组等可以以此类推
排序作为最基础的算法,有选择排序,冒泡排序,插入排序,希尔排序,堆排序,快速排序,归并排续等,我会用c++写一下,欢迎交流~
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
自己看书时写的排序算法:堆排序 CPP文件
一个堆排序算法 c++写的 逻辑相同 可自行 改为java 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一...
c语言实现堆排序。代码实现的是建立大根堆
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。