引言
推排序常常应用在操作系统的任务调度中，尝试使用硬件对堆排序进行实现，在实现的过程中不使用function和tasks语法，即真·硬件实现
参考的博客
也就这一个博客有介绍
堆排序的Verilog实现
原理
堆排序还需要复习一遍吗? 我肯定是要的
菜鸟-堆排序
图解排序算法(三)之堆排序
可以看到，推排序很复杂，所以我们需要祭出我们的FSM(有限状态机)
首先，将整个堆排序分为两个阶段：
- 构建大根堆或小根堆
- 从最后一个节点开始，和根节点交换，并维护大根堆
我们这里统一构建大根堆
大根堆的构建
直接上流程：
- 从第一个非叶子节点开始，读取左右孩子的值；
- 比较大小，确定是否需要交换，以及交换的数据；
- 写入或不写入，如果这个节点是根节点，那么构建结束。
还是很简单的，就是需要在读写时注意控制，以及节点编号的判断与更改
交换数据，进行排序
流程如下：
- 从最后一个节点开始；
- 交换根节点和这个节点的值；
- 维护大根堆
3.1 从根节点开始，读取左右孩子的值；
3.2 比较大小，确定是否需要交换，以及交换的数据；
3.3 写入或不写入，如果这个节点是叶子节点，那么维护结束。
- 如果这个节点已经是根节点，排序结束。
我们可以发现在这个第三步和之前构建的步骤是相似的，虽然我很想优化掉它，但是能力不太够
实现
自己实现的读写时序存在问题，改好bug后再贴出来
缺陷
我觉得最大的缺陷就是：排序的数比较固定，就是和其他Verilog实现的排序算法相似，都是存在这个问题，如果更改排序的数的个数，这个模块或多或少都要修改一部分
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
