场景描述：任务连续执行，任务之间存在关联关系。一个任务包含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栈中，等待后续加入）：
public class Task {
private String serialNo;
private String relativeSerialNo;
public Task(String serialNo, String relativeSerialNo) {
this.serialNo = serialNo;
this.relativeSerialNo = relativeSerialNo;
}
public String getSerialNo() {
return serialNo;
}
public void setSerialNo(String serialNo) {
this.serialNo = serialNo;
}
public String getRelativeSerialNo() {
return relativeSerialNo;
}
public void setRelativeSerialNo(String relativeSerialNo) {
this.relativeSerialNo = relativeSerialNo;
}
@Override
public String toString() {
return "serialNo=" + serialNo + ";relativeSerialNo=" + relativeSerialNo + "\n";
}
}
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class TaskTest {
public List<Task> initTaskList() {
Task task1 = new Task("202003030900", "");
Task task2 = new Task("202003030902", "202003030901");
Task task3 = new Task("202003030903", "202003030902");
Task task4 = new Task("202003030901", "202003030900");
Task task5 = new Task("202003030905", "202003030904");
Task task6 = new Task("202003030906", "202003030905");
List<Task> taskList = new ArrayList<Task>();
taskList.add(task2);
taskList.add(task1);
taskList.add(task3);
taskList.add(task4);
taskList.add(task5);
taskList.add(task6);
return taskList;
}
public void testSort(List<Task> taskList) {
long start1 = System.currentTimeMillis();
System.out.println("Thead:" + Thread.currentThread().getId() + ",normal:\n" + taskList.toString());
System.out.println("Thead:" + Thread.currentThread().getId() + ",normal spends:" + (System.currentTimeMillis() - start1));
long start2 = System.currentTimeMillis();
Stack stack = new Stack();
List<Task> backTaskList = new ArrayList<Task>();
for (int i = 0; i < taskList.size(); i++) {
Task task = taskList.get(i);
if ("".equals(task.getRelativeSerialNo()) || task.getRelativeSerialNo() == null) {
backTaskList.add(task);
} else {
if (backTaskList.size() > 0) {
Task backTask = backTaskList.get(backTaskList.size() - 1);
if (task.getRelativeSerialNo().equals(backTask.getSerialNo())) {
backTaskList.add(task);
Task stackTask;
Stack backStack = new Stack();
int loopCount = 0;
while(stack.size() > 0) {
loopCount++;
stackTask = (Task) stack.pop();
if (stackTask != null) {
backTask = backTaskList.get(backTaskList.size() - 1);
if (stackTask.getRelativeSerialNo().equals(backTask.getSerialNo())) {
backTaskList.add(stackTask);
} else {
backStack.push(stackTask);
}
}
if (stack.size() == 0) {
stack = backStack;
}
if (loopCount > taskList.size()) {
break;
}
}
} else {
stack.push(task);
}
} else {
stack.push(task);
}
}
}
if (stack.size() > 0) {
for (int i = 0; i < taskList.size(); i++) {
if (!backTaskList.contains(taskList.get(i))) {
backTaskList.add(taskList.get(i));
}
}
}
taskList.clear();
taskList.addAll(backTaskList);
System.out.println("Thead:" + Thread.currentThread().getId() + ",sort:\n" + taskList.toString());
System.out.println("Thead:" + Thread.currentThread().getId() + ",sort spends:" + (System.currentTimeMillis() - start2));
}
public static void main(String[] args) throws IOException {
TaskTest taskTest = new TaskTest();
List<Task> taskList = taskTest.initTaskList();
taskTest.testSort(taskList);
System.out.println("Thead:" + Thread.currentThread().getId() + ",Final:\n" + taskList.toString());
System.in.read();
}
}
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
]
总结：主动思考，用技术解决业务问题。
