好问题。尽管拓扑排序可能是最推荐的方法，但您必须首先解析输入以构建依赖关系列表。我想到了一种更直接的方法，基于查找出现在多个列表中的项目来设置订单定义。
我无法预测任何时间复杂度，但由于您不关心性能，特别是考虑到项目总数最多为 500，我认为这个算法应该可以很好地工作。
算法
- 所有列表都放在一个临时列表中，然后自然排序以识别和筛选所有重复项。那些名为Keys的重复项构成了最终排序顺序的唯一定义。
- Key 列表通过比较每两个项目按输入排序顺序进行排序：如果两个 Key 出现在同一个输入列表中，则该列表中的第一个也排在输出列表中的第二个之前。如果两个键在任何输入列表中不同时出现，则认为它们相等。
- 随后，一个循环在密钥上循环。
- 在每个循环中，在每个输入列表中，前一个 Key 和当前 Key 之间的每个项目都被添加到输出列表中。一个循环以当前密钥的添加结束。
执行
type
TSorterStringList = class(TStringList)
protected
Id: Integer;
KeyId: Integer;
function Current: String;
public
constructor Create;
end;
TSorterStringLists = class(TObjectList)
private
function GetItem(Index: Integer): TSorterStringList;
public
property Items[Index: Integer]: TSorterStringList read GetItem; default;
end;
TSorter = class(TObject)
private
FInput: TSorterStringLists;
FKeys: TStringList;
procedure GenerateKeys;
function IsKey(const S: String): Boolean;
public
constructor Create;
destructor Destroy; override;
procedure Sort(Output: TStrings);
property Input: TSorterStringLists read FInput;
end;
{ TSorterStringList }
constructor TSorterStringList.Create;
begin
inherited Create;
KeyId := -1;
end;
function TSorterStringList.Current: String;
begin
Result := Strings[Id];
end;
{ TSorterStringLists }
function TSorterStringLists.GetItem(Index: Integer): TSorterStringList;
begin
if Index >= Count then
Count := Index + 1;
if inherited Items[Index] = nil then
inherited Items[Index] := TSorterStringList.Create;
Result := TSorterStringList(inherited Items[Index]);
end;
{ TSorter }
constructor TSorter.Create;
begin
inherited Create;
FInput := TSorterStringLists.Create(True);
FKeys := TStringList.Create;
end;
destructor TSorter.Destroy;
begin
FKeys.Free;
FInput.Free;
inherited Destroy;
end;
threadvar
CurrentSorter: TSorter;
function CompareKeys(List: TStringList; Index1, Index2: Integer): Integer;
var
Input: TSorterStringLists;
I: Integer;
J: Integer;
K: Integer;
begin
Result := 0;
Input := CurrentSorter.Input;
for I := 0 to Input.Count - 1 do
begin
J := Input[I].IndexOf(List[Index1]);
K := Input[I].IndexOf(List[Index2]);
if (J > - 1) and (K > -1) then
begin
Result := J - K;
Break;
end;
end;
end;
procedure TSorter.GenerateKeys;
var
All: TStringList;
I: Integer;
begin
All := TStringList.Create;
try
All.Sorted := True;
All.Duplicates := dupAccept;
for I := 0 to FInput.Count - 1 do
All.AddStrings(FInput[I]);
for I := 0 to All.Count - 2 do
if (All[I] = All[I + 1]) then
if (FKeys.Count = 0) or (FKeys[FKeys.Count - 1] <> All[I]) then
FKeys.Add(All[I]);
finally
All.Free;
end;
CurrentSorter := Self;
FKeys.CustomSort(CompareKeys);
end;
function TSorter.IsKey(const S: String): Boolean;
begin
Result := FKeys.IndexOf(S) > -1;
end;
procedure TSorter.Sort(Output: TStrings);
var
KeyId: Integer;
I: Integer;
List: TSorterStringList;
begin
if FInput.Count = 0 then
Exit;
Output.BeginUpdate;
try
GenerateKeys;
for KeyId := -1 to FKeys.Count - 1 do
begin
for I := 0 to FInput.Count - 1 do
begin
List := FInput[I];
if List.KeyId <= KeyId then
while (List.Id < List.Count) and not IsKey(List.Current) do
begin
Output.Add(List.Current);
Inc(List.Id);
end;
while (List.Id < List.Count) and IsKey(List.Current) do
begin
List.KeyId := FKeys.IndexOf(List.Current);
Inc(List.Id);
end;
end;
if KeyId + 1 < FKeys.Count then
Output.Add(FKeys[KeyId + 1]);
end;
finally
Output.EndUpdate;
end;
end;
示例用法
procedure TForm1.Button1Click(Sender: TObject);
var
Sorter: TSorter;
begin
Sorter := TSorter.Create;
try
Sorter.Input[0].CommaText := '1, 2, 4, 9, 10, 11, 22, 46, 48, 51, 70, 72';
Sorter.Input[1].CommaText := '3, 9, 23, 43, 44, 45, 47, 48, 51, 71, 90, 91';
Sorter.Input[2].CommaText := '0, 3, 4, 7, 8, 11, 23, 50, 51, 52, 55, 70';
Sorter.Input[3].CommaText := '2, 6, 14, 15, 36, 37, 38, 39, 51, 65, 66, 77';
Sorter.Input[4].CommaText := '5, 27, 120, 130';
ListBox1.Items.Assign(Sorter.Input[0]);
ListBox2.Items.Assign(Sorter.Input[1]);
ListBox3.Items.Assign(Sorter.Input[2]);
ListBox4.Items.Assign(Sorter.Input[3]);
ListBox5.Items.Assign(Sorter.Input[4]);
Sorter.Sort(ListBox6.Items);
// Results in:
// 1, 0, 5, 27, 120, 130, 3, 2, 6, 14, 15, 36, 37, 38, 39, 4, 7, 8, 9, 10,
// 11, 22, 46, 23, 43, 44, 45, 47, 50, 48, 51, 71, 90, 91, 52, 55, 65, 66,
// 77, 70, 72
finally
Sorter.Free;
end;
end;