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

Question

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

objective-ciossortingnsarray

11

各种NSArray排序方法中使用的排序算法是否稳定？（即它们是否是“稳定排序”算法，其中具有相同排序键的项目保留其相对顺序。）

- StCredZero

6

“试一试”对于这种情况并不是很有用。排序可能在某些情况下是稳定的，但在其他情况下却不是，这取决于数据的大小、数组的构造方式等因素。 - omz

好的，我以为行为一直都是一样的。知道了就好。 - Titouan de Bailleul

如果它在单一情况下不稳定，那么它就是不稳定的。因此，“试一试”确实是有帮助的。 - gnasher729

3个回答

7

我找到的唯一“官方”答案是来自苹果公司的Chris Kane在2002邮件列表帖子中写道：

“NSArray / NSMutableArray的排序方法的稳定性是未定义的，因此您应该预计它们是不稳定的。由于未定义，情况也可能会从发布到发布发生变化，尽管我（个人而言）不认为这很可能。当前的实现使用快速排序，这是几乎与BSD的qsort（）例程相同的算法版本。一堆实验曾经发现，在我们通过测试时很难做得比那更好，适用于一般类型的数据。[当然，如果有关于正在排序的数据的其他信息，则可以使用其他算法或修改使其有所帮助。]”

我不知道这是否仍然正确，因为这篇文章太旧了，但最好假设 NSArray 的排序方法不稳定。

- omz

4

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

因此，我认为对顺序做出任何假设都是不明智的。即使你通过实验确定了顺序，这也可能会根据数组中的项目数量或运行排序的iOS版本而改变。

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

- Jeffery Thomas

即使我已经彻底测试过它，我也不会相信它，因为苹果可能会在下一个版本中更改所使用的算法，使任何测试都变得毫无意义，并可能导致一些奇怪的错误。 - JustSid

4

文档确实进行了规定，只不过它被深深地埋藏在NSSortOptions的文档后面：https://developer.apple.com/library/ios/#documentation/Cocoa/Reference/Foundation/Miscellaneous/Foundation_Constants/Reference/reference.html#//apple_ref/doc/c_ref/NSSortOptions - wxactly

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- wxactly · Accepted Answer

稳定排序不保证除非您使用NSSortStable。从NSSortOptions的文档中可知：

NSSortStable

指定排序结果应返回在原始顺序中具有相等值的比较项目。

如果未指定此选项，则可能或可能不会以其原始顺序返回等效对象。

如果您需要保证稳定排序，请尝试以下内容：

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