Вам по сути нужна разновидность топологической сортировки.
Воспользуемся стандартным методом слияния списков. Я пишу на C#, в нём LinkedList
не умеет сливаться, так что я написал свой велосипед.
Вспомогательные классы:
class LinkedNode<T>
{
public T Entry;
public LinkedNode<T> Next;
}
class MergeableLinkedList<T>
{
public LinkedNode<T> First, Last;
public MergeableLinkedList(T head)
{
First = new LinkedNode<T>() { Entry = head };
Last = First;
}
public void Merge(MergeableLinkedList<T> other) // other is destroyed
{
Last.Next = other.First;
Last = other.Last;
}
}
Ваша структура данных:
class Entry
{
public int id;
public int? parent;
}
Данные:
var data = new Entry[]
{
new Entry() { id = 1 },
new Entry() { id = 2, parent = 1 },
new Entry() { id = 3 },
new Entry() { id = 4, parent = 1 },
new Entry() { id = 5, parent = 3 },
new Entry() { id = 6, parent = 4 }
};
Сортировка:
// создаём списки
var lists = new Dictionary<int, MergeableLinkedList<Entry>>();
foreach (var d in data)
lists[d.id] = new MergeableLinkedList<Entry>(d);
// сливаем их
foreach (var d in data)
{
// если есть предок...
if (d.parent != null)
{
var parentId = d.parent.Value;
// свой список подцепляем в конец списка предка
lists[parentId].Merge(lists[d.id]);
lists[d.id] = lists[parentId];
}
}
// и перепаковываем всё в новый массив
var newData = new Entry[data.Length];
var newDataIndex = 0;
foreach (var d in data)
{
if (d.parent == null)
{
for (var curr = lists[d.id].First; curr != null; curr = curr.Next)
newData[newDataIndex++] = curr.Entry;
}
}
Вывод:
foreach (var d in newData)
{
if (d.parent != null)
Console.Write(d.parent + ".");
Console.WriteLine(d.id);
}
Результат:
1
1.2
1.4
4.6
3
3.5
[5.1, 4, 3.2, 2, 1.1, 1].sort()
годится?