工艺规程其步骤排序算法评定分享

**

1.问题背景
步骤展示仅按时间排序。
步骤之间是有前后关系， 仅按时间排序并不能反应前后关系，不利于用户操作，不便于用户理解。
2. 如何才能让步骤展示便于理解？
构思：平铺按前后顺序到一个平面，然后按一定规则挨个取点，展示再列表中。这个一定规则就是需要的算法。
3.参考文献
现在市面上常见两种：广度优先、深度优先。
深度优先搜素算法：不全部保留结点，占用空间少；有回溯操作(即有入栈、出栈操作)，运行速度慢。
广度优先搜索算法：保留全部结点，占用空间大； 无回溯操作(即无入栈、出栈操作)，运行速度快。

1.例子展示：

深度优先首先从A 出发找到A指向的下一级B (A-B)，B指向的下一级C(A-B-C)，C下一级有D和E，但因为D比E先新增，于是C先指向D(A-B-C-D)，再从D回到C，从C指向E(A-B-C-D-E)，再回到B回到A，然后下一轮找到F(A-B-C-D-E-F)，F指向的B因为已经被记录，算法结束

广度优先首先找到 第一层起始步骤A和F，因为A比F先新增A在前面(A-F)，接下来找第二层与A F指向的B(A-F-B)，找B指向的C(A-F-B-C)，C指向D和E(A-F-B-C-D-E),到DE指向结束，算法结束.

2.算法选择
结合实际业务，这里我选择广度优先。
原因：当有多个 起始步骤(A、F)时，先会被执行的步骤将排在列表的前面。列表上始终有一条大致范围的业务线，【执行完成】【正在执行中】【未执行】三个区域。而深度优 排序的列表，在第二条B执行时，最后一条F被标记为执行完成，列表美观度上不够
3.实际编写
需求转换：要对一个步骤list进行排序，要求：金字塔级，第一层无前置步骤，第二层必须是第一层已经存在基础上才能存在，第三层必须……以此类推。

• 期望输入：oldList
• 期望输出：newList

因为需要递归 因此多几个参数
• 实际输入： newList，oldList，ids
• 实际输出： newList


时间复杂度： O < n²/2

分享者：朱志鹏
2020年1月15日