为TList和TStringList添加稳定排序的简单方法 [英] Easy way to add stable sorting to TList and TStringList

问题描述

我使用TList / TObjectList和TStringList（与关联的对象）进行多个任务，无论是原样还是作为更复杂结构的基础。虽然排序功能通常足够好，我有时需要执行 stable 排序，两个列表都使用quicksort。

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

解决方案

您必须编写自己的排序例程。

您可以阅读当前的QuickSort实现，并编写自己的稳定版本（例如，合并排序或任何其他稳定的变体）。

一些技巧： / p>

• 如果您确定索引为< 计数，您可以使用快速指针数组（ TList.List [] ）而不是较慢的项目[] 或 GetItem（）：子方法调用和范围检查减慢执行速度;


• 比较功能大部分时间是搜索的速度瓶颈 - 所以请注意这一部分;


• 如果需要速度，请使用真实的分析器（例如随机的）数据 - 但是在使之快速进行之前使其正确;


• 从现有的排序实现开始;


• 为了最小化堆栈空间，您可以使用一个临时记录，用于在递归调用之间存储和共享变量。

I use TList/TObjectList and TStringList (with associated objects) for a multitude of tasks, either as-is, or as basis for more complex structures. While the sort functionality is usually good enough, I sometimes need to do a stable sort, and both lists use quicksort.

What's the easiest way to implement stable sorting for TList and/or TStringList? Do I have to write my own sorting routine, or can it be done by using some clever trick with TStringListSortCompare/TListSortCompare?

解决方案

You'll have to write your own sorting routine.

You can read the current QuickSort implementation, and write your own stable version (e.g. a Merge sort or any other stable variant).

Some tricks:

• If you are sure that an index is < Count, you can use the fast pointer array (TList.List[]) instead of slower Items[] or GetItem(): sub-method calling and range checking slow down the execution;
• The comparison function is most of the time the speed bottleneck of the search - so take care of this part;
• If you need speed, use a real profiler over real (e.g. random) data - but make it right before making it fast;
• Start from an existing implementation of the sort;
• To minimize stack space, you may use a temporary record to store and share variables among recursive calls.

这篇关于为TList和TStringList添加稳定排序的简单方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！