/threeWaysMergeSort

三路归并排序 qt 可视化

Primary LanguageC++MIT LicenseMIT

三路归并排序可视化

License

实现思路

  1. 窗体大小固定, 便于编写代码。
  2. 排序元素随机生成,但是排序后的序列是指定的,即排序后元素 的间隔是相同的,随机只是打乱顺序,这样绘制出来比较好看。
  3. 绘制操作必须在主线程进行,子线程负责执行排序流程,每一步操作执行后 如果需要移动或者绘制图形颜色则通过信号的方式发送给主线程绘制。
  4. 图像分为两层,上层展示原数组,下层展示临时数组,当原数组中的元素 放入临时数组时,则将上层对应元素的矩形先更换颜色,然后先向下移动,再水平移动到临时数组对应位置, 当这一层三路的元素都放置到临时数组后,从首个元素开始向上移动,每移动完成一个 元素,颜色就重新恢复。
  5. 最后当所有元素都排序完成后,从第一个元素开始依次更新元素的颜色。
  6. 关于矩形元素的宽度,设置为 [scene 宽度 / 元素数量],类型为 qreal,矩形的高度 即是元素的大小,排序则就是按矩形的高度进行从小到大排列。
  7. 排序线程构造时传入 items 的不可变引用 const vector<QGraphicsItem *>& ,子线程根据它维护一个索引 数组,排序实际上是对索引数组的排序, 比较的时候通过索引访问对应的 item 高度。
  8. 当需要对元素进行操作时,通过发送信号操作指定索引对应的 item。

效果图

demo.png