文章目录堆排序堆(Heap) 排序过程 建堆操作/堆的插入操作(自底向上) 堆排序算法()调用/测试上述函数堆排序性能代码参考
选择排序简单选择排序
每一趟排序都会为A区增加一个元素,相应的B区中的元素就减少一个
L[0]L[1]L[2]…L[i]…L[n-1]
初始情况下,A区元素为0个
B区包含序列所有元素
第一趟排序开始,要计算出B区中的最小值min(1),将其调整到A区
第二趟开始
…
直到B区中只剩下一个元素,排序结束
计算min(i)交换参考代码
def swap(l, i, j):#python支持成组赋值l[i], l[j] = l[j], l[i]def selectionSort(l):"""简单选择排序,传入一个待排序列表即可完成排序(调用之)Parameters----------l : list需要排序的列表Returns-------listsorted list !"""for i in range(len(l)):to_min=ij=i+1#初始化变量指针(循环变量)while(jl[j]):to_min=jj+=1if(i!=to_min):swap(l,i,to_min)# l[to_min],l[i]=l[i],l[to_min]print("sorted res:",l)return l
性能分析稳定性堆排序
ref
is an in-place , but it is not asort.
堆排序简史堆(Heap)存储堆根据堆的定义,可以发现,堆的任意一个分支结点作为根结点的子树,也是一个堆大根堆(max-heap)[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img--44)(D:\repos\blogs\neep\408\ds\\\image-.png)]小根堆(min-heap)对比完全二叉查找树排序过程
iParent(i)= floor((i-1) / 2) 向下取整.iLeftChild(i)= 2*i + 1iRightChild(i) = 2*i + 2
In thestep,
can bein place.
【dataStructure_交换排序:简单选择排序SelectionSort/堆】Theof heaps asishere.
若以升序排序说明，把数组转换成最大堆（Max-Heap Heap），这是一种满足最大堆性质（Max-Heap ）的二叉树：对于除了根之外的每个节点i, A[(i)] ≥ A[i] 。
重复从最大堆取出数值最大的结点（把根结点和最后一个结点交换，把交换后的最后一个结点移出堆），并让残余的堆维持最大堆性质 。
主要问题维护堆 i级堆的调整(自顶向下)当被调整的堆满足某些条件的时候,执行一次,就可以使得以某个结点首的序列满足堆的性质能处理这类情况的足以应对弹出最大元素()或者说和堆底最后一个未排序元素交换位置)后执行的调整维护堆性质的操作 那么能不能处理其他问题堆的调整算法(/)
现在,我们来实现这个堆的调整算法(使得它具有执行一次调整的能力)
def heapify(l, k=1, end=0):"""由于完全二叉树的结点的双亲孩子结点编号计算公式依赖于编号的非0性因此,这里的起点k必须是非0的我们的数组第一个位置要空出来,(可以充当备份被筛选元素)Parameters----------l : 需要调整(heapify的序列)不是任何序列都可以一次性就可以调整成功,但是最坏的情况下,也只需要最多有限次调整就可以将任意的序列调整成堆如果将一个序列理解成:非堆区A+堆区B,在序列中B区是后一个区域,通过反复调整,B区逐渐扩大A区逐渐减小,直到B区包含了全序列的所有元素,那么建堆就完成了除非是在堆排序中的弹出堆定(交换)引起的被破坏这类的情况,才可以一次调用就修复堆的性质k : int, optional_description_, by default 1end : int, optional对序列中的前end个元素(有意义的关键字)进行heapify调整, by default 0,如果不传值,那么内部会默认计算全部全l序列的长度如果传值,那么将以传入的非0值为准那么每次调用的heapify的范围是l[k]~l[end]对于大根堆升序排序,默认总是让k=1即可,但是end在heapSort中调用来调整堆的时候,取值从堆的最后一个分支结点编号逐渐减小2Returns-------listheapified list"""end= len(l)-1if end==0 else end# print("heapify len:",end)bak_k = l[k]i = 2 * k#左孩子节点while (i