objective-c - NSArray 使用的排序算法是稳定排序吗？

Question

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

Answer 1

除非您使用NSSortStable. 从NSSortOptions 的文档中：

NSSortStable

指定排序结果应返回具有相同值的比较项，其值与它们最初出现的顺序相同。

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

如果您需要保证稳定的排序，请尝试以下操作：

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

Answer 2

我发现的唯一“官方”答案是2002 年来自 Apple 的 Chris Kane 的邮件列表帖子：

NSArray/NSMutableArray 的排序方法的稳定性是不确定的，所以你应该预料到它们是不稳定的。由于未定义，情况也可能因版本而异，尽管我（我自己）不认为这是可能的。当前实现使用快速排序，该算法的一个版本几乎与 BSD 的 qsort() 例程相同。一堆实验发现，很难比我们在测试中通过的一般数据类型做得更好。[当然，如果有关于被排序数据的附加信息，可以使用其他有助于该情况的算法或修改。]

我不知道这是否仍然正确，考虑到帖子的历史，但最好假设NSArray's 的排序方法不稳定。

Answer 3

在doc中，没有详细说明相同项目的最终顺序。

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

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