堆排序法排序怎么排(希尔排序法是怎么排的)
堆排序是将所有要排序的元素组成一个堆,然后不断弹出堆顶部的元素并调用函数来维护堆顺序,直到所有元素都弹出,排序完成。弹出元素序列是有序序列。
一般做法如下:
当插入一个节点时,将其放在堆的末尾(这是为了确保堆是一个完整的二叉树),然后与它的父节点进行比较,看该节点是否比它的父节点大(或小),即判断当前堆是否满足堆顺序。如果不是,请将该节点与其父节点交换。
然后,将该节点与其新的父节点进行比较,以此类推,直到该节点不再需要与其父节点进行交换。(即满足堆顺序时停止)当一个根节点被弹出(即从堆中删除)时,堆的最后一个节点被移动到头节点的位置,然后不断地将该节点与被激发的流沙节点进行比较,如果不满足堆顺序,则交换该节点,直到满足堆顺序。
扩展信息:
堆的操作
堆排序是指利用堆的数据结构设计的一种排序算法。堆是一种近乎完整的二叉树结构,同时满足堆的性质:即子节点的键值或索引总是小于(或大于)其父节点。
在堆的数据结构中,堆中的最大值总是在根节点(如果在优先级队列中使用堆,堆中的最小值是在根节点)。堆中定义了以下操作:
Max Heapify调整:调整堆末端的子节点,使子节点始终小于父节点。
构建最大堆:对堆中的所有数据重新排序。
堆排序:去掉第一个数据的根节点,做最大堆调整的递归操作。
参考文献:
搜狗-堆排序