在 NSMutableDictionary 上使用 keysSortedByValueUsingComparator 方法的速度是多少

Question

我有一个 NSMutableDictionary，我想将其作为键打印出来：按排序顺序排列的值（其中键是这样的，首先打印具有较低值的键）。

为此，我正在使用 keysSortedByValueUsingComparator: NSDictionary 的方法，如下所示。

有谁知道底层实现是否使用类似快速排序的方法并实现了 O(N*logN)，或者是否将每个对象与其他每个对象进行比较导致 O(N^2) 复杂度？

示例：

NSMutableDictionary *hashTable = [[NSMutableDictionary alloc] init];
....
code that adds a bunch of Objects to the hashtable dictionary with key = NSString and value = NSNumber object
....
NSArray * sortedKeys = [hashTable keysSortedByValueUsingComparator:^(id  _Nonnull obj1, id  _Nonnull obj2) {
           if ([obj1 integerValue] > [obj2 integerValue])
           {
               return (NSComparisonResult)NSOrderedDescending;
           }

           if ([obj1 integerValue] < [obj2 integerValue])
           {
               return (NSComparisonResult)NSOrderedAscending;
           }

           return (NSComparisonResult)NSOrderedSame;
       }];

for (NSString *nextKey in sortedKeys)
{
   NSLog(@"%@: %@",nextKey,hashTable[nextKey]);
}

Answer 1

它似乎使用了归并排序——当然是 O(n log n)。已知其他排序方法使用快速排序。

如何猜测：在你的比较器块中放置一个断点，并在它被击中时读取堆栈跟踪。在您的代码中，您会看到 CFSimpleMergeSort 正在调用比较器。这是一个很好的猜测，除非 Apple 程序员有一个有趣的命名方案，否则这是一个合并排序！

也许如何确定：主要的 NS 集合是免费桥接到它们的 CF 对应集合的，并且 CF 源代码可以从 Apple 的开源站点获得。搜索 CFArray.c、CFDictionary.c 等，您将找到来源。这将不包括所有 NS 方法，因此 "maybe find out"，但它显示了这些类型的工作方式。

HTH

在 NSMutableDictionary 上使用 keysSortedByValueUsingComparator 方法的速度是多少

What is speed of using keysSortedByValueUsingComparator method on a NSMutableDictionary

sorting

objective-c

nsmutabledictionary