为TList和TStringList添加稳定排序的简便方法

Question

我使用TList/TObjectList和TStringList(带有关联对象)来执行大量任务,既可以是原样,也可以作为更复杂结构的基础.虽然排序功能通常足够好,但我有时需要进行稳定排序,两个列表都使用快速排序.

为TList和/或TStringList实现稳定排序的最简单方法是什么？我是否必须编写自己的排序例程,还是可以通过TStringListSortCompare/TListSortCompare使用一些聪明的技巧来完成？

Answer 1

你必须编写自己的排序例程.

您可以阅读当前的QuickSort实现,并编写自己的稳定版本(例如合并排序或任何其他稳定版本).

一些技巧:

• 如果您确定索引是< Count,则可以使用快速指针数组(TList.List[])而不是较慢Items[]或GetItem():子方法调用和范围检查会降低执行速度;
• 比较功能大部分时间都是搜索的速度瓶颈 - 所以要照顾这一部分;
• 如果您需要速度,请使用真实的分析器而不是真实的(例如随机的)数据 - 但要在快速之前使其正确;
• 从现有的排序实现开始;
• 要最小化堆栈空间,可以使用临时记录在递归调用之间存储和共享变量.