首页天道酬勤堆排序法排序怎么排(希尔排序法是怎么排的)

堆排序法排序怎么排(希尔排序法是怎么排的)

admin 11-28 07:02 147次浏览

堆排序是将所有要排序的元素组成一个堆,然后不断弹出堆顶部的元素并调用函数来维护堆顺序,直到所有元素都弹出,排序完成。弹出元素序列是有序序列。

一般做法如下:

当插入一个节点时,将其放在堆的末尾(这是为了确保堆是一个完整的二叉树),然后与它的父节点进行比较,看该节点是否比它的父节点大(或小),即判断当前堆是否满足堆顺序。如果不是,请将该节点与其父节点交换。

然后,将该节点与其新的父节点进行比较,以此类推,直到该节点不再需要与其父节点进行交换。(即满足堆顺序时停止)当一个根节点被弹出(即从堆中删除)时,堆的最后一个节点被移动到头节点的位置,然后不断地将该节点与被激发的流沙节点进行比较,如果不满足堆顺序,则交换该节点,直到满足堆顺序。

扩展信息:

堆的操作

堆排序是指利用堆的数据结构设计的一种排序算法。堆是一种近乎完整的二叉树结构,同时满足堆的性质:即子节点的键值或索引总是小于(或大于)其父节点。

在堆的数据结构中,堆中的最大值总是在根节点(如果在优先级队列中使用堆,堆中的最小值是在根节点)。堆中定义了以下操作:

Max Heapify调整:调整堆末端的子节点,使子节点始终小于父节点。

构建最大堆:对堆中的所有数据重新排序。

堆排序:去掉第一个数据的根节点,做最大堆调整的递归操作。

参考文献:

搜狗-堆排序

C#实现一个控制台的点餐系统NodeJS中的进程管理怎么实现
什么是冒泡排序(排序算法详解) 堆排序是什么类排序(堆排序算法属于什么算法)
相关内容