场景描述：任务连续执行，任务之间存在关联关系。一个任务包含serialNo，relativeSerialNo两个关键属性。第一个任务relativeSerialNo为空，后续任务的relativeSerialNo为前一个任务的serialNo。
需求：得到的任务列表可能是乱序的，怎么让任务列表有序。
示例：
原任务列表：[{serialNo:"1",relativeSerialNo:"0"},{serialNo:"0",relativeSerialNo:""},{serialNo:"2",relativeSerialNo:"1"}]
排序后列表：[{serialNo:"0",relativeSerialNo:""},{serialNo:"1",relativeSerialNo:"0"},{serialNo:"2",relativeSerialNo:"1"}]
OK，现在基于上述需求，我们来写个简单的算法实现下（主要思想：relativeSerialNo为空的作为排序列表第一个任务，后续任务的relativeSerialNo与排序列表最后一个任务的serialNo比较，相等就加入到排序序列，不相等就加到Stack栈中，等待后续加入）：
1 public class Task {
2 private String serialNo;
3 private String relativeSerialNo;
4
5 public Task(String serialNo, String relativeSerialNo) {
6 this.serialNo = serialNo;
7 this.relativeSerialNo = relativeSerialNo;
8 }
9
10 public String getSerialNo() {
11 return serialNo;
12 }
13
14 public void setSerialNo(String serialNo) {
15 this.serialNo = serialNo;
16 }
17
18 public String getRelativeSerialNo() {
19 return relativeSerialNo;
20 }
21
22 public void setRelativeSerialNo(String relativeSerialNo) {
23 this.relativeSerialNo = relativeSerialNo;
24 }
25
26 @Override
27 public String toString() {
28 return "serialNo=" + serialNo + ";relativeSerialNo=" + relativeSerialNo + "\n";
29 }
30 }
1 import java.io.IOException;
2 import java.util.ArrayList;
3 import java.util.List;
4 import java.util.Stack;
5
6 public class TaskTest {
7 public List<Task> initTaskList() {
8 Task task1 = new Task("202003030900", "");
9 Task task2 = new Task("202003030902", "202003030901");
10 Task task3 = new Task("202003030903", "202003030902");
11 Task task4 = new Task("202003030901", "202003030900");
12 Task task5 = new Task("202003030905", "202003030904");
13 Task task6 = new Task("202003030906", "202003030905");
14
15 List<Task> taskList = new ArrayList<Task>();
16 taskList.add(task2);
17 taskList.add(task1);
18 taskList.add(task3);
19 taskList.add(task4);
20 taskList.add(task5);
21 taskList.add(task6);
22
23 return taskList;
24 }
25
26 public void testSort(List<Task> taskList) {
27 long start1 = System.currentTimeMillis();
28 System.out.println("Thead:" + Thread.currentThread().getId() + ",normal:\n" + taskList.toString());
29 System.out.println("Thead:" + Thread.currentThread().getId() + ",normal spends:" + (System.currentTimeMillis() - start1));
30
31 long start2 = System.currentTimeMillis();
32
33 Stack stack = new Stack();
34 List<Task> backTaskList = new ArrayList<Task>();
35 for (int i = 0; i < taskList.size(); i++) {
36 Task task = taskList.get(i);
37 if ("".equals(task.getRelativeSerialNo()) || task.getRelativeSerialNo() == null) {
38 backTaskList.add(task);
39 } else {
40 if (backTaskList.size() > 0) {
41 Task backTask = backTaskList.get(backTaskList.size() - 1);
42 if (task.getRelativeSerialNo().equals(backTask.getSerialNo())) {
43 backTaskList.add(task);
44
45 Task stackTask;
46 Stack backStack = new Stack();
47 int loopCount = 0;
48 while(stack.size() > 0) {
49 loopCount++;
50
51 stackTask = (Task) stack.pop();
52 if (stackTask != null) {
53 backTask = backTaskList.get(backTaskList.size() - 1);
54 if (stackTask.getRelativeSerialNo().equals(backTask.getSerialNo())) {
55 backTaskList.add(stackTask);
56 } else {
57 backStack.push(stackTask);
58 }
59 }
60 if (stack.size() == 0) {
61 stack = backStack;
62 }
63
64 if (loopCount > taskList.size()) {
65 break;
66 }
67 }
68 } else {
69 stack.push(task);
70 }
71 } else {
72 stack.push(task);
73 }
74 }
75 }
76 if (stack.size() > 0) {
77 for (int i = 0; i < taskList.size(); i++) {
78 if (!backTaskList.contains(taskList.get(i))) {
79 backTaskList.add(taskList.get(i));
80 }
81 }
82 }
83
84 taskList.clear();
85 taskList.addAll(backTaskList);
86
87 System.out.println("Thead:" + Thread.currentThread().getId() + ",sort:\n" + taskList.toString());
88 System.out.println("Thead:" + Thread.currentThread().getId() + ",sort spends:" + (System.currentTimeMillis() - start2));
89 }
90
91 public static void main(String[] args) throws IOException {
92 TaskTest taskTest = new TaskTest();
93
94 List<Task> taskList = taskTest.initTaskList();
95 taskTest.testSort(taskList);
96
97 System.out.println("Thead:" + Thread.currentThread().getId() + ",Final:\n" + taskList.toString());
98
99 System.in.read();
100 }
101 }
运行结果展示：
Thead:1,normal: [serialNo=202003030902;relativeSerialNo=202003030901 , serialNo=202003030900;relativeSerialNo= , serialNo=202003030903;relativeSerialNo=202003030902 , serialNo=202003030901;relativeSerialNo=202003030900 , serialNo=202003030905;relativeSerialNo=202003030904 , serialNo=202003030906;relativeSerialNo=202003030905 ] Thead:1,normal spends:1 Thead:1,sort: [serialNo=202003030900;relativeSerialNo= , serialNo=202003030901;relativeSerialNo=202003030900 , serialNo=202003030902;relativeSerialNo=202003030901 , serialNo=202003030903;relativeSerialNo=202003030902 , serialNo=202003030905;relativeSerialNo=202003030904 , serialNo=202003030906;relativeSerialNo=202003030905 ] Thead:1,sort spends:0 Thead:1,Final: [serialNo=202003030900;relativeSerialNo= , serialNo=202003030901;relativeSerialNo=202003030900 , serialNo=202003030902;relativeSerialNo=202003030901 , serialNo=202003030903;relativeSerialNo=202003030902 , serialNo=202003030905;relativeSerialNo=202003030904 , serialNo=202003030906;relativeSerialNo=202003030905 ]
总结：主动思考，用技术解决业务问题。