sortedArrayUsingComparator方法是如何实现的

我试图在Objective-C中重写官方的sortedArrayUsingComparator:方法。我该怎么做？

在NSArray类中，元素实际上是如何存储在数组中的？for循环中的类型（在代码中：type?）是什么？在Objective-C中似乎不存在泛型。compare:方法是如何工作的？

- (NSArray *)recentQuestions {
    return [questions sortedArrayUsingComparator: ^(id obj1, id obj2) {
        Question *q1 = (Question *)obj1; 
        Question *q2 = (Question *)obj2; 
        return [q2.date compare: q1.date];
}]; }
//class NSArray
//? NSArray* selfArray = @[];
-(...) sortedArrayUsingComparator : (void (^)(id obj1, id obj2) ) blockName{
    for ( int i=0; i<selfArray.count-1; i++){ 
        for ( int j=i+1; j<selfArray.count; j++){ 
            type? *bigger = blockName(selfArray[i], selfArray[j]);          
            //move items if j>i
            if (bigger isEqual:selfArray[j]) {
                int tempValue = newArray[i];
                newArray[i] = newArray[j];
                newArray[j] = tempValue;
            }
        }
    }
}

类一定义就可以使用它自己。因为它可以在里面使用。

NSArray可能在其实现中使用NSMutableArray，但这将是尴尬的，因为NSArray是NSMutabableArray的超类，如果超类依赖于知识子类，则被认为是糟糕的设计。

但是

实际上，我们从来没有处理过NSArray，也没有处理过NSFutableArrays，它们是类簇，在实例化时创建其他子类，如__NSArrayI（不可变）和__NSArrayM（可变）。如果他们两个都知道公共NSMutableArray接口，那绝对没问题。

该方法可能只在数组上进行两次循环（更可能是一些更好的排序算法。对于不同的内存情况，甚至是多次循环），并在返回不可变副本之前填充NSMutableArray。

具有运行时复杂性O（n²）和内存使用率O（1）的基本实现可能如下所示：

@interface NSArray (Comparator)
-(NSArray *)vs_sortedArrayUsingComparator:(NSComparisonResult(^)(id obj1, id obj2))comparator;
@end
@implementation NSArray (Comparator)
-(NSArray *)vs_sortedArrayUsingComparator:(NSComparisonResult(^)(id obj1, id obj2))comparator
{
    NSMutableArray *array = [self mutableCopy];
    if ([array count] > 1) {
        for (NSUInteger i = 0; i < [array count] - 1; ++i) {
            for (NSUInteger j  = i; j < [array count]; ++j) {
                if (comparator(array[i], array[j]) == NSOrderedDescending) {
                    [array exchangeObjectAtIndex:i withObjectAtIndex:j];
                }
            }
        }
    }
    return [array copy];
}
@end

用法：

NSArray *array = @[@4, @9, @2, @1, @7];
array = [array vs_sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
    return  [obj1 compare:obj2];
}];

中的结果

运行时复杂度为O（nlogn）的更快实现，但需要更多内存（平均值：O（log（n

@interface NSArray (Comparator)
-(NSArray *)vs_sortedArrayUsingComparator:(NSComparisonResult(^)(id obj1, id obj2))comparator;
@end
@implementation NSArray (Comparator)
-(NSArray *) quicksortUsingComparator:(NSComparisonResult(^)(id obj1, id obj2))comparator
{
    NSArray *array = [self copy];
    if ([array count]<2) return [array copy];
    id pivot = [array randomElement];
    NSMutableArray *array2= [NSMutableArray array];
    array = [array arrayByPerformingBlock:^id  (id element) { return element;}
                      ifElementPassesTest:^BOOL(id element) { return comparator(element, pivot) == NSOrderedAscending;}
                         elsePerformBlock:^    (id element) { if (element!=pivot) [array2 addObject:element];}
            ];
    return [[[array quicksortUsingComparator:comparator]
                                    arrayByAddingObject:pivot]
                                        arrayByAddingObjectsFromArray:[array2 quicksortUsingComparator:comparator]];
}
-(NSArray *)vs_sortedArrayUsingComparator:(NSComparisonResult(^)(id obj1, id obj2))comparator
{
    return [self quicksortUsingComparator:comparator];
}
@end

由于在这两种实现中，只有vs_sortedArrayUsingComparator:向公众展示，因此很容易想象，在不同的情况下，在幕后可能会使用不同的算法。快速排序是一个非常快的方法，但对于非常大的列表，它可能会造成堆栈溢出。在这种情况下，最好切换到另一种可能较慢但实现就地排序的算法。

Quicksort示例的完整实现可以在这里找到：http://vikingosegundo.github.io/2015/02/05/implement-comparator/

包括

- (NSArray *)arrayByPerformingBlock:(id (^)(id element))performBlock ifElementPassesTest:(BOOL (^)(id element))testBlock elsePerformBlock:(void (^)(id element))elseBlock;
和

-(id)randomElement;
的类型是什么（在代码中：type？）
id，翻译为"指向任何对象的指针"。您可以将其缩写为"任何对象"，因为Objective-C中的所有对象都只能通过指针访问。

我将尝试回答您提出的问题。

在NSArray类中，如何实际存储添加到数组中的元素

我想你在问如何在NSArray中添加新元素或修改元素的顺序。这是不可能的。如果需要更改数组的内容，则应该使用NSMutableArray。对于NSMutableArray，以下情况是可能的：

id tempValue = newArray[i];
newArray[i] = newArray[j];
newArray[j] = tempValue;

for循环中的类型（代码为type?）是什么？Generics似乎不存在于objective-c中

您应该期望的类型是您从块中获得的任何返回类型。在您的情况下，您指定的块具有void返回类型，这意味着您实际上不应该尝试从其结果中分配变量。下面，您将看到返回类型应列为NSComparisonResult。

在我对第一个问题的回答中，您可能已经注意到在objective-c:id中如何处理泛型指针。每个非基元对象都可以保存在一个id变量中。

比较方法是如何工作的

-(...) sortedArrayUsingComparator : (void (^)(id obj1, id obj2) ) blockName{

您应该为sortedArrayUsingComparator指定一个返回类型。我建议NSArray。您的块还应该具有返回类型NSComparisonResult。

-(NSArray *) sortedArrayUsingComparator : (NSComparisonResult (^)(id obj1, id obj2) ) blockName{

现在，当您调用块时，您将获得一个表示比较两个对象的结果的值。这将是NSOrderedSame、NSOrderedDescending或NSOrderedAscending中的一个。

我不清楚您的selfArray和newArray值在这里是什么。看起来您正在比较selfArray中的值，但随后根据该比较更改newArray的顺序。听起来你并不是在问用于排序的算法，所以我就不谈了。

但是

相关内容

最新更新

热门标签：