NSArray使用的排序算法是否稳定排序？

Question

NSArray中各种排序方法使用的排序算法是否稳定？(因为它们是"稳定排序"算法,其中具有相同排序键的项目保留了相对顺序.)

Answer 1

除非您使用,否则无法保证稳定的排序NSSortStable.从NSSortOptions的文档:

NSSortStable

指定排序结果应返回比较项目按其最初发生的顺序具有相等值.

如果未指定此选项,则可以或可以不按原始顺序返回相等的对象.

如果您需要保证稳定的排序,请尝试以下方法:

[array sortWithOptions:NSSortStable usingComparator:^NSComparisonResult(id obj1, id obj2) {
    return [obj1 compare:obj2];
}];

Answer 2

我发现的唯一"官方"答案是来自Apple的Chris Kane 的2002年邮件列表:

NSArray/NSMutableArray的排序方法的稳定性是未定义的,因此您应该预期它们不稳定.由于未定义,情况也可能因发布而异,但我(我自己)并未预料到这种可能性.当前的实现使用快速排序,该算法的版本几乎与BSD的qsort()例程相同.在一个点上发现了一堆实验,很难比我们在测试中通过的一般数据类型做得更好.[当然,如果有关于正在排序的数据的其他信息,可以使用其他算法或修改来帮助这种情况.]

我不知道这是否仍然是正确的,给出的职位有多老,但它可能是最好的假设NSArray的排序方法是不稳固.

Answer 3

在文档中，没有给出相同项目的最终订单的详细信息。

因此，我觉得对订单做出任何假设都是一个坏主意。即使您通过实验确定顺序是什么，这也可能会根据数组中的项目数或运行排序的 iOS 版本而改变。

对我来说，我会坚持文档提供的承诺。