sortedArrayUsingComparator 方法是如何实现的？

Question

我试图在 Objective-C 中重写官方 sortedArrayUsingComparator: 方法。我怎样才能做到这一点？

在NSArrayclass中，数组中的元素实际是如何存储的？ 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;
            }
        }
    }
}

Answer 1

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

在NSArrayclass中，实际上是如何存储添加到数组中的元素的？

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

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

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

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

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

比较方法如何工作？

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

您应该为 sortedArrayUsingComparator 指定 return 类型。我建议 NSArray。你的块也应该有一个 return 类型的 NSComparisonResult.

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

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

之一

我不清楚您的 selfArray 和 newArray 值是什么意思。看起来您正在比较 selfArray 中的值，然后根据该比较更改 newArray 的顺序。听起来你不是在问用于排序的算法，所以我就不用管它了。

Answer 2

一个class一旦定义就可以使用自己。 There-for it 可以在里面使用。

NSArray 有可能在其实现中使用 NSMutableArray，但这会很尴尬，因为 NSArray 是 NSMutableArray 的超class，如果超class 依赖于知识，则它被认为是糟糕的设计subclasses.

但是……

实际上我们从来没有处理过 NSArrays，也没有处理过 NSMutableArrays，它们 class clusters 在实例化时创建了其他子 classes 作为 __NSArrayI（不可变）和 __NSArrayM（可变）。如果他们都知道 public 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(n log n) 的更快实现，但需要更多内存（平均：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: 呈现给 public，很容易想象在不同情况下可能会在幕后使用不同的算法。 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;

What is the type (in the code: type?) i

id，翻译成«指向任何对象的指针»。您可以将其缩写为“任何对象”，因为 Objective-C 中的所有对象都只能通过指针访问。

sortedArrayUsingComparator 方法是如何实现的？

How is the sortedArrayUsingComparator method implemented?

sorting

cocoa-touch

compare

objective-c

ios

但是……